1

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

4

1 回答 1

9

我会故意保持非正式的讨论。随意询问您是否认为某些索赔不成立或需要更多详细信息。我希望我不会说得太啰嗦。如果我这样做，我会稍微压缩一下小说......

基本

该算法由一系列 DFS 遍历组成，同时在图的顶点上保持状态。反复地，选择一个算法之前没有访问过的起始顶点，并从这个节点开始一个DFS。假设v是在这个 DFS 期间遇到的某个节点。让“部分 DFS 植根于v”成为 DFS 遍历的一部分，从第一次访问开始，到最后一次访问结束v。对某个节点的“访问”要求遍历的最后一条边是树边。对某个边缘的“访问”意味着它在 DFS 过程中的第一次遍历。

两个基本观察：

1. 会有精确的kDFS 搜索，k连接组件的数量在哪里。

2.在无向图的DFS中，只有树边和后边，没有前边和交叉边。

在无向图中，所有入射到顶点的边都是“外”边，即。可在 DFS 中遍历。因此，在连通分量#i 中的 DFS 搜索中的任何时候，遇到的任何顶点要么根本没有被访问过，要么位于当前的 DFS 树路径上。DFS 到达所述顶点的边因此分别是树边或后边，但永远不能是前边或交叉边。

信息集

该算法维护以下关于顶点的信息。首先，让顶点状态为以下三个类别之一：

  • unseen: 顶点还没有被访问过。
  • active: 顶点已经被访问过，至少有一个但不是所有的入射边都被访问过。
  • done：已访问顶点及其所有入射边。该顶点将永远不会被再次访问。

这些定义暗示每个顶点在算法过程中将其状态从unseen结束active更改为结束done。维护顶点处理状态的另外两个方面：

  • depth：顶点到当前 DFS 根的树路径距离。
  • minseen：在以顶点为根的部分 DFS 期间遇到的最小顶点“深度”。

depth并且minseen对于处于未见状态的顶点是未定义的。转动时active，depth顶点的 将被设置并且不再改变。minseen将被设置为depth并可能在此顶点保留时更改active。进入状态后done，顶点看不到其minseen属性的更多变化。

minseen根据以下规则更新。

w当从to回溯（即在根的部分 DFS 搜索完成v后从节点返回w到）时，设置为 和 的较小值，即设置为到目前为止在 的部分 DFS期间访问的任何节点之间的最近距离。vwv.minseenv.minseenw.minseenv

桥梁检测

如果e=(u,v)是当前 DFS 中的一个桥，则部分 DFSv在任何时候都不会到达比 更接近 DFS 根的顶点u。因此，当节点状态从变为v后立即离开时，该节点的属性将等于。由于状态变化，我们知道这两个值都不会再次改变。因此是一座桥梁。activedoneminseendepthe

切换视角，如果在v以active节点为根的部分 DFS 期间的任何时候z，在当前 DFS 的根和（u其depth值因此小于' us 和DFS 的过程定义了最终值的上限- 所以当 DFS 最后一次离开时它不能相等，表明这不是一座桥。vz.depthvv.minseenv.depthve

复杂

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

由于遍历是标准的 DFS，每条边最多被遍历两次（如果是树边则两次，否则一次）。
->O(E)

->O(V+E)

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

于 2013-04-13T02:10:55.167 回答