Graph AlgosAlgorithmaka cut edges, critical connections, Tarjan bridge-finding

Bridges

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

▶ VisualizePattern: Depth-First SearchPractice (2)
Progress

Overview

A bridge (cut edge) of an undirected graph is an edge whose removal increases the number of Connected Components. Bridges are the single points of failure of a network: the only link between two parts of the graph. An edge is a bridge exactly when it lies on no cycle.

The linear-time algorithm is Tarjan's: run Depth-First Search (DFS), assign each vertex a discovery time disc[u], and compute low[u] = the smallest discovery time reachable from u's subtree using tree edges downward plus at most one back edge. A tree edge u — v (with v the child) is a bridge iff low[v] > disc[u]: nothing in v's subtree can climb back to u or above without using the edge itself.

Bridges partition the graph into 2-edge-connected components (contract everything except bridges). Removing all bridges and counting components, or building the "bridge tree", is a common follow-up.

undirectedlow-linkDFScut edgeconnectivityO(V + E)

Intuition

A mental model before the formal terms.

Picture the DFS tree as a rope ladder hanging down from the root; back edges are extra ropes tied from a lower rung to a higher one. Cut a ladder rung u — v. Does the part below v fall? It stays up if some rope from below v is tied to u or higher. low[v] measures the *highest* point (smallest discovery time) any rope from v's subtree reaches. If low[v] > disc[u], every rope from below ends at or below v — the subtree hangs by the rung alone, so the rung is a bridge.

Example: edges 0—1, 1—2, 2—0, 2—3. DFS from 0: disc = [0, 1, 2, 3]. Vertex 3 has only its parent: low[3] = 3 > disc[2] = 2 → 2—3 is a bridge. Vertex 2 sees back edge to 0: low[2] = 0. So low[2] = 0 ≤ disc[1] = 1 → 1—2 not a bridge; low[1] = 0 ≤ disc[0] → 0—1 not a bridge.

How it works

  1. Initialise disc[v] = -1, a timer t = 0, and an empty result list.
  2. dfs(u, parentEdge): set disc[u] = low[u] = t++. For each edge (u, v, id): skip if id == parentEdge (do not walk back along the tree edge you came from; comparing edge ids rather than parent vertices handles parallel edges). If v is undiscovered: dfs(v, id), then low[u] = min(low[u], low[v]), and if low[v] > disc[u] record (u, v) as a bridge. Else (v already discovered — a back edge): low[u] = min(low[u], disc[v]).
  3. Call dfs(s, -1) for every undiscovered s to handle disconnected graphs.
  4. Note the asymmetry: tree edges propagate low[v], back edges contribute disc[v]. Using low[v] for back edges over-counts (it can pass through a second back edge) and produces wrong answers for bridges.

Why it works

In a DFS of an undirected graph every non-tree edge is a back edge (connects a vertex to an ancestor); there are no cross edges. So the only way the subtree of v can connect to the rest of the graph without the tree edge u — v is through a back edge from inside the subtree to a proper ancestor of v, i.e. to a vertex with discovery time ≤ disc[u].

low[v] is exactly the minimum discovery time reachable that way (tree edges down, then one back edge up). Hence low[v] ≤ disc[u] ⇔ such an escape exists ⇔ u — v lies on a cycle ⇔ not a bridge. Conversely low[v] > disc[u] ⇔ bridge.

Each vertex and each edge is processed a constant number of times, so O(V + E).

Recognition

How to tell a problem wants this.

  • "Critical connections", "which links, if cut, disconnect the network", "single point of failure between routers".
  • "Count edges not on any cycle", or "minimum edges to add to make the graph 2-edge-connected" (⌈leaves of bridge tree / 2⌉).
  • Undirected graph plus the word "removal" applied to edges — for vertices it is Articulation Points.
“connected groups” → Depth-First Search

Interactive visualization

Play, step, change the input. ← → and space work too.

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

Pseudocode

1disc[*] = -1; t = 0; bridges = []
2dfs(u, parentEdge):
3  disc[u] = low[u] = t++
4  for (v, id) in adj[u]:
5    if id == parentEdge: continue
6    if disc[v] == -1:
7      dfs(v, id); low[u] = min(low[u], low[v])
8      if low[v] > disc[u]: bridges.append((u, v))
9    else: low[u] = min(low[u], disc[v])
10for s in 0..n-1: if disc[s] == -1: dfs(s, -1)

Implementations

1def find_bridges(adj: list[list[tuple[int, int]]]) -> list[tuple[int, int]]:
2    """A bridge is an edge whose removal disconnects the graph. Tarjan's rule:
3    edge (u, v) with v a DFS child is a bridge iff low[v] > disc[u] — nothing
4    in v's subtree can reach u or above without using that very edge.
5    Adjacency stores (neighbour, edge_id) so parallel edges are handled."""
6    n = len(adj)
7 
81 · disc = discovery time, low = earliest reachable discovery time
9    disc = [-1] * n
10    low = [0] * n
11    bridges: list[tuple[int, int]] = []
12    timer = 0
13 
14    for s in range(n):
15        if disc[s] != -1:
16            continue
17 
182 · Frames carry the vertex, its incoming edge id, and a cursor
19        stack = [[s, -1, 0]]  # [vertex, incoming edge id, neighbour cursor]
20        disc[s] = low[s] = timer
21        timer += 1
22 
23        while stack:
24            f = stack[-1]
25            u, in_edge, i = f[0], f[1], f[2]
26            if i < len(adj[u]):
27                f[2] += 1
28                v, edge_id = adj[u][i]
293 · Skip only the exact edge we arrived on, not every parent edge
30                if edge_id == in_edge:
31                    continue
32                if disc[v] == -1:
33                    disc[v] = low[v] = timer
34                    timer += 1
35                    stack.append([v, edge_id, 0])
36                else:
37                    low[u] = min(low[u], disc[v])  # back edge
38            else:
394 · On the way back up, propagate low and apply the bridge test
40                stack.pop()
41                if stack:
42                    p = stack[-1][0]
43                    low[p] = min(low[p], low[u])
44                    if low[u] > disc[p]:
45                        bridges.append((p, u))
46 
475 · A graph with no bridges is 2-edge-connected within each component
48    return bridges
Walkthrough
  1. Frames are three-element *lists* because f[2] += 1 must mutate the entry already on the stack; a tuple would raise.
  2. disc[s] = low[s] = timer chains the assignment, and timer += 1 follows because Python has no post-increment operator.
  3. The if edge_id == in_edge: continue check skips the arrival edge by id, which is what makes parallel edges work.
  4. low[u] = min(low[u], disc[v]) on a back edge and low[p] = min(low[p], low[u]) when unwinding are the two distinct updates.
  5. p = stack[-1][0] reads just the parent vertex from the frame below, since that is all the bridge test needs.
Complexity (this implementation)
time O(V + E) — one DFS, each edge examined twice · space O(V)
Language notes
  • Python has no ++, so the timer increments on its own line; chained assignment (a = b = value) still works and evaluates the right-hand side once.
  • A tuple frame raises TypeError on the cursor increment, which is why the frame is a list.
  • networkx.bridges(G) yields the bridges directly and handles labelled vertices.
  • The iterative form avoids RecursionError, which a recursive Tarjan would hit on a path of about 1000 vertices.
Common mistakes in this language
  • Using a tuple for the frame and hitting TypeError on f[2] += 1.
  • Relaxing low[u] against low[v] rather than disc[v] on a back edge.
  • Tracking the parent vertex instead of the parent edge id, breaking on multigraphs.
Language differences that matter here
  • C++ is the only language here where pushing onto the stack can invalidate a reference to the current frame — std::vector reallocation is real, while JS/TS objects and Python lists are separately heap-allocated.
  • Cursor increment: C++ and JS/TS write f.i++ inline; Python needs a separate f[2] += 1 statement and a mutable list frame.
  • Only Python has a ready-made networkx.bridges; C++ reaches it via Boost.Graph biconnected_components, and JS/TS have nothing.
  • The readonly annotation burden is unique to TypeScript — three nested levels here, where C++ expresses the same intent with a single const&.

Complexity

Best
O(V + E)
Average
O(V + E)
Worst
O(V + E)
Space
O(V + E)

Recursive DFS; convert to an explicit stack for graphs with 10^5+ vertices in Python/JS.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Finding critical links in networks, road systems, or dependency graphs modelled as undirected graphs.
  • Computing 2-edge-connected components or the bridge tree for follow-up questions.
  • Checking whether a graph stays connected after removing any single edge (no bridges ⇔ 2-edge-connected).
Avoid it when
  • The question is about removing vertices — that is Articulation Points (same DFS, different condition).
  • Directed graphs — "bridge" is an undirected concept; for directed reachability after edge removal use Strongly Connected Components or dominator trees.
  • Weighted "most expensive edge to lose" style questions — that is an MST / bottleneck problem, not connectivity.

Alternatives

Articulation PointsConnected ComponentsUnion-Find (Disjoint Set Union)Tarjan's SCC Algorithm

Common mistakes

  • Updating low[u] with low[v] on back edges instead of disc[v] — works by luck on some inputs, fails on others (it can chain two back edges).
  • Skipping the parent by *vertex* instead of by edge id — parallel edges u — v are then wrongly reported as bridges.
  • Using >= instead of > in low[v] > disc[u] (the >= form is for articulation points).
  • Not restarting DFS in every component.
  • Recursion depth: a long path graph overflows the default stack in Python; raise the limit or go iterative.

Interview patterns

  • Critical Connections in a Network: return all bridges.
  • Minimum edges to add to make a graph 2-edge-connected: build the bridge tree, answer ⌈leaves / 2⌉.
  • Count edges that lie on some cycle: E − #bridges.
Interview questions on this
Mock interviews

Example problems

Critical Connections in a NetworkhardRedundant Connectionmedium