~/home/bridges & articulation points: the weak links
Algorithms · Graphs
The Weak Links.
Which single connection, if it failed, would split a network in two? That edge is a bridge; the analogous vertex is an articulation point. Tarjan finds them all in a single depth-first search using two numbers per node: disc[v], the order it was discovered, and low[v], the earliest-discovered node its subtree can reach by any path. An edge to a child c is a bridge exactly when low[c] > disc[v] — the child’s subtree has no other way back. Step the DFS and watch the two numbers fill and the critical edges light up.
O(V + E) — one DFS · disc[v] = discovery order · low[v] = earliest reachable
bridge
An edge whose removal increases the number of disconnected components.
articulation point
A vertex whose removal disconnects the graph.
disc[v]
The step number when the DFS first reached v — its discovery time.
low[v]
The smallest disc reachable from v’s subtree via tree or back edges.
bridges.js — disc, low, and the critical edges
Ready
Two triangles joined by a thin chain. A DFS assigns each node a discovery time disc and a low-link low. An edge to a child is a bridge when the child’s subtree can’t reach back above it. Step the DFS.
–
at node
0/7
visited
0
bridges
How it works
The magic number is low[v]: the earliest-discovered vertex reachable from v’s subtree using tree edges plus at most one “back edge” to an ancestor. A node starts with low[v] = disc[v], then lowers it whenever a back edge or a child’s subtree offers a way to an older ancestor. Now consider the tree edge from v down to a child c: if low[c] > disc[v], the entire subtree under c can reach nothing older than c itself — so that one edge is the only route in or out. Remove it and the subtree falls off: it’s a bridge. (Articulation points use the closely-related test low[c] ≥ disc[v], with a special rule for the DFS root.)
1
DFS and stamp discovery times
Run a depth-first search from any node. The moment you first reach a node, stamp it with the next discovery number and initialize its low-link to the same value.
2
Lower the low-link
When you find a back edge to an already-visited ancestor, or return from a child, update low[v] to the smallest disc your subtree can reach. This records the earliest ancestor still reachable.
3
Test each tree edge
For a tree edge v→c, if low[c] > disc[v], the child’s subtree has no alternative route above v, so v→c is a bridge. (For an articulation point, the test is low[c] ≥ disc[v].)
✓
One pass finds them all
A single DFS computes every disc and low value and identifies all bridges (and articulation points) in O(V + E) — no need to try removing edges one at a time.
Time
O(V + E)
Passes
one DFS
Bridge test
low[c] > disc[v]
Finds
weak links
The code
# Tarjan bridge-finding in one DFS, O(V + E)def dfs(v, parent_edge):
disc[v] = low[v] = time[0]; time[0] += 1
for (u, eid) in adj[v]:
if eid == parent_edge: continueif disc[u] == -1: # tree edge
dfs(u, eid)
low[v] = min(low[v], low[u])
if low[u] > disc[v]:
bridges.append((v, u)) # v-u is a bridgeelse: # back edge
low[v] = min(low[v], disc[u])
Quick check
1. What is a bridge in a graph?
A bridge is a critical edge: removing it splits the graph into more components. An edge inside a cycle is never a bridge, because the cycle provides an alternate route.
2. What does low[v] represent?
low[v] is the earliest-discovered vertex the subtree rooted at v can reach, using tree edges and at most one back edge to an ancestor. It measures how far “back up” the subtree can escape.
3. When is the tree edge v→c a bridge?
If low[c] > disc[v], nothing in c’s subtree can reach v or an older ancestor except through this edge — so it’s the only route in or out, and removing it disconnects the subtree. That is exactly a bridge.
FAQ
What are bridges and articulation points?
In an undirected graph, a bridge is an edge whose removal disconnects the graph, and an articulation point (cut vertex) is a vertex whose removal does. They identify the single points of failure — the links and hubs whose loss splits the network.
How does Tarjan’s algorithm find them in one DFS?
A DFS stamps each node with a discovery time disc[v] and a low-link low[v] (earliest node reachable from its subtree). A tree edge v→c is a bridge when low[c] > disc[v]; a non-root v is an articulation point when a child has low[c] ≥ disc[v]; the root is one if it has 2+ DFS children. All in O(V + E).
Why is low[v] compared with disc, not low, in the bridge test?
A back edge lowers low[v] using the ancestor’s disc (the node you actually reach), not its low. The test low[c] > disc[v] then asks whether c’s subtree can reach v or anything older; if it can’t, the connecting edge is the sole crossing — a bridge.
What are bridges and articulation points used for?
Network reliability and single-point-of-failure analysis (communication, power, transport), finding critical roads/links, decomposing graphs into biconnected components, and as a subroutine in other graph algorithms — answering “what weakest link, if lost, breaks connectivity?”