有向无环图的拓扑排序为阶段

Question

是否有一种算法，给定一个未加权的有向无环图，将所有节点排序到一组节点列表中，使得

1. 保留拓扑顺序（即，对于所有边 u->v，v 出现在比 u 更靠后的集合中）和
2. 列表的长度是最小的。

这个问题有名字吗？

例子

下图的可能排序是

[1], [2, 3], [4, 5], [6, 7]

另一种解决方案是

[1], [2, 3], [4], [5, 6, 7]

Answer 1

将每个节点的阶段索引定义为零，如果它没有前任，或者一加其前任的最大阶段索引。将每个节点置于指示的阶段。

可以按拓扑顺序高效地评估阶段索引，这使其成为您最喜欢的拓扑排序算法的简单扩展。

Answer 2

考虑规范 Kahn 算法的这种变体：

1. 从包含所有节点的集合 S0 开始，没有传入边
2. 初始化下一组Sn+1
3. 遍历 Sn，对于每个节点 N:
1. 对于所有具有来自N的传入边的节点D，移除边
2. 如果D没有其他入边将其加入Sn+1
4. 如果Sn+1不为空，增加pass到n+1，从2开始重复。

S0 ... Sk 集合的列表包含结果。