gpt4 book ai didi

algorithm - 从每个节点中找到最高可达的节点

转载 作者:行者123 更新时间:2023-12-04 10:27:12 26 4
gpt4 key购买 nike

我有一个有向图 G(V,E)。 G 可能包含循环。每个 v 以值 n[v] 开头。让我们将 G 中 v 可达的所有顶点称为 S{v}。对于每个 v,我需要用 max(n[u]), u∈S{v} 更新 n[v]。

我试过使用 带路径压缩的 Quick-Union ,但我不能,因为 G 是有向图。

一个选项是在每个节点上使用 DFS,但在最坏的情况下复杂性将是 O(V(V+E))。

有没有更好的方法来处理它(可能使用拓扑排序、传递归约或强连接组件)?

最佳答案

是的,有更好的方法 O(V+E):

  • 找到所有强连通分量(Kadane 或 Tarjan 算法)并保存 max_n[v]对于组件中的每个顶点
  • 用强连通分量构建一个新图
  • 新图是 DAG
  • 使用 DP 计算每个组件所需的值(对于 DAG,它要么使用 DFS 自上而下,要么使用 Kahn 自下而上)
  • 关于algorithm - 从每个节点中找到最高可达的节点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/60585206/

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