无向图中的桥确定

Question

我需要在O(V + E)时间内确定无向图中的所有关键边.根据我的发现,我需要使用修改后的DF搜索,但我找到的所有伪代码算法都有低[v]和d [v],我不明白.有人可以向我解释O(V + E)桥确定算法吗？

Answer 1

我将故意非正式地讨论.如果您认为某些声明不成立或需要更多细节,请随时询问.我希望我不会太过于喋喋不休.如果我这样做,我会在某种程度上浓缩这部小说......

基本

该算法由一系列dfs遍历组成,同时保持图形顶点的状态.重复地,选择之前未访问算法的起始顶点,并从该节点开始dfs.让v这个节点在这个dfs期间被包围.让'部分dfs根源v'成为dfs遍历的一部分,从第一次访问开始到最后一次访问结束v.对某个节点的"访问"要求最后一个遍历的边缘是树边缘.对某些边缘的"访问"意味着它在dfs过程中的第一次遍历.

2基本观察:

1.将有精确的kdfs搜索,其中k是连接组件的数量.

2.在无向图上的dfs中,只有树和后边,但没有前沿或交叉边.

在无向图中,入射到顶点的所有边都是"向外"边,即.可以在dfs中遍历.因此,在连接组件#i中的dfs搜索中的任何时候,遇到的任何顶点都从未被访问过或者位于当前的dfs树路径上.因此,dfs到达所述顶点的边缘是树边缘或后边缘,但是永远不能是前沿或交叉边缘.

信息集

该算法在顶点上保留以下信息.首先,让顶点状态为3类之一:

• unseen:顶点尚未访问过.
• active:访问过顶点,至少有一个但不是全部的入射边缘.
• done:已访问顶点及其所有事件边缘.永远不会再访问顶点.

定义意味着每个顶点从改变其状态unseen比active对done in the算法的过程.在顶点上维护处理状态的另外两个方面:

• depth:顶点与当前dfs根的树路径距离.
• minseen:在以顶点为根的部分dfs期间遇到的最小顶点"深度".

depth并且minseen对于看不见的状态的顶点将是未定义的.在转弯时active,depth应设置顶点并且不再改变.minseen将depth保留此顶点时将设置为并可能更改active.进入状态后done,顶点看不到其minseen属性的更改.

minseen 根据以下规则更新:

从回溯时w到v(即,从节点返回w到v后部分DFS搜索根植于w已完成),v.minseen被设置为的较小值v.minseen和w.minseen,即.v到目前为止在部分dfs 期间访问的任何节点之间的最近距离.

桥梁检测

如果e=(u,v)是当前dfs中的桥接器,则根植于此的部分dfs v不会到达比dfs根更接近的顶点u.因此,当v状态从改变active到最后一次离开时done,minseen节点的属性将相等depth.由于状态的变化,我们知道这两个值都不会再发生变化.因此e是一座桥梁.

切换角度来看,如果在过程中的根的部分DFS任何时候v一个active节点z已经遇到的当前DFS的根部之间的树路径上u(其depth值因此是小于u的和v的),z.depth将渗透回v在dfs的过程定义了最终值的上限v.minseen- 所以v.depth当dfs离开时v最后一次显示e不是桥接时它不能相等.

复杂

以预定顺序检查所有顶点一次.当unseen遇到顶点时,dfs开始以此顶点为根.当它结束时,标记该根done并继续检查,直到unseen找到下一个顶点,依此类推.
- >O(V)

因为遍历是标准dfs,所以每条边最多遍历两次(如果是树边,则两次,否则一次).
- >O(E)

- > O(V+E)

所有其他步骤都转化为恒定数量的操作.