查找无向图中最短周期的长度 [英] Finding length of shortest cycle in undirected graph

问题描述

我尝试了以下内容：

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

1) DFS, keeping track of level of each vertex in my DFS tree

2）每次看到后边缘（x，y）时，我计算周期长度= level [x] - level [y] + 1，如果它小于最短的

2) Each time a back edge (x,y) is seen, I calculate cycle length = level[x] - level[y] + 1, and save it if it is smaller than the shortest

有人可以告诉一个这个方法是错误的对照示例吗？

Can someone tell a counter example for which this approach is wrong ?

什么可以是一个更好的方式找到无向的最短周期图形？

What could be a better way to find shortest cycle in undirected graphs ?

谢谢。

推荐答案

为什么DFS不工作

你不能使用DFS找到最短的圈子。我们可以轻松创建一个计数器示例，其中DFS线程只找到最长的圆圈。让我们看看下面的图表：

Why DFS won't work

You cannot use DFS to find a shortest circle. We can easily create a counter example, where DFS leads finds only the longest circle. Lets have a look at the following graph:

的图表

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

As you can see we have nine nodes. If we start at the leftmost node A, the following DFS level could be possible:

我们在迭代时有两个后边缘：

We have two back edges while iterating:

c $（c，c）（B，A），因此我们发现一个长度为8的圈子

• A），因此我们找到了一个长度为8的圈子。

• (B , A), therefore we found a circle with length 8
• (D , A), therefore we found a circle with length 8

然而，最短的圆圈长度为5。在下一张照片中显示为蓝色，而其中一个已找到的圈子显示为红色：

However, the shortest circle has length 5. It's shown in blue in the next picture, whereas one of the previously found circles is shown in red:

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

You didn't see the blue circle because your DFS path doesn't contain it. Dagupa et al also mention this behaviour in their book:

但这也意味着DFS可能会花费很长时间

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（见下一节），但是你不能使用你的公式。采取以下图表：

Why BFS won't work

Well, that's not entirely true, one can use BFS (see next subsection), but you cannot use your formula. Take the following graph:

No fancy picture for this graph yet.

Every "o" is a node.

        o---o
        |   |
+-------o---o-------+
|                   |
o----o----o----o----o

让我们看看BFS是可以实现的。如果我从中间的节点开始，我得到以下级别：

Lets see what levels are possible in BFS. If I start at the node in the middle, I get the following levels:

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

如果我从左侧节点开始，我得到以下级别：

And if I start at the left node, I get the following levels:

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

所以你不能使用你的级别公式。

Therefore, you cannot use your level formula.

一旦遇到后边缘，将两个根节点路径连接到它们相交的第一个节点。这是你的圈子这具有O（2 | V |）的最大复杂度，因此该算法具有O（（| V | + | E |）| V |）

As soon as you encounter a back edge, take both root-node paths up to the first node where they intersect. This is your circle. This has maximum complexity of O(2|V|), therefore this algorithm has O((|V|+|E|)|V|)

尽管效率不高，但使用全对最短路径算法并检查每个节点的距离（i，i）是一个有效的解决方案。

Although not efficient, using an all-pair shortest path algorithm and checking the distance (i,i) for every node is a valid solution.

这篇关于查找无向图中最短周期的长度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！