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

Question

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

1. 保留拓扑顺序（即，对于所有边

   u->v

   ，

   v

   出现在列表中比

   u

   更靠下的集合中）并且
2. 列表的长度是最小的。

这个问题有名字吗？

示例

下图的可能排序是

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

另一种解决方案是

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

Answer 1

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

1. 从包含所有没有传入边的节点的集合“S_0”开始

从

n = 0:

开始
2. 初始化下一组`S_n+1`
3. 对于 `S_n` 中的每个 `n`：
1. 对于“n”的所有后继“d”，删除边“n -> d”
2. 如果`d`没有其他传入边将其添加到`S_n+1`
4. 如果`S_n+1`不为空，则增加pass到n+1并从2开始重复。

S_0 ... S_k

集合的列表包含结果。

Answer 2

如果每个节点没有前驱，则将其阶段索引定义为零，或者将其前驱的最大阶段索引加一。将每个节点放入指定的阶段。

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