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

Question

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

1. 保留拓扑顺序(即，对于所有边 u->v，v 出现在列表中比 u) 和
2. 列表的长度是最小的。

这个问题有名字吗？

例子

下图的可能排序是

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

另一种解决方案是

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

Answer 1

考虑规范 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 集合的列表包含结果。