Bridge determination in undirected graphs

Question

I need to determine all critical edges in an undirected graph, in O(V+E) time. From what I found out, I need to use a modified DF search, but all pseudo-code algorithms I found have low[v] and d[v] which I don't understand. Can someone please explain to me the O(V+E) bridge determination algorithm?

Answer 1

I'll keep the discussion deliberately informal. Feel free to ask if you believe that some claim does not hold or needs more details. I hope I'm not coming out too loquacious. If I do, I'll condense the novel somewhat...

Basics

The algorithm consists of a series of DFS traversals while maintaining state on the graph's vertices. Repeatedly, a start vertex is chosen that the algorithm has not visited before, and a DFS is started from this node. Let v be some node encountered during this DFS. Let the 'partial DFS rooted in v' be the part of the DFS traversal beginning with the first visit and ending with the last visit to v. A 'visit' to some node mandates that the last edge traversed has been a tree edge. A 'visit' to some edge means its first traversal in the course of the DFS.

Two basic observations:

1. there will be exactly k DFS searches, where k is the number of connected components.

2. in DFS on undirected graphs there are only tree and backward edges, but no forward or cross edges.

In undirected graphs, all edges incident to a vertex are 'out' edges, ie. traversable in a DFS. Thus at any time in a DFS search in connected component #i, any vertex encountered has either never been visited at all or is located on the current DFS tree path. The edge across which the DFS reaches said vertex is therefore a tree edge or back edge, resp., but can never be a forward or cross edge.

Information set

The algorithm maintains the following information on vertices. First of all, let the vertex state be one of three categories:

• unseen: the vertex has not yet been visited.
• active: the vertex has been visited, as have been at least one but not all of its incident edges.
• done: the vertex and all its incident edges have been visited. The vertex will never be visited again.

The definitions imply that each vertex changes its state from unseen over active to done in the course of the algorithm. Maintain two more aspects of a processing state on vertices:

• depth: the tree path distance of the vertex from the current DFS root.
• minseen: the minimum vertex 'depth' encountered during the partial DFS rooted in a vertex.

depth and minseen will be undefined for vertices in state unseen. when turning active, the depth of the vertex shall be set and never again changed. minseen will be set to depth and potentially changes while this vertex remains active. After entering state done, the vertex sees no more change of its minseen attribute.

minseen is updated according the following rule.

When backtracking from w to v (i.e. returning from node w to v after the partial DFS search rooted in w has finished), v.minseen is set to the lesser value of v.minseen and w.minseen, i.e. to the closest distance between any node visited during v's partial DFS so far.

Bridge detection

If e=(u,v) is a bridge in the current DFS, the partial DFS rooted at v at no time reaches a vertex closer to the DFS root than u. Therefore, when leaving v for the last time immediately after its state change from active to done, the minseen attribute of the node will equal depth. Due to the state change we know that neither of the values will ever change again. Thus e is a bridge.

Switching perspective, if at any time during the partial DFS rooted at v an active node z has been encountered on the tree path between the root of the current DFS and u (its depth value thus being less than u's and v's), z.depth will percolate back to v in the course of the DFS defining an upper limit to the ultimate value of v.minseen - so it cannot equal v.depth when the DFS leaves v for the last time showing that e is not a bridge.

Complexity

All vertices are inspected once in a predetermined order. When an unseen vertex is encountered, a DFS starts rooted at this vertex. When it ends, this root is marked done and the inspection continues until the next unseen vertex is found and so on.
-> O(V)

Since traversal is standard DFS, each edge is traversed at most twice (twice if it's a tree edge, once otherwise).
-> O(E)

-> O(V+E)

All other steps translate into a constant number of operations.