有向无环图的拓扑排序 [英] Topological sorting of a directed acyclic graph into stages

问题描述

有没有一种算法，给定一个未加权的有向无环图，它将所有节点分类到节点集列表中，这样

Is there an algorithm that, given an unweighted directed acyclic graph, sorts all nodes into a list of sets of nodes such that

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

1. the topological order is preserved (i.e., for all edges u->v, v occurs in a set further down the list than u) and
2. the length of the list is minimal.

这个问题有名字吗?

下面的图形可能是

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

一种替代解决方案是

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

推荐答案

考虑标准Kahn算法的这种变化形式:

Consider this variation of the canonical Kahn's algorithm:

1. 从集合S0开始，该集合包含所有没有传入边的节点
2. 初始化下一组Sn + 1
3. 对每个节点N遍历Sn:

1. 对于从N入边的所有节点D，删除边
2. 如果D没有其他入局边，请将其添加到Sn + 1

如果Sn + 1不为空，则将传递增加到n + 1并从2开始重复.

If Sn+1 is not empty, increase pass to n+1 and repeat from 2.

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

The list of S0 ... Sk sets contains the result.

这篇关于有向无环图的拓扑排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！