Bridges & Articulation Points
An edge whose removal disconnects the graph is called a bridge. A vertex whose removal disconnects the graph is called an articulation point (or cut vertex). These two concepts are closely related and both solved efficiently using a single DFS framework discovered by Robert Tarjan.
Node B is an articulation point. Edge B-D is a bridge. Removing either disconnects the graph.
What You Will Learn
This series breaks the topic into three focused pages. Each page builds on the previous one and includes interactive step-through animations so you can watch the algorithm execute on real graphs.
1. Bridge Detection (Tarjan's Algorithm)
DFS trees, discovery time and low-link values, the bridge condition (low[v] > disc[u]), complete C++ implementation, two animated walkthroughs on 7-node and 10-node graphs, edge cases including multigraphs.
Read →2. Articulation Points
How the condition changes to low[v] ≥ disc[u], the special root rule, why strict vs non-strict inequality matters, combined bridge and AP detection in a single DFS, animated walkthrough.
Read →3. Applications
Real-world uses: network reliability, biconnected components, 2-edge-connected components, finding critical servers, router failure analysis. Practice problems with solution sketches.
Read →Prerequisites
Comfortable with DFS traversal and adjacency list representation. If not, start with the graph traversal series first.
DFS Refresher →Core Idea in 30 Seconds
Run a single DFS and maintain two arrays:
- disc[v]: When was node v first discovered?
- low[v]: What is the earliest node reachable from v's subtree using back edges?
A tree edge (u, v) where u is v's parent is a bridge if low[v] > disc[u]. This means v's entire subtree has no back edge reaching u or above, so removing (u, v) disconnects the subtree.
A node u is an articulation point if any child v satisfies low[v] ≥ disc[u] (or if u is the DFS root with two or more children).
Why This Matters
Bridges and articulation points appear in network design, circuit analysis, social network analysis, and competitive programming. Some concrete scenarios:
- Network reliability: Identifying single points of failure (a router or link whose failure partitions the network).
- Road networks: Bridges are roads whose closure disconnects towns. City planners need redundancy.
- Social graphs: Articulation points are people whose departure splits a community.
- Competitive programming: Frequently tested in contests (Codeforces, ICPC). Often combined with biconnected component decomposition or block-cut trees.