Bridges and Articulation Points

The idea: find the single points of failure

Think of a graph as a network: routers and cables, power stations and lines, people and friendships. A bridge is an edge whose loss splits the network in two. An articulation point (also called a cut vertex) is a vertex whose loss splits it. These are the single points of failure. Testing each edge and vertex one by one takes O(V·(V + E)). Tarjan showed in 1972 that one depth-first search finds them all in O(V + E).

On the canvas the network is drawn as it is; the DFS colours each edge as it scans it, and the table on the right fills in disc and low for every vertex. Demo 1 runs it on the network above.

Tree edges and back edges

Start a DFS at a root (here A) and scan neighbours in alphabetical order. When an edge leads to a vertex not yet visited, it is a tree edge (green) and the DFS goes down into that vertex. When it leads to a vertex already on the DFS path above, it is a back edge (blue). In an undirected graph there is nothing else: a DFS never leaves an edge to a finished side branch unexplored, so there are no cross edges.

The tree edges form the DFS tree. Every back edge closes a cycle with the tree path between its ends. An edge on a cycle can never be a bridge, because the rest of the cycle is a second route. So the question becomes: which tree edges are not covered by any back edge?

Each edge is seen twice, once from each end. The page skips the edge a vertex was entered by (its parent edge), and the second sighting of a back edge from the ancestor's side.

Discovery time and low-link

The discovery time disc[v] is 1 for the root, 2 for the next vertex reached, and so on. Ancestors always have smaller times than their descendants. The low-link low[v] is the smallest discovery time that v's whole subtree can reach using tree edges down and then at most one back edge up. It is filled in as the DFS returns:

dfs(u):
    disc[u] = low[u] = ++time
    for each neighbour w of u:
        if edge u–w is the edge u came in by: skip
        if w not visited:                      # tree edge
            dfs(w)
            low[u] = min(low[u], low[w])
            if low[w] >  disc[u]: edge u–w is a BRIDGE
            if low[w] >= disc[u] and u is not the root: u is a CUT VERTEX
        else if disc[w] < disc[u]:             # back edge to an ancestor
            low[u] = min(low[u], disc[w])
root is a CUT VERTEX if it has 2 or more DFS children

On the canvas, when the DFS returns from v to u, a yellow box carries low[v] from v's column into u's column, and the two tests are shown with ✓ or ✗.

The bridge test: low[v] > disc[u]

Let u–v be a tree edge with u the parent. If low[v] > disc[u], nothing in v's subtree has a back edge to u or anything above u. The only connection from that subtree to the rest of the graph is the edge u–v itself, so it is a bridge. In the network, low[D] = 4 > disc[C] = 3: C–D is a bridge. On the other side, low[B] = 1, because C has a back edge to A, so A–B and B–C are safe.

The cut-vertex test: low[v] ≥ disc[u]

A non-root u is a cut vertex when some child v has low[v] ≥ disc[u]. The subtree under v may climb back to u itself, but not above it, so removing u cuts that subtree off. The equality case is the interesting one: in the network, E–F–D is a triangle, so low[E] = 4 = disc[D]. D–E is not a bridge, but D is still a cut vertex. Every bridge end that is not a leaf is a cut vertex: the one bridge C–D in Demo 6 makes both C and D cut vertices. The other way round fails: the bowtie's A is a cut vertex with no bridge at all (Demo 4).

The root needs its own rule, because nothing is above it and low[v] ≥ disc[root] = 1 is always true. The root is a cut vertex exactly when it has two or more DFS children: two subtrees that the DFS could not reach from each other, so they only meet at the root (Demo 4, the bowtie). A tree is the extreme case: there are no back edges, every low equals its own disc, and every edge is a bridge (Demo 5).

Graph	Bridges	Cut vertices
Network (8 vertices)	C–D, F–G, G–H	C, D, F, G
Ring with a chord	none	none
Bowtie	none	A (root, 2 children)
Tree	all 5 edges	A, B, C
Two rings on one edge	C–D	C, D

Checking by brute force

Test Cuts removes each bridge and cut vertex in turn, then one harmless edge and one harmless vertex, and colours the pieces that are left with a plain breadth-first search. Each test costs O(V + E); the DFS needed only one pass for all of them. In Demo 3 nothing splits: a graph with no bridge is 2-edge-connected, and one with no cut vertex (and at least 3 vertices) is biconnected. It survives any single failure.

Where it is used

• Network reliability. Bridges and cut vertices are the links and routers to duplicate first.
• Biconnected components. The same DFS, with a stack of edges, splits a graph into its biconnected blocks, joined at cut vertices (the block-cut tree).
• Other algorithms. Fleury's algorithm for Euler paths avoids crossing a bridge; planarity testing and 2-SAT build on the same low-link idea.

See also Depth-First Search for the plain traversal, Strongly Connected Components (Tarjan) for the same disc / low trick on directed graphs, Kosaraju's algorithm for the two-pass alternative, and Euler paths, where bridges decide which edge Fleury's algorithm may cross.

What the page leaves out

Graphs with several components (run the DFS from every unvisited vertex), parallel edges (skip the parent edge, not the parent vertex, which the page already does), the iterative version that avoids deep recursion on big graphs, the edge stack that outputs biconnected components, and dynamic graphs where edges come and go.

References

Tarjan, Depth-First Search and Linear Graph Algorithms, SIAM J. Computing (1972)

Finding bridges in a graph in O(N + M) (cp-algorithms)

Finding articulation points in a graph in O(N + M) (cp-algorithms)

Biconnected component (Wikipedia): articulation points, low-link, block-cut tree