Algorithms / Bridges Articulation
Least You Need to Know: Bridges, Articulation Points, and Fragile Connectivity
Bridges and articulation points identify where an undirected graph is **fragile**. A bridge is an edge whose removal disconnects the graph; an articulation point is a vertex whose removal does the same.
The least you need to know
- Bridges are cut edges in undirected graphs.
- Articulation points are cut vertices in undirected graphs.
- Both concepts detect single-point failures in connectivity.
- DFS low-link reasoning reveals whether back edges bypass a tree edge or vertex.
- Tree edges with no alternate return route indicate vulnerability.
Key notation
disc[u]
DFS discovery time of u
low[u]
lowest discovery time reachable from u via tree edges plus at most one back edge
bridge
edge whose deletion increases connected-component count
Tiny worked example
- If DFS goes from `u` to child `v` and the subtree under `v` cannot reach any ancestor of `u`, then edge `(u, v)` is a bridge.
- Intuitively, there is no alternate route around that edge.
- The same style of reasoning identifies articulation points when removing a vertex separates child subtrees.
- Low-link values summarize whether such alternate routes exist.
Common mistakes
- Bridges and articulation points are usually defined for undirected graphs.
- A vertex on a cycle is often not an articulation point because the cycle provides an alternate route.
- The DFS root has a special articulation-point rule involving multiple children.
How to recognize this kind of problem
- The problem asks about single edge or single vertex failures.
- You need to know whether a DFS subtree can reconnect upward without using its parent edge.
- Low-link or Tarjan-style DFS is suggested.