Bridges in Undirected Graphs
Find edges whose removal disconnects a graph and connect each bridge to a depth-first low-link witness.
Free theory articleFind edges whose removal disconnects a graph and connect each bridge to a depth-first low-link witness.
Concept & interpretation
In a simple undirected graph, a bridge is an edge whose removal strictly increases the number of connected components. Tarjan's low-link algorithm uses a single Depth-First Search (DFS) to efficiently find all bridges in linear time by comparing discovery times and lowest reachable times.
Experimenting with the Module
You can verify these properties yourself using the interactive Bridges module. By observing the visual DFS tree and low-link discovery times, you can trace exactly when a bridge is identified.
- Load the module and observe the default graph edges
0-1,1-2,2-0,2-3. - Press the Step button to advance the algorithm event by event, watching as nodes are discovered and their
tin/lowvalues appear. - Press Finish to immediately compute the entire tree. Verify that the bridge count is 1 and the specific bridge edge 2-3 is highlighted.
- Change the Edges input to
0-1,1-2,2-3,3-4to create a spanning path. Note that every edge becomes a bridge. - Try to enter an invalid edge like
0-0. The system will reject self-loops, and the output status will switch to Invalid.