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.
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
Worked example
- If DFS goes from
uto childvand the subtree undervcannot reach any ancestor ofu, 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 it
- 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.
Next recommended lesson
Continue through this topic with Least You Need to Know: BST Invariants, Search Ranges, and Inorder Structure.
Least You Need to Know: BST Invariants, Search Ranges, and Inorder StructureRelated lessons
Keep going with nearby lessons in the same topic.