如何拓扑排序这个数据结构

Question

我正在弄清楚一些依赖性的东西，我走得很远，但现在我被卡住了。

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

map<string, vector<string>> deps;

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

此外，假设地图有 4 个键（A、B、C 和 D）以及以下依赖项：

我正在寻找一种算法（某种拓扑排序？），它会产生一个字符串向量，使字符串按以下顺序出现：

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

Answer 2

如您在问题中所述，映射中的每个键都是一个从属节点，该键处的值是从属节点所依赖或依赖的节点列表。

因此，实际的依赖关系类似于（例如，'from -> to' 形式的数据集）：

B -> A
C -> A
D -> A
F -> B
B -> C
F -> C
C -> D

思路是先找到起点。起点永远不会在条目的“到”一侧。一旦找到起点，我们就可以简单地遍历给定的集合以按顺序打印行程。以下是步骤。

以上面显示的形式创建一组给定的条目对（称为此数据集）。 'dataset' 的每个条目都是 "from->to".
寻找行程起点
- 创建反向集。让反向为 'reverseMap'。 'reverseMap' 的条目采用 "to->from" 的形式。以下是上述示例的 'reverseMap'。
```
A -> B
A -> C
A -> D
B -> F
C -> B
C -> F
D -> C
```
- 遍历'dataset'。对于数据集的每个键，检查它是否在 'reverseMap' 中表达式的左侧。如果密钥不存在，那么我们找到了起点。在上面的示例中，"F" 是起点。
- 从上面找到的起点出发，遍历'dataset'打印行程，考虑以下规则。
  - 当我们遇到一个节点出现在数据集中的多个 'from' 位置时，然后在表达式左侧的 reverseMap 中检查其所有 'to' 对应节点的频率并选择频率最低的那个。
  例如，当我们以"F"作为起始节点开始时，我们在数据集中有两个选项可以向前移动，即"F -> B"和"F -> C"。因此，我们在表达式左侧的 reverseMap 中检查 "C" 和 "B" 的频率，结果分别为 2 和 1。因此，我们继续处理 B 的条目 (F -> B)，并丢弃另一个条目 (F -> C)。以后将不再需要此条目。

希望对您有所帮助。与我分享，如果您发现任何错误，或者有什么要补充的。

如何拓扑排序这个数据结构

How to topologically sort this data struct

c++

sorting

dependencies