Bridges in Undirected Graphs

Find edges whose removal disconnects a graph and connect each bridge to a depth-first low-link witness.

Bridges in Undirected Graphs

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.

Algorithm Overview

The algorithm runs DFS and records two values for each vertex v: 1. tin[v]: The time when the vertex was first visited (discovery time). 2. low[v]: The lowest discovery time reachable from v, including through at most one back-edge from a descendant.

For every tree edge u - v (where u is the parent and v is the child), if low[v] > tin[u], it means there is no back-edge from v or any of its descendants that reaches u or an ancestor of u. Thus, removing u - v disconnects v from u, making it a bridge.

Worked Example: Triangle with a tail

Consider a graph with vertices 0, 1, 2, 3 and edges 0-1, 1-2, 2-0, 2-3. We start DFS from vertex 0. The tree and discovery values proceed as follows:

Start at 0: tin[0]=1, low[0]=1. Move to 1.
At 1: tin[1]=2, low[1]=2. Move to 2.
At 2: tin[2]=3, low[2]=3. We scan 0 (a back-edge). Update low[2] = min(3, tin[0]=1) = 1.
Still at 2, move to 3.
At 3: tin[3]=4, low[3]=4. No other edges. DFS exits 3. low[3] remains 4.
Back to 2: We check the bridge condition for edge 2-3. Is low[3] > tin[2]? 4 > 3 is true! The edge 2-3 is a bridge.
DFS exits 2. low[1] = min(low[1]=2, low[2]=1) = 1. Bridge condition for 1-2: low[2] > tin[1] (1 > 2) is false.
DFS exits 1. low[0] = min(low[0]=1, low[1]=1) = 1. Bridge condition for 0-1: low[1] > tin[0] (1 > 1) is false.

We successfully identified 2-3 as the only bridge. The connected components remain 2 (since the simulation counts 4 as an isolated vertex out of 5 fixed vertices 0..4, so 0,1,2,3 is one component and 4 is another, totaling 2 components).

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/low values 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-4 to 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.

Limitations and Assumptions

This interactive model focuses on explaining the core algorithm on a small, bounded scale.

The graph is restricted to exactly five fixed vertices (0 to 4) to ensure the visual tracing remains clear and easy to follow.
The maximum number of distinct unordered edges is bounded to 10, avoiding overly cluttered visual layouts.
The module operates strictly on exact integer inputs and rejects multigraphs (duplicate edges) or self-loops (0-0).
This algorithm identifies edge-connectivity bottlenecks (bridges), but does not identify vertex-connectivity bottlenecks (articulation points), though their algorithms are very similar.

References

CP-Algorithms. “Finding bridges in O(N+M)”. Available at: https://cp-algorithms.com/graph/bridge-searching.html. This source describes the standard O(V+E) Tarjan's bridge-finding algorithm using the tin and low discovery times.

The CP-Algorithms reference provides the rigorous mathematical backing for the bridge condition low[to] > tin[v] and the linear-time traversal strategy used in this module.

Bridges in Undirected Graphs