Show HN: TopoSort 库背后的拓扑排序算法

TopoSort 算法

William Wong, 2025-04-02

TopoSort 中使用的算法是 Kahn 算法的一个变体，它以集合而不是单个节点的方式处理节点，并增加了寻找独立子集和寻找循环节点的功能。

概述

主要思想是迭代地找到图的连续根集合，并在每一轮中移除它们。以下是该算法的高级概述：

1. 找到图的第一个根集合。
2. 从图中删除根集合的节点。
3. 找到下一个根集合。转到第 2 步，直到图为空。

连续移除的根集合形成一个拓扑顺序。每个根集合中的节点在该根集合中是相互独立的。此外，当节点按照根集合的顺序排列时，它们也是一个拓扑顺序。

示例

对于具有节点 {a, b, c, d, e, f} 的图，连续移除的根集合如下所示：

{a, b} | {c, d, e, f}
{a, b} {d} | {c, e, f}
{a, b} {d} {c, e} | {f}
{a, b} {d} {c, e} {f}

原理

根据定义，有向无环图 (DAG) 的节点的拓扑顺序是指这些节点以线性方式排序，以使一个节点不依赖于任何位于其后的节点。

在 DAG 图中，存在一些不依赖于任何其他节点的节点。这些是图的根节点，图的遍历从它们开始。这些节点形成初始根集合。

我们定义，当节点 y 依赖于 x 时，节点 y 具有来自 x 的传入链接。当节点 x 被移除时，到 y 的传入链接也被移除。

从图中移除根集合的节点会导致依赖于它们的剩余节点的依赖性减少一个，即它们的传入链接递减。对于传入链接达到 0 的节点，它们成为新的根节点，因为它们不依赖于任何人。

我们定义，当 A 的所有成员都不依赖于 B 的任何成员时，集合 A 不依赖于集合 B。

因此，迭代期间移除的每个根集合都不依赖于其后的任何其他根集合，因此，连续移除的根集合的序列形成一个拓扑顺序。

独立子集

根集合中的节点彼此之间没有依赖关系，因为根据定义，根节点不依赖于任何其他节点。根集合中这些相互独立的节点允许在根集合的范围内进行并行处理。

当所有根集合的节点按照根集合的顺序排列时，它们也形成一个拓扑顺序。

循环节点检测

使用“rooted”列表来跟踪节点是否已成为根节点。当遍历根节点的依赖项以查找下一组根时，rooted 列表中的依赖项表示它之前已经成为根。这意味着图中存在一个循环，将已经 rooted 的节点链接为另一个节点的依赖项。

遍历根节点的依赖项可以简单地跳过，而不是中止。这可以阻止进入循环，并允许算法继续处理其余节点。最后可以生成拓扑顺序节点的局部列表。

在主迭代之后，任何不在 "rooted" 列表中的节点都可以被归类为循环的一部分，因为由于先前在遍历根节点的依赖项时跳过循环，它们是无法访问的。