寻找最短周期的长度无向图 [英] 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）可以看到的，我计算周期长度=水平[X] - 电平[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线索发现只有最长圈。让我们来看看下图：

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:

• （B，A），因此我们发现，长度8
圆
• （D，A），所以我们发现长了一圈8

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

不过，最短圈的长度是5，它显示为蓝色，在未来的画面，而previously发现的一个圈子中以红色显示：

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

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屋！