Pattern visualizer
Bridges in Graph
A single DFS pass answers this without ever actually removing an edge. Give every node a discovery time, then track its low-link: the earliest discovery time reachable from that node's subtree using at most one back-edge. When a child's low-link can only reach back down to itself or later — never past its parent's own discovery time — the tree edge connecting them is the ONLY way between the two halves it separates, so removing it disconnects the graph. Any edge that sits on a cycle always has a back-edge shortcut lowering some descendant's low-link past the parent, so it survives. Animated on: 7 nodes, undirected: two triangles (0-1-2 and 3-4-5) joined by edge (2,3), plus a pendant leaf 6 hanging off 5 — which edges are bridges?.
Tarjan's DFS: an edge is a bridge only if nothing in the child's subtree can reach back past it
Badge = discovery time / lowest reachable time
Call stack
Start the DFS at node 0: give it discovery time 0 and set its low-link to the same value — the low-link only ever drops from here, never rises.
1FUNCTION findBridges(n, edges):2 BUILD adj FROM edges3 tin, low <- ARRAY OF n VALUES -14 timer <- 05 FUNCTION dfs(u, parent):6 tin[u], low[u] <- timer7 timer <- timer + 18 FOR EACH v IN adj[u]9 IF v = parent CONTINUE10 ELSE IF tin[v] = -111 dfs(v, u)12 low[u] <- MIN(low[u], low[v])13 IF low[v] > tin[u]14 APPEND (u, v) TO bridges15 ELSE16 low[u] <- MIN(low[u], tin[v])17 dfs(0, -1)18 RETURN bridges
← / → step · space play · Home restart