c++ - 如何对这个数据结构进行拓扑排序

Question

我正在尝试解决一些依赖项的问题，并且已经取得了很大的进展，但现在我陷入了困境。

假设我有一个像这样的数据结构:

map<string, vector<string>> deps;

其中映射中的每个键都是一个依赖节点，该键的值是依赖节点所依赖的节点列表。

此外，假设映射有 4 个键(A、B、C 和 D)以及以下依赖项:

我正在寻找一种算法(某种拓扑排序？)，它将产生一个字符串 vector ，使得字符串按以下顺序出现:

F, B, C, D, A
0  1  2  3  4

此列表表示评估依赖项的顺序。

Answer 1

我最近想出了一个基于 this algorithm 的解决方案:

这是针对您的数据结构稍作修改的版本:

#include <map>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

/**
 * Performs dependency resolution using
 * a topological sort
 */
template<typename ValueType>
class Resolver
{
public:
    using value_type = ValueType;
    using value_vec = std::vector<value_type>;
    using value_map = std::map<value_type, value_vec>;

private:
    value_vec seen;
    value_map deps;

    void resolve(value_type const& d, value_vec& sorted)
    {
        seen.push_back(d);
        for(auto const& nd: deps[d])
        {
            if(std::find(sorted.begin(), sorted.end(), nd) != sorted.end())
                continue;
            else if(std::find(seen.begin(), seen.end(), nd) == seen.end())
                resolve(nd, sorted);
            else
            {
                std::cerr << "Circular from " << d << " to " << nd << '\n';
                continue;
            }
        }
        sorted.push_back(d);
    }

public:

    /**
     * Clear the resolver ready for new
     * set of dependencies.
     */
    void clear()
    {
        seen.clear();
        deps.clear();
    }

    /**
     * Items that don't depend on anything
     */
    void add(value_type const& a)
    {
        deps[a];
    }

    /**
     * Item a depends on item b
     */
    void add(value_type const& a, value_type const& b)
    {
        deps[a].push_back(b);
    }

    value_vec resolve()
    {
        value_vec sorted;
        for(auto const& d: deps)
            if(std::find(sorted.begin(), sorted.end(), d.first) == sorted.end())
                resolve(d.first, sorted);
        return sorted;
    }
};

int main()
{
    Resolver<std::string> resolver;

    resolver.add("A", "B");
    resolver.add("A", "C");
    resolver.add("A", "D");

    resolver.add("B", "F");

    resolver.add("C", "B");
    resolver.add("C", "F");

    resolver.add("D", "C");

    resolver.add("F");

    for(auto const& d: resolver.resolve())
        std::cout << d << '\n';
}

输出:

F
B
C
D
A

如果您发现任何错误，请告诉我(尚未经过充分测试)。

从评论中添加:

For efficiency, in production code, if the node type (string, in this example) can be imbued with a flag to mark the node as seen/sorted, then the calls to std::find can be replaced with setting the seen/sorted values for flag. Of course, in this example, Galik couldn't do that, which is why std::find is used, instead. - @Dess