Lesson 37.1 · Advanced Graph Algorithms
Bridges and Articulation Points (Low-Link)
During DFS, low[u] is the smallest discovery time reachable from u's subtree using at most one back edge. An edge u–v is a bridge when low[v] > disc[u].
16 min
Think of it like this
A road network where you ask: if this one bridge collapsed, would some towns be cut off? A road is critical exactly when the towns beyond it have no other way back.
1.disc and low
Give each node a discovery time when DFS first reaches it. low[u] starts as disc[u]; it takes the minimum of children's low values and of disc[w] for back edges u–w (excluding the edge to the parent).
Bridge: tree edge u → v with low[v] > disc[u]: v's subtree can't reach u or anything above without that edge. Articulation point: a non-root u with a child v where low[v] ≥ disc[u], or the DFS root with two or more children.
Both run in O(V + E) with one DFS (Tarjan). Use them to find single points of failure in networks.
edges = [[0,1],[1,2],[2,0],[1,3]]disc / low(map)
Step 1/4DFS starts at 0: disc = low = 0.
Remember
- low = earliest reachable discovery time.
- Bridge: low[v] > disc[u].
- Articulation: low[v] ≥ disc[u] (root: ≥ 2 children).
Common mistakes
- Using the parent edge as a back edge (every edge would look non-bridge).
- Recursion depth on 10⁵-node paths (use an iterative DFS or a bigger stack).
Words used in this lesson
- Bridge
- An edge whose removal disconnects the graph.
- Articulation point
- A node whose removal disconnects the graph.
- Low-link
- The smallest discovery time reachable from a subtree with one back edge.