拓扑排序算法

Question

"I am building a dependency based scheduler where my tasks/nodes form a directed acyclic graph. I have the following constraints and am trying to decide on the most appropriate algorithm:

1. 新任务可以随时添加（具有或不具有依赖关系） 2. 一些任务可以并行运行

有关拓扑排序，经常提到两种算法：深度优先搜索和Kahn算法。

以下是这两种算法的优缺点： - 深度优先搜索：实现简单，但可能会导致栈溢出。 - Kahn算法：稳定且无栈溢出的风险，但需要使用额外数据结构。

对于我的情况，是否有一种算法更加适合？ 是否有其他算法更适合我的情况？

我还有一个词汇问题。给定依赖关系如下： "

c->b
b->a
e->d

这是否被视为一个有向无环图，2个有向无环图（因为e和d不依赖于其他任务），还是一个包含子有向无环图的有向无环图？

- Tom

Answer 1

我认为你误解了这些算法。

深度优先搜索：深度优先搜索算法（我在维基百科上查过，那里实际上称其为算法。我宁愿称其为策略）是一种用于遍历图形的算法，以访问所有节点。它不会返回您的图形的拓扑顺序！

Kahn算法：另一方面，Kahn算法是解决您的问题的正确算法。如果有拓扑顺序，它将返回给您。该算法具有O(m+n)的渐近运行时间，其中m是边缘数量，n是图中的顶点数量。我认为，您不会找到更好的算法来解决这个问题。

词汇：在您的示例中，您有一个带有两个弱连接组件的DAG（有向无环图）。

编辑：在您提到基于深度优先搜索的算法之后，对于渐近运行时间，使用哪种算法并不重要。两者都是O(m+n)。此外，关于存储，实际上应该没有关系。

- Andreas

---

深度优先搜索可以用于进行拓扑排序：https://en.wikipedia.org/wiki/Topological_sorting#Algorithms - Tom

哦，我明白了。但是请仔细阅读：“...基于深度优先搜索”，这并不奇怪，因为这是遍历图形的基本策略。 - Andreas