我需要在O（V + E）的时间内确定无向图中的所有关键边。从我发现的结果来看，我需要使用修改后的DF搜索，但是我发现的所有伪代码算法都有我不理解的low [v]和d [v]。有人可以向我解释O（V + E）桥梁确定算法吗？
我将使讨论故意保持非正式。随意询问您是否认为某些主张不成立或需要更多详细信息。我希望我不会太客气。如果可以，我会把这本小说浓缩一下...
该算法由一系列DFS遍历组成，同时保持图形顶点的状态。重复地，选择算法从未访问过的起始顶点，然后从该节点开始DFS。令v是此DFS期间遇到的某个节点。让“从v植根的部分DFS”成为DFS遍历的一部分，从第一次访问到最后一次访问v结束。对某些节点的“访问”要求所遍历的最后一条边是树边。 “访问”到某个边缘意味着它在DFS的过程中第一次遍历。
两个基本观察：
1。将完全有k个DFS搜索，其中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到v的回溯（即，以w为根的部分DFS搜索完成后，从节点v返回到w），v.minseen被设置为较小的值v.minseen ]和w.minseen，即到目前为止v的部分DFS期间访问的任何节点之间的最近距离。
如果e=(u,v)是当前DFS中的桥，则以v为根的部分DFS不会比u更接近DFS根。因此，当状态从v更改为active后立即离开done时，节点的minseen属性将等于depth。由于状态更改，我们知道两个值都不会再次更改。因此，e是一个桥梁。
切换角度，如果在以v为根的部分DFS的任何时候，在当前DFS的根和active之间的树路径（其z值）上都遇到了u节点depth因此小于u和v的值，z.depth将在DFS的过程中渗透回v，从而定义v.minseen最终值的上限-因此它不能等于DFS最后一次离开v.depth时显示v不是网桥时的e。
以预定顺序检查所有顶点一次。遇到unseen顶点时，DFS从该顶点开始生根。结束时，将此根标记为done，然后继续检查直到找到下一个unseen顶点，依此类推。-> O(V)
由于遍历是标准DFS，因此每个边缘最多可遍历两次（如果是树边缘则两次遍历，否则遍历两次）。-> O(E)
-> O(V+E)
所有其他步骤都转换为恒定数量的操作。