gpt4 book ai didi

algorithm - 图检查三个节点之间是否存在路径

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:56:37 24 4
gpt4 key购买 nike

问题是我们必须找到从 A 到 C 的路径,该路径经过节点 B 或以下示例图 A-G-F-B-L- C.

现在使用 BFS 很容易实现从 A 到 C,但我不知道如何确保这条路径通过 B?

最佳答案

“路径”可能是指“简单路径”——没有重复顶点的路径。

首先,确保A、B、C已连接。

A-...-B-..-C 路径存在当且仅当:

  • 没有将 A、B 和 C 分成 3 个不同部分的切割顶点
  • A 不是将 B 和 C 分成不同部分的切割顶点
  • C 不是将 B 和 A 分成不同部分的切割顶点

关于algorithm - 图检查三个节点之间是否存在路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44616455/

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