Tarjan's Bridges

How the bridge algorithm works

A bridge (cut edge) is an edge whose removal disconnects the graph. In a tree every edge is a bridge; in a single triangle, none are. Real networks lie somewhere in between, and finding bridges quickly tells you which connections are catastrophic single-points-of-failure.

Tarjan's insight: run a DFS over the graph and maintain two integers per vertex:

• disc[v] — the discovery time, the counter value when DFS first visits v.
• low[v] — the smallest disc value reachable from v's subtree, using tree edges plus at most one back edge (to a vertex already discovered).

For each tree edge u → v, after the recursive call returns, check low[v]. If low[v] > disc[u], that edge is a bridge — no back path from v's subtree can reach u or earlier. Cutting it strands v's subtree.

Why the low-link condition works

Suppose low[v] > disc[u]. By definition of low-link, every vertex in v's DFS subtree reaches only vertices with disc ≥ low[v] > disc[u]. So none of them connects back to u or any earlier-discovered vertex without going through the edge u-v. Remove that edge, and v's subtree becomes its own component — the very definition of a bridge.

Conversely, if low[v] ≤ disc[u], there's a back edge from some descendant of v to u or earlier — an alternate route. Cutting u-v doesn't disconnect anything.

Worked example — 10-node graph

Consider an undirected graph with two dense regions connected by a single edge:

  1 — 2 — 3       7 — 8
  |   |   |       |   |
  4 — 5 — 6 ————— 9 — 10

The edge 6 — 9 connects the two clusters. Run DFS starting at 1:

Node	disc	low	Tree-edge parent	Notes
1	0	0	—	root
2	1	0	1	back-edge to 1? — yes via 5-4-1
3	2	1	2	back-edge to 2 via 6-5-2
4	5	0	5	back-edge to 1
5	4	0	2	cycle through 4-1
6	3	1	3	cycle 3-6-5-2
7	7	6	9	cycle 7-8-10-9
8	8	6	7	back-edge to 9 via 10
9	6	6	6	can only reach itself
10	9	6	8	back-edge to 9

Check each tree edge: only edge 6 → 9 satisfies low[9] = 6 > disc[6] = 3. That's the single bridge — exactly the intuition that cutting it splits the two clusters. Time: 10 DFS visits + 11 edge checks = O(V + E) ≈ 21 elementary operations.

Cost in real terms

On a graph of 1 million vertices and 5 million edges (a typical mid-sized social or road network), Tarjan's bridge algorithm finishes in about 100 ms in compiled C++ — essentially the cost of one DFS pass. Memory: 8 MB for two int32 arrays. The bridge-block tree (collapse each 2-edge-connected component to a single node) typically has 10–30% as many nodes as the original on real-world graphs — useful as a sparsified planning structure.

Tarjan's bridges vs alternatives

	Tarjan's bridges	Naive (remove each edge)	Chain decomposition	Random sampling	Min-cut (Stoer-Wagner)
Time	O(V + E)	O(E · (V + E))	O(V + E)	O((V + E) log V)	O(V·E + V² log V)
Finds all bridges	Yes	Yes	Yes	Probabilistic	One min cut only
Implementation	One DFS	BFS per edge	Two DFS passes	Karger's trick	Heavy machinery
Online (with link/cut)	No	No	No	No	Specialized variants exist
Output	Bridge set	Bridge set	Bridge set + ear decomp	Bridge set	Bridges + min cut
Use case	Default choice	Pedagogical	Planarity / SPQR	Approximate, parallel	Optimal cut, not bridges

JavaScript implementation

// Iterative Tarjan bridges — avoids recursion limits on deep graphs.
// graph: { v: [neighbour, ...] } as an undirected adjacency list.
function findBridges(graph) {
  const disc = new Map(), low = new Map();
  const parent = new Map();
  const bridges = [];
  let timer = 0;

  function dfs(start) {
    const stack = [[start, 0]];
    disc.set(start, timer); low.set(start, timer); timer++;
    parent.set(start, null);
    while (stack.length) {
      const top = stack[stack.length - 1];
      const [u, idx] = top;
      const neighbours = graph[u] || [];
      if (idx < neighbours.length) {
        const v = neighbours[idx];
        top[1]++;
        if (!disc.has(v)) {
          disc.set(v, timer); low.set(v, timer); timer++;
          parent.set(v, u);
          stack.push([v, 0]);
        } else if (v !== parent.get(u)) {
          // back edge — update low[u]
          low.set(u, Math.min(low.get(u), disc.get(v)));
        }
      } else {
        // Done with u; pop and update parent's low
        stack.pop();
        const p = parent.get(u);
        if (p !== null) {
          low.set(p, Math.min(low.get(p), low.get(u)));
          if (low.get(u) > disc.get(p)) {
            bridges.push([p, u]);
          }
        }
      }
    }
  }

  for (const v of Object.keys(graph)) {
    if (!disc.has(v)) dfs(v);
  }
  return bridges;
}

// Example
const g = {
  1: [2, 4], 2: [1, 3, 5], 3: [2, 6], 4: [1, 5],
  5: [2, 4, 6], 6: [3, 5, 9],
  7: [8, 9], 8: [7, 10], 9: [6, 7, 10], 10: [8, 9]
};
console.log(findBridges(g));  // [[6, 9]] — the single bridge

Python implementation (recursive form)

def find_bridges(graph):
    disc, low = {}, {}
    bridges = []
    timer = 0

    def dfs(u, parent):
        nonlocal timer
        disc[u] = low[u] = timer; timer += 1
        for v in graph.get(u, []):
            if v not in disc:
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if low[v] > disc[u]:
                    bridges.append((u, v))
            elif v != parent:
                # back edge
                low[u] = min(low[u], disc[v])

    for v in graph:
        if v not in disc:
            dfs(v, None)
    return bridges

# For very deep graphs, set sys.setrecursionlimit(10**6) or use iterative form.

Variants and extensions

• Bridge-block tree (2-edge-connected condensation). Contract each 2-edge-connected component to a single node; keep bridges as edges between them. The result is a tree (by construction — any cycle would have lived inside a 2-EC component). Useful for network-flow shortcuts.
• Online bridge finding. With link-cut trees (Sleator-Tarjan 1983) the bridge set can be maintained under edge insertions and deletions in O(log² n) per update. Used in fully-dynamic graph connectivity.
• Chain decomposition (Schmidt 2013). Two-pass algorithm: first DFS finds tree edges; second pass walks back edges. Slightly simpler bookkeeping than Tarjan's classic version, same O(V+E).
• Articulation points jointly. The same DFS pass that finds bridges can find articulation points by a slightly different test on tree edges. Many implementations bundle both.
• SPQR-tree decomposition. Generalizes bridge-block trees to triconnected components — splits a biconnected graph into series, parallel, and rigid pieces. Used in planarity tests.

When to use bridge detection

• Network resilience analysis. Telecom and ISP planners use bridges to find single-points-of-failure: the edges that, if cut, isolate part of the network. Production routing tables sometimes treat bridges as "critical" with redundancy requirements.
• Bridge-block decomposition. Compute the 2-edge-connected components — graphs without bridges within them. Used as a preprocessing step in min-cut computations.
• Web crawler graph analysis. Bridges separate communities of pages; identifying them helps prioritize crawl budget.
• Bioinformatics — gene regulatory networks. A bridge in a transcription-factor graph represents a single connection between regulatory modules — often biologically significant.
• Planarity testing. Tarjan-Hopcroft's linear-time planarity algorithm uses bridge decomposition as a preprocessing step.

Famous bridge problems

LeetCode 1192 — Critical Connections in a Network

Given a connected undirected network of N servers and M connections, return all "critical" connections — connections whose removal would disconnect the network. That's exactly the bridge set. Tarjan's O(V+E) solution passes; the brute-force O(M · (V+E)) "remove each edge and BFS" version times out around N = 10⁴.

Two-edge-connected augmentation

Given an undirected graph, what's the minimum number of edges to add so that no bridge remains? Eswaran-Tarjan (1976) showed this is the max of (number of leaves in the bridge-block tree, divided by 2 rounded up) and (number of isolated components in the original graph minus 1). Solution: contract via bridge-block tree, then pair up leaves greedily — all driven by an initial Tarjan bridge pass.

Common bugs and edge cases

• Updating low through the parent edge. When iterating neighbors of u, ignore the edge back to u's DFS parent — that's the tree edge we just came from, not a back edge. With multi-edges, ignore only the *specific* parent-edge instance, not every edge to the parent (or you miss the redundancy).
• Using disc[v] vs low[v] in the update. For a back edge u → v (v already discovered), update low[u] = min(low[u], disc[v]). For a finished tree-edge return from v, update low[u] = min(low[u], low[v]). Swapping these silently misses some bridges.
• Recursion limit. A path graph of 10⁶ nodes blows JavaScript's stack at ~10⁴ frames. Use the iterative DFS form for production code; Python users should also use the iterative form rather than just raising sys.setrecursionlimit.
• Bridge in self-loops. A self-loop is never a bridge — removing it doesn't disconnect anything. Some implementations crash because the self-loop confuses the parent-edge check. Filter self-loops out before running, or handle them explicitly.
• Disconnected graphs. Run DFS from every unvisited vertex. Forgetting the outer for-loop misses bridges in components not reachable from the starting vertex.
• Directed graph misuse. Bridges are an undirected concept. For directed graphs use 2-edge-connectivity or "strong bridges" — different algorithms entirely (e.g., Italiano-Laura-Santaroni 2010).