Sign in to watch this lesson
Advanced - Graphs Ā· 4:58
Bridges & Articulation Points (Low-Link)
A bridge is an edge, and an articulation point a vertex, whose removal disconnects a graph. One depth-first search finds them all in O(n + m): it records each vertex's entry time tin and its low-link value low, the smallest entry time its subtree can reach with one back edge. A tree edge v-to is a bridge when low[to] > tin[v], and v is a cut vertex when some child has low[to] >= tin[v], with a separate rule for the root.
You will learn
- Explain why a DFS of an undirected graph has only tree edges and back edges, and compute tin and low for every vertex
- Find all bridges with the test low[to] > tin[v] and all articulation points with low[to] >= tin[v] plus the root rule
- Handle parallel edges by skipping the parent edge by index, and deduplicate cut vertices
- Make the search safe on deep or disconnected graphs with an explicit stack and an outer loop over roots