Graph AlgosGraph Algorithms

Bridges (Tarjan low-link)

Find every edge of an undirected graph whose removal disconnects it, using DFS discovery times and low-link values.

Learn Bridges →
ABCDEFG
Bridges
empty
1/21A bridge is an edge whose removal disconnects the graph. One DFS with discovery times and low-links finds all of them in O(V + E).
Current node (label = disc/low)On recursion pathFinishedDFS tree edgeBack edgeBridge
PseudocodeLearn Bridges →
1time = 0
2def dfs(u, parent):
3  disc[u] = low[u] = time; time += 1
4  for v in neighbors(u), skipping parent:
5    if v unvisited: dfs(v, u); low[u] = min(low[u], low[v])
6      if low[v] > disc[u]: (u, v) is a bridge
7    else: low[u] = min(low[u], disc[v])   # back edge
8  (root has no special rule)
9for u in nodes: if u unvisited: dfs(u, None)
Complexity
best O(V + E)
avg O(V + E)
worst O(V + E)
space O(V + E)
Speed