gpt4 book ai didi

algorithm - 如何找到有向图中2个特定顶点之间所有可能路径中存在的顶点?

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:23:44 26 4
gpt4 key购买 nike

如何在有向图中的 2 个特定顶点之间的所有可能路径中找到公共(public)顶点?至少存在一条路由是先决条件。

最佳答案

O(|V||E|) 解决方案。 AB - 路线的终点。

  1. 遍历所有顶点。
  2. 从图中删除顶点。
  3. 检查是否存在从AB 的路径(即使用 DFS)
  4. 如果路径不存在 - 顶点对所有路径都是公共(public)的。

关于algorithm - 如何找到有向图中2个特定顶点之间所有可能路径中存在的顶点?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22716131/

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