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

Question

我尝试了以下方法:

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

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

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

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

谢谢。

Answer 1

为什么 DFS 不起作用

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

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

迭代时我们有两个后边:

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

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

您没有看到蓝色圆圈，因为您的 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) 是一个有效的解决方案。