反向拓扑排序算法

Question

我正在寻找一种有效的算法来解决依赖图中一系列模块的依赖关系，具有以下约束:

• 该算法可以将一个或多个起始节点作为输入。
• 计算这些节点的依赖关系，以便可以并行加载它们。
• 如果图不是非循环的，则必须抛出错误。
• 它的复杂性应该尽可能小(不需要访问非必需的节点)——该图可能包含数十亿个节点，每个查询只需要其中的一小部分。

目标示例

在这个例子中，绿色的两个节点被提供作为起点。红色节点从未被访问过。访问了白色的每个节点。加载计划按步骤执行(在节点内指示)。

您对遵守这些规则的算法有什么建议吗？

Answer 1

这个问题可以通过使用拓扑排序来解决，在this中有描述。维基百科文章；请注意，该文章是从“依赖关系解决”重定向而来的。所描述算法的运行时间为

O(|V| + |E|)

其中 V 是节点集，E 是边集，即运行时间与输入大小成线性关系。