Bridges and Articulation Points
In a connected undirected graph, a bridge (a.k.a. cut edge) is an edge whose removal disconnects the graph; an articulation point (a.k.a. cut vertex) is a vertex whose removal (along with its incident edges) disconnects the graph. Both are computed in a single DFS in
O(V + E)time using two per-vertex labels:disc[u](discovery time) andlow[u](lowest discovery time reachable fromu’s subtree via at most one back edge). The conditions are crisp —(u, v)is a bridge ifflow[v] > disc[u], anduis an articulation point iffuis the DFS root with ≥ 2 children ORuis non-root and has a childvwithlow[v] >= disc[u]. The same DFS framework yields biconnected components (maximal subgraphs without articulation points), which underpin network reliability analysis, planar graph algorithms, and chip-design routing.
1. Intuition — Single Points of Failure in a Network
Imagine a road network connecting villages. Some roads are duplicated by alternate routes; others are the only way to get from one half of the country to the other. A road that, if closed, splits the country into disconnected pieces is a bridge. A village that, if quarantined, cuts the country in two is an articulation point.
For network-engineering parallels: in a computer network, a bridge is a link whose failure partitions the network; an articulation point is a router whose failure does the same. Identifying these “single points of failure” is the first step in reliability analysis — you either add redundancy at those locations or pre-plan workarounds.
The algorithmic insight (Tarjan, 1972): during DFS, a non-tree edge in an undirected graph is always a back edge to an ancestor (there are no cross or forward edges in undirected DFS — see Depth-First Search §6 for the directed-graph classification). A back edge from a descendant of v over (u, v) provides an “alternate route” that bypasses the tree edge (u, v). So (u, v) is a bridge iff no such back edge exists — i.e., the deepest discovery time reachable from v’s subtree is still later than u’s discovery time. That’s the inequality low[v] > disc[u].
The same low/disc trick handles articulation points with one extra special case for the DFS root.
2. Tiny Worked Example
Vertices 0..6, undirected edges:
0 — 1, 1 — 2, 2 — 0, (triangle)
2 — 3, (single connector)
3 — 4, 4 — 5, 5 — 3, (triangle)
3 — 6 (pendant)
Picture:
0 ——— 1 4
\ / / \
\/ / \
2 ——————— 3 —————————5
|
6
Tree-by-eye:
- Removing edge 2–3 disconnects {0,1,2} from {3,4,5,6}. Bridge.
- Removing edge 3–6 disconnects 6. Bridge.
- Removing edge 0–1, 1–2, 2–0: each is in a triangle, and the other two still connect the same vertices. Not bridges.
- Removing edge 3–4, 4–5, 5–3: same logic. Not bridges.
Articulation points:
- Removing vertex 2: 0 and 1 are connected via 0–1 directly, so {0,1} stays connected; but {3,4,5,6} loses its only connection to {0,1} via 2. Disconnects. Articulation point.
- Removing vertex 3: {0,1,2} disconnects from {4,5} and from {6}. Articulation point.
- Removing vertex 0, 1, 4, 5, 6: graph stays connected (verify by hand). Not articulation points.
The algorithm in §3–§4 will derive both lists in one DFS.
3. The Two Per-Vertex Labels
For DFS starting at any vertex of a connected component:
disc[u]= discovery time ofu— counter incremented every time DFS enters a new vertex. Equivalent to “u was the k-th vertex visited.”low[u]= the minimum of:disc[u]itself, anddisc[w]for everywreachable fromu’s DFS subtree via at most one back edge.
Equivalently and more usefully: low[u] = min(disc[u], min over back edges (u→w) of disc[w], min over tree children v of low[v]).
Computing low[u] is a post-order task: only after every child v has finished (and its low[v] is known) can we finalize low[u]. That’s why the algorithm fits naturally inside the recursive return path of DFS.
4. Bridge-Finding Algorithm
4.1 Pseudocode
find_bridges(graph): # graph: undirected adjacency list
counter := 0
disc := array, all -1
low := array, all -1
bridges := empty list
for each u in V:
if disc[u] == -1:
dfs(u, parent = -1)
return bridges
dfs(u, parent):
disc[u] := counter; low[u] := counter; counter += 1
for each v in graph[u]:
if disc[v] == -1: # tree edge
dfs(v, u)
low[u] := min(low[u], low[v])
if low[v] > disc[u]: # bridge condition
bridges.append((u, v))
else if v != parent: # back edge (skip the edge we came from)
low[u] := min(low[u], disc[v])
4.2 Why the Condition low[v] > disc[u] Is Correct
(u, v) is a tree edge with u the parent. After dfs(v) returns, low[v] is the lowest discovery time reachable from v’s subtree using zero-or-more tree edges followed by at most one back edge. Two cases:
low[v] ≤ disc[u]: some descendant ofvhas a back edge touitself or to a strict ancestor ofu. Removing(u, v)still leaves an alternate route through that back edge. Not a bridge.low[v] > disc[u]: no back edge fromv’s subtree reachesuor above. Removing(u, v)strandsv’s entire subtree. Bridge.
This is necessary and sufficient. (Note: the strict > matters; equality low[v] == disc[u] means a back edge reaches u itself, which is alternate route enough.)
4.3 Trace on the §2 Example
Start DFS at 0; counter = 0.
| Visit | disc | low after subtree | Edge classification | Bridge? |
|---|---|---|---|---|
| 0 | 0 | 0 | root | — |
| 1 (from 0) | 1 | 0 | tree | low[1]=0 ≤ disc[0]=0 → not bridge |
| 2 (from 1) | 2 | 0 | tree | low[2]=0 ≤ disc[1]=1 → not bridge |
| 2→0 | back (v != parent=1) → low[2] = min(2, disc[0]=0) = 0 | |||
| 3 (from 2) | 3 | 3 | tree | low[3]=3 > disc[2]=2 → BRIDGE 2-3 |
| 4 (from 3) | 4 | 3 | tree | low[4]=3 ≤ disc[3]=3 → not bridge |
| 5 (from 4) | 5 | 3 | tree | low[5]=3 ≤ disc[4]=4 → not bridge |
| 5→3 | back → low[5] = min(5, disc[3]=3) = 3 | |||
| 6 (from 3) | 6 | 6 | tree | low[6]=6 > disc[3]=3 → BRIDGE 3-6 |
Bridges: {(2,3), (3,6)}. ✓ Matches our by-eye answer.
4.4 Python Implementation
import sys
def find_bridges(graph: dict[int, list[int]], n: int) -> list[tuple[int, int]]:
"""
graph: undirected adjacency list, vertex -> list of neighbors (each edge appears twice).
n: number of vertices, 0..n-1.
"""
sys.setrecursionlimit(max(10**6, n + 100))
disc = [-1] * n
low = [-1] * n
bridges: list[tuple[int, int]] = []
counter = [0]
def dfs(u: int, parent: int) -> None:
disc[u] = low[u] = counter[0]; counter[0] += 1
for v in graph.get(u, []):
if disc[v] == -1: # tree edge
dfs(v, u)
low[u] = min(low[u], low[v])
if low[v] > disc[u]:
bridges.append((u, v))
elif v != parent: # back edge (skip parent edge)
low[u] = min(low[u], disc[v])
for u in range(n):
if disc[u] == -1:
dfs(u, -1)
return bridges4.5 Handling Multi-Edges (Parallel Edges)
The simple v != parent check misidentifies the parent edge when there are multiple edges between u and parent. If the graph has parallel edges, track the edge index you traversed instead of the parent vertex:
def dfs(u: int, parent_edge_id: int) -> None:
disc[u] = low[u] = counter[0]; counter[0] += 1
for v, edge_id in graph[u]:
if edge_id == parent_edge_id: continue
if disc[v] == -1:
dfs(v, edge_id)
...This matters for graphs that genuinely have parallel edges (like the LeetCode 1192 input format, which doesn’t have them, but real network graphs do). With parallel edges, an edge is a bridge iff no other parallel edge connects the same pair, in which case low[v] > disc[u] no longer detects the redundancy correctly without the edge-id fix.
5. Articulation-Point Algorithm
5.1 Pseudocode
find_articulation_points(graph):
counter := 0
disc := array, all -1
low := array, all -1
is_ap := array, all false
for each u in V:
if disc[u] == -1:
dfs(u, parent = -1, is_root = true)
return [u for u in V if is_ap[u]]
dfs(u, parent, is_root):
disc[u] := counter; low[u] := counter; counter += 1
children := 0
for each v in graph[u]:
if disc[v] == -1:
children += 1
dfs(v, u, false)
low[u] := min(low[u], low[v])
if not is_root and low[v] >= disc[u]: # non-root AP rule
is_ap[u] := true
else if v != parent:
low[u] := min(low[u], disc[v])
if is_root and children >= 2: # root AP rule
is_ap[u] := true
5.2 Why the Two Rules Are Necessary
Non-root rule (low[v] >= disc[u]). If some child subtree of u has no back edge bypassing u, then removing u disconnects that subtree from the rest of the DFS tree. The condition low[v] >= disc[u] says “the deepest reachable ancestor from v’s subtree is u itself or below” — u is the choke point. Note >= here, not >: equality is fine (means back edge to u exactly), and it still requires u to stay in the graph for the connection to exist; remove u and the subtree is stranded.
Root rule (children >= 2). The root has no parent, so the non-root rule never applies. But the root is an articulation point iff its DFS tree has ≥ 2 children — because removing the root disconnects those children’s subtrees from each other (they can’t reach each other through any back edge, since back edges only go to ancestors, and there are none above the root).
If the root has exactly 1 child, removing the root just leaves that one subtree, which is still connected. Not an articulation point.
5.3 The Subtle > vs >= Difference
This is the most asked follow-up question:
- Bridges: strict
>, because we’re asking about a single edge’s removal — even one back edge touprovides redundancy. - Articulation points (non-root): weak
>=, because we’re asking about a vertex’s removal — a back edge touis not redundancy if we’re removingu.
Memorize this. Mixing them up is the most common bug.
5.4 Python Implementation
def find_articulation_points(graph: dict[int, list[int]], n: int) -> list[int]:
sys.setrecursionlimit(max(10**6, n + 100))
disc = [-1] * n
low = [-1] * n
is_ap = [False] * n
counter = [0]
def dfs(u: int, parent: int) -> None:
disc[u] = low[u] = counter[0]; counter[0] += 1
children = 0
for v in graph.get(u, []):
if disc[v] == -1:
children += 1
dfs(v, u)
low[u] = min(low[u], low[v])
if parent != -1 and low[v] >= disc[u]:
is_ap[u] = True
elif v != parent:
low[u] = min(low[u], disc[v])
if parent == -1 and children >= 2:
is_ap[u] = True
for u in range(n):
if disc[u] == -1:
dfs(u, -1)
return [u for u in range(n) if is_ap[u]]5.5 Trace on the §2 Example
Start at 0. After the same DFS as §4.3:
- Vertex 2: child 3 has
low[3]=3 >= disc[2]=2→ 2 is AP. ✓ - Vertex 3: children 4 and 6.
low[4]=3 >= disc[3]=3→ 3 is AP. ✓ (Alsolow[6]=6 >= disc[3]=3confirms.) - Vertex 0 (root): only one DFS child (1) → not AP. ✓
Articulation points: {2, 3}. Matches.
6. Complexity
For both algorithms:
- Time:
O(V + E). One DFS, each edge examined twice (once from each endpoint in the undirected adjacency list). - Space:
O(V)fordisc,low, recursion stack (or work stack if iterative).
The O(V + E) is asymptotically tight: identifying bridges/APs requires inspecting every edge to know whether it provides redundancy.
7. Biconnected Components
7.1 Definition
A graph is 2-vertex-connected (or biconnected) if it has no articulation points. A biconnected component (BCC) is a maximal biconnected subgraph. Equivalently: BCCs are the equivalence classes of edges under the relation “edges e and f lie on a common simple cycle, or e == f.”
Note about isolated edges
An isolated edge (one whose removal disconnects an endpoint) — i.e., a bridge — is its own BCC of two vertices and one edge. Wikipedia and CLRS agree on this convention; some textbooks differ. Verify the convention used in your problem.
7.2 Why BCCs Matter
Within a BCC, any two vertices have at least two vertex-disjoint paths between them (Menger’s theorem applied to 2-connectivity). That makes BCCs the natural “redundant” subnetworks: a packet within a BCC can always reroute around any single vertex failure.
The block-cut tree is built by representing each BCC and each articulation point as a node; an edge connects an AP to each BCC containing it. The block-cut tree is always a tree (proof: any cycle in the block-cut tree would correspond to a cycle of articulation points + BCCs, contradicting BCC maximality). The block-cut tree is the macroscopic skeleton of the graph’s 2-connectivity structure, analogous to how the condensation is the skeleton of a directed graph’s strong connectivity.
7.3 Algorithm
Modify the AP DFS to maintain a stack of edges. When low[v] >= disc[u] (non-root AP condition) or when DFS finishes the root, pop edges from the stack until the edge (u, v) is popped — those edges form one BCC.
def find_bccs(graph: dict[int, list[int]], n: int) -> list[list[tuple[int, int]]]:
disc = [-1] * n; low = [-1] * n
counter = [0]; edge_stack: list[tuple[int, int]] = []
bccs: list[list[tuple[int, int]]] = []
def dfs(u: int, parent: int) -> None:
disc[u] = low[u] = counter[0]; counter[0] += 1
for v in graph.get(u, []):
if v == parent: continue
if disc[v] == -1:
edge_stack.append((u, v))
dfs(v, u)
low[u] = min(low[u], low[v])
if low[v] >= disc[u]: # u is AP wrt this child (also handles root)
bcc = []
while edge_stack and edge_stack[-1] != (u, v):
bcc.append(edge_stack.pop())
bcc.append(edge_stack.pop()) # the (u, v) edge itself
bccs.append(bcc)
elif disc[v] < disc[u]: # back edge (avoid double-counting)
edge_stack.append((u, v))
low[u] = min(low[u], disc[v])
for u in range(n):
if disc[u] == -1:
dfs(u, -1)
return bccsThe disc[v] < disc[u] check (instead of v != parent) prevents pushing an undirected edge twice onto the stack (once from each endpoint). Only push it from the deeper endpoint.
8. Use Cases
8.1 Network Reliability
Telecom carriers, power grids, and computer networks identify bridges and APs to know where redundancy is missing. A bridge is “single link of failure”; an AP is “single node of failure.” Adding a parallel edge or duplicate node at these locations turns 1-connectivity into 2-connectivity.
8.2 Critical Connections (LeetCode 1192)
Direct application: given a server network, find all “critical” connections whose removal increases the number of disconnected clusters. This is the bridge-finding problem.
8.3 Planar Graph Algorithms
Many planar-graph algorithms (e.g., Hopcroft-Tarjan planarity testing) decompose into BCCs first because biconnected planar graphs have a unique embedding (up to reflection) by Whitney’s theorem (1932). Reducing to biconnected case simplifies the proof and the algorithm.
8.4 Chip-Layout and PCB Routing
In VLSI and PCB design, the routing graph’s articulation points are critical: a fault at such a node disconnects whole sub-circuits. Designers either reinforce these nodes or reroute around them.
8.5 Social Network Influence Analysis
In a social-network graph, articulation points are “broker” individuals who connect otherwise-disconnected communities. Removing them fragments the network — a useful signal for community detection and influencer identification.
8.6 Fault-Tolerant Routing in Sensor Networks
Wireless sensor networks model the “communication graph” with sensors as vertices. Bridges and APs identify weak points where a single node failure isolates entire regions. The algorithm runs at deployment time to flag topology weaknesses.
8.7 Game Theory and Scheduling
In some scheduling problems where jobs have prerequisite chains, articulation points in the dependency DAG correspond to “bottleneck” jobs whose delay cascades to disjoint downstream branches. (Note: dependency graphs are directed; the bridge/AP definitions here apply to undirected graphs. For directed graphs, see Strongly Connected Components.)
9. Common Interview Problems
| Problem | Pattern |
|---|---|
| LC 1192 — Critical Connections in a Network | Tarjan’s bridge algorithm (this is the canonical example) |
| Classic — “Minimum number of edges to add to make graph 2-edge-connected” | Bridges + counting leaves of bridge-tree |
| Classic — “Find all articulation points” | Tarjan’s AP algorithm |
| Hackererth / Codeforces — “Block-cut tree problems” | BCC decomposition + tree problem on block-cut tree |
| LC 928 — Minimize Malware Spread II | Articulation points within malware-sourced subgraph |
| LC 1568 — Minimum Number of Days to Disconnect Island | Special case: 0, 1, or 2 always suffice; 1 means an articulation cell |
| Classic — “Number of pairs of vertices with no two-disjoint paths” | BCC enumeration |
If a problem mentions “critical edge”, “single point of failure”, “removing X disconnects”, “2-edge-connected”, or “alternate path” — bridges and APs are on the shortlist.
10. Diagram — disc and low in Action
flowchart TD A((A<br/>disc=0<br/>low=0)) --- B((B<br/>disc=1<br/>low=0)) B --- C((C<br/>disc=2<br/>low=0)) A -.back.- C C --- D((D<br/>disc=3<br/>low=3)) D --- E((E<br/>disc=4<br/>low=4))
What this diagram shows. Solid edges (A-B, B-C, C-D, D-E) are tree edges in the DFS spanning tree from root A. The dashed edge (A-C) is a back edge: it lets C reach A directly without going through B, so low[C] = min(disc[C]=2, disc[A]=0) = 0. That value back-propagates to B and A. For tree edge A-B: low[B]=0 ≤ disc[A]=0 → A-B is not a bridge (the back edge A-C provides redundancy). For tree edge B-C: same logic, not a bridge. For tree edge C-D: low[D]=3 > disc[C]=2 → C-D is a bridge. For D-E: low[E]=4 > disc[D]=3 → D-E is a bridge. Articulation points: A is root with 1 child (B), so not an AP. B is non-root, child C has low[C]=0 < disc[B]=1, so not an AP. C is non-root, child D has low[D]=3 >= disc[C]=2, so C is an AP. D is non-root, child E has low[E]=4 >= disc[D]=3, so D is an AP.
11. Pitfalls
11.1 Confusing > and >=
The most-bug-causing detail in this algorithm. Bridge condition is strict >; AP non-root condition is weak >=. They look almost identical and they are not interchangeable. Re-derive from §4.2 and §5.2 if you forget which is which.
11.2 Forgetting the Root Special Case
The root has no parent, so the standard non-root rule (low[v] >= disc[u]) doesn’t apply. The root is an AP iff it has ≥ 2 DFS-tree children. Forgetting this rule will miss root APs entirely or, worse, wrongly mark root-with-one-child as an AP if you naively apply the non-root rule.
11.3 The Parent Edge in Undirected Graphs
In undirected DFS, when at u examining edge to v, you must distinguish “this is the edge back to my parent” from “this is a genuine back edge.” The simple v != parent check works iff the graph has no parallel edges. With parallel edges, track edge IDs (see §4.5).
11.4 Disconnected Graphs
Bridges and APs are defined in the context of “removal disconnects this connected component”. If the input graph has multiple connected components, run the DFS from a vertex in each component (the outer for u in V: if disc[u] == -1: ... loop). The bridges and APs of each component are computed independently.
11.5 Self-Loops
A self-loop (u, u) is never a bridge (removing it doesn’t change connectivity) and u doesn’t become an articulation point because of it. The simple v != parent check accidentally treats self-loops as back edges; this is harmless for AP/bridge detection (it just sets low[u] = min(low[u], disc[u]) which is a no-op), but be aware.
11.6 Recursion Depth
For long-chain graphs (e.g., 10^5 vertices in a path), Python’s default recursion limit (1000) blows up. Either sys.setrecursionlimit(N) (with N safely above the chain length) or rewrite as iterative DFS with an explicit work stack. The recursive version is far more readable; only switch when forced.
11.7 Missing Back Edges Inside the Adjacency Twice
In an undirected adjacency list, edge (u, v) typically appears in both graph[u] and graph[v]. The DFS sees it twice — once when at u, once when at v. This is fine for AP/bridge detection (the duplicates don’t change the low values), but in BCC code (§7.3), pushing the edge twice onto the stack double-counts. The fix is the disc[v] < disc[u] check.
11.8 Treating “Articulation Point” and “Bridge Endpoint” as Identical
Easy intuition trap: surely the endpoints of every bridge are articulation points? Not always. If (u, v) is a bridge and v has degree 1 (a leaf), then removing v doesn’t disconnect anything new — v was already an endpoint with no other connections. So v is not an AP even though (u, v) is a bridge. The endpoint with non-trivial structure on its side is an AP; the leaf endpoint is not.
11.9 Non-Tree Edges Are Always Back Edges (Undirected)
For undirected graphs, the only non-tree edges DFS produces are back edges. Confusing forward edges or cross edges (which don’t exist in undirected DFS) with back edges leads to spurious updates. The classification is much simpler than the directed case (see Depth-First Search §6).
12. Open Questions
- What’s the best fully dynamic algorithm for maintaining bridges under edge insertions/deletions? Holm-Lichtenberg-Thorup (2001) achieved
O(log^2 n)amortized; recent work has improved this — verify. - Is there a parallel
O(log V)-depth bridge-finding algorithm? Tarjan-Vishkin (1985) gaveO(log V)PRAM withO(V + E)work; rarely implemented in practice.
13. See Also
- Depth-First Search — foundation of the algorithm;
disc/lowframework - Strongly Connected Components — Tarjan’s analogous single-DFS algorithm for directed graphs
- Connected Components — the simpler “is the graph connected?” precursor
- Union-Find — alternative for some 2-edge-connectivity questions in batch settings
- Graph Representations — adjacency-list is the natural representation for these algorithms
- Big-O Notation
- SWE Interview Preparation MOC