有向无圈图的拓扑排序
有向无圈图的拓扑排序
提问于 2021-04-26 11:16:10
是否有一种算法，给定一个无权无环图，将所有节点排序为一组节点，以便
- 保持拓扑顺序(即对于所有边
u->v，v发生在一个比u更远的集合中)，而 - 列表的长度是最小的。
这个问题有名字吗？
示例
下面的图表可能的排序是
[1], [2, 3], [4, 5], [6, 7]另一种解决办法是
[1], [2, 3], [4], [5, 6, 7]
回答 2
Stack Overflow用户
回答已采纳
发布于 2021-04-26 13:29:31
考虑一下正则Kahn算法的这种变化：
从包含所有没有传入edges
- Initialize的节点的集合S0开始，下一集Sn+1
- 在Sn上迭代，对于每个节点N：
- ，对于所有从N输入边缘的节点D，如果D没有其他传入边缘，则删除边缘
- ，将其添加到Sn+1
- If Sn+1不为空，增加传递到n+1，并从2重复。
G 215
S0的名单..。Sk集包含结果。
Stack Overflow用户
发布于 2021-04-26 13:17:20
将每个节点的阶段索引定义为零，如果它没有前辈，或者加上它的前一个节点的最大阶段索引。将每个节点置于指定的阶段。
阶段索引可以有效地按拓扑顺序进行评估，这是对您最喜欢的拓扑排序算法的简单扩展。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/67265652
复制相关文章
相似问题
腾讯云开发者
