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

问题描述

我尝试了以下方法:

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

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

有人能举出一个反例，说明这种方法是错误的吗?

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

谢谢.

解决方案

为什么 DFS 不起作用

您不能使用 DFS 来找到最短的圆.我们可以轻松创建一个反例，其中 DFS 线索仅找到最长的圆.让我们看看下图:

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

我们在迭代时有两个后边:

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

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

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

<块引用>

但这也意味着 DFS 最终可能会采取一条漫长而复杂的路线到达实际上非常接近的顶点.

为什么 BFS 不起作用

嗯，这并不完全正确，可以使用 BFS(请参阅下一小节)，但您不能使用公式.取下图:

<前>还没有这张图表的精美图片.每个o"都是一个节点.哦---哦||+-------o---o-------+||o----o----o----o----o

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

<前>5~~~5 ~~~都是后缘||+-------4~~~4-------+||3----2----1----2----3

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

<前>3~~~4||+-------2---3-------+||1----2----3----4~~~~4

因此，您不能使用等级公式.

解决方案

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

I tried the following :

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

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 ?

Thanks.

解决方案

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:

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), therefore we found a circle with length 8
• (D , A), therefore we found a circle with length 8

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:

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:

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

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

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.

Solution

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

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