Bridge Finding

A bridge (or cut edge) is an edge whose removal disconnects the graph. Bridge finding locates the critical links of a network, the connections with no alternative route.

How it works

A single depth-first search assigns discovery times and low-link values. An edge (u, v), where v is a DFS child of u, is a bridge exactly when low[v] > disc[u], meaning nothing in the subtree of v links back to u or above. All bridges are found in O(V + E) time. The same DFS skeleton also yields articulation points, and contracting the 2-edge-connected components produces the bridge tree of the graph.

Applications

Bridges reveal critical fiber links in telecom backbones, indispensable roads and rail segments, and fragile connections in power grids. In software, bridge analysis helps assess API dependency risk. LeetCode features it as the well-known critical connections problem.