Graph Theory37 sections · 1633 units
Open in Course

Critical Connections - Trace

(Running Tarjan's algorithm)

Trace on input n=4n=4, edges [[0,1],[1,2],[2,0],[1,3]][[0,1],[1,2],[2,0],[1,3]]: DFS from 00: disc[0]=0, low[0]=0. Visit 11: disc[1]=1, low[1]=1. Visit 22: disc[2]=2, low[2]=2. Back edge 202-0: low[2]=0. Backtrack: low[1]=0.

Visit 33: disc[3]=3, low[3]=3. Backtrack: check low[3]=3 > disc[1]=1, add (1,3)(1, 3) to result. Bridges: [[1,3]][[1,3]]. This is the only edge whose removal disconnects the graph.