gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-05 02:42:50 30 4
gpt4 key购买 nike

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

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

这个问题有名字吗?

例子

下图的可能排序是

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

另一种解决方案是

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

enter image description here

最佳答案

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

关于algorithm - 有向无环图的拓扑排序为阶段,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/67265652/

30 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com