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.
جو کم از کم جاننا ضروری ہے
- 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.
اہم علامتیں
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
مختصر حل شدہ مثال
- 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.
عام غلطیاں
- 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.
اس قسم کے سوال کو کیسے پہچانیں
- 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.