Skip to main content

Bridges

Learn Bridges (Graphs, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

Bridges in an Undirected Graph A bridge (cut edge) is an edge whose removal disconnects the graph. They mark weak links in a network. Run one DFS and compute disc and low for each vertex. A tree edge u - v (v a child of u) is a bridge when low[v] > disc[u] : nothing in v's subtree can get back to u or above. Skip only the edge you came from (by edge id , so parallel edges are handled). Cost: O(V + E) .

More lessons in Graphs