Critical points of a graph
In an undirected graph, an articulation point is a node whose removal increases the number of disconnected pieces. A bridge is an edge with the same property. These mark the fragile spots of a network where a single failure splits it.
Depth first numbers
A single depth first search assigns each node a discovery time and computes a low value, the earliest discovery time reachable using tree edges and at most one back edge. Comparing these numbers across each tree edge reveals the critical points.
- A non root node is an articulation point if some child cannot reach above the node, that is the child's low value is at least the node's discovery time.
- The root is an articulation point only if it has two or more children in the search tree.
- An edge is a bridge when the child's low value is strictly greater than the parent's discovery time, meaning no back edge bypasses it.
Why one pass suffices
All the low values are computed during the same traversal that builds the search tree, so a single depth first search reveals every articulation point and bridge together in linear time.
Key idea
Use discovery times and low values from one depth first search to flag nodes and edges whose removal disconnects the graph.