Critical Link
Removing a bridge splits the graph into two separate components. It's a single point of failure for communication between nodes.
Loading...
Loading...
Loading Curriculum...
Loading Subject...
Loading Topic...
Loading Lesson...
Loading Lab...
A bridge is an edge whose removal increases the number of connected components in an undirected graph. It signifies a critical link in any network or infrastructure.
Removing a bridge splits the graph into two separate components. It's a single point of failure for communication between nodes.
If there's no back-edge from a node or its descendants to any ancestor of the parent, then the edge to the parent is a bridge.
An edge (u, v) is a bridge if and only if low[v] > disc[u], meaning v has no alternative path to u.
Like articulation points, bridges can be found in a single DFS pass, making the analysis highly efficient for large networks.