Bridges & Articulation Points
Identify critical connections (Bridges) and critical nodes (Articulation Points) whose removal would disconnect the graph.
Trace Table
| Node | Disc | Low |
|---|---|---|
| 0 | - | - |
| 1 | - | - |
| 2 | - | - |
| 3 | - | - |
| 4 | - | - |
| 5 | - | - |
| 6 | - | - |
Ready to start
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Intuition
Consider a network of islands connected by bridges.
Bridge: A literal bridge that, if collapsed, makes it impossible to reach some islands from others.
Articulation Point: A critical island (hub) that, if it sinks, splits the network into disconnected pieces.
Concept
We use Tarjan's Algorithm (based on DFS) to find these efficiently in O(V+E).
- Discovery Time (disc): The time/order a node was first visited.
- Low Link Value (low): The lowest `disc` value reachable from the node (including itself) in the DFS tree, possibly using a back-edge (but not the direct parent edge).
How it Works
For Bridges (Edge u-v): If low[v] > disc[u], it means there is NO back-edge from `v` or its descendants to `u` or its ancestors. The edge `u-v` is the only way to reach `v`.
For Articulation Points (Node u): If low[v] >= disc[u] for any child `v`, then `u` is an articulation point (unless `u` is root, which needs >1 children). This means `v` has no back-edge to avoid `u`.
Step-by-Step Breakdown
During DFS Traversal:
- Visit u: Set
disc[u] = low[u] = time++. - For neighbor v:
- If parent, ignore.
- If visited (Back-edge),
low[u] = min(low[u], disc[v]). - If unvisited (Tree-edge), recurse
dfs(v), thenlow[u] = min(low[u], low[v]). - Check Bridge condition:
low[v] > disc[u]. - Check Articulation condition:
low[v] >= disc[u].
When to Use
Applications:
- Network reliability: Finding single points of failure (routers, cables).
- Social Network Analysis: Finding key influencers or bridges between communities.
- Graph Decomposition.
When NOT to Use
- Highly Connected Graphs: If every node has high degree, bridges are unlikely (e.g., Complete Graphs).
- Simple Reachability: Use BFS/Union-Find if you just want to know IF it's connected, not WHERE it breaks.
How to Identify
"Find critical connections", "Single point of failure", "Edge whose removal increases connected components".
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.