gpt4 book ai didi

algorithm - 在无向图中查找最短循环的长度

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

我尝试了以下方法:

1) DFS,跟踪我的 DFS 树中每个顶点的级别

2)每次看到后边(x,y),我计算循环长度= level[x] - level[y] + 1,如果小于最短的就保存

谁能说出这种方法错误的反例?

在无向图中找到最短环路的更好方法是什么?

谢谢。

最佳答案

为什么 DFS 不起作用

您不能使用 DFS 来找到最短的圆。我们可以很容易地创建一个反例,其中 DFS leads 只找到最长的圆。让我们看看下图:

A graph with a "long line"

如您所见,我们有九个节点。如果我们从最左边的节点 A 开始,则可能有以下 DFS 级别:

Resulting depth first search tree

迭代时我们有两个后边:

  • (B , A),因此我们找到了一个长度为8的圆
  • (D , A),因此我们找到了一个长度为8的圆

然而,最短的圆的长度为 5。它在下一张图片中以蓝色显示,而之前找到的一个圆以红色显示:

Long circle vs. short circle

您没有看到蓝色圆圈,因为您的 DFS 路径不包含它。Dagupa 等人在他们的书中也提到了这种行为:

But it also means that DFS can end up taking a long and convoluted route to a vertex that is actually very close by.

为什么 BFS 不起作用

嗯,这不完全正确,可以使用 BFS(请参阅下一节),但您不能使用您的公式。拿下图:

No fancy picture for this graph yet.Every "o" is a node.        o---o        |   |+-------o---o-------+|                   |o----o----o----o----o

让我们看看 BFS 中可能有哪些级别。如果我从中间的节点开始,我会得到以下级别:

        5~~~5            ~~~ are back-edges        |   |+-------4~~~4-------+|                   |3----2----1----2----3

如果我从左侧节点开始,我会得到以下级别:

        3~~~4        |   |+-------2---3-------+|                   |1----2----3----4~~~~4

因此,您不能使用级别公式。

解决方案

虽然效率不高,但使用全对最短路径算法并检查每个节点的距离 (i,i) 是一个有效的解决方案。

关于algorithm - 在无向图中查找最短循环的长度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20847463/

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