Bridges & Articulation Points
Bridges and articulation points are the critical edges and critical nodes of a graph: removing one disconnects the graph.
ENTER
Bridges
None found yet
Articulation points
None found yet
Enter 0 at time 1. Its own discovery time is the best it can reach so far.
Next
Enter 1 at time 2. Its own discovery time is the best it can reach so far.
Mark
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
discvalue 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".
Applying for software engineering roles? Free, no sign-up: