What Is a Bridge in a Graph? The Edge That Can Split Everything

Picture a small town connected to the highway by a single road. One construction project, one washed-out bridge, and the town is cut off. Everything still works internally. Debates happen. The coffee is still bad. But nothing gets in or out.

That single road is a bridge in a graph. Finding bridges is a classic coding interview problem that shows up at Google and Amazon, usually disguised as "critical connections" or "network reliability." Here is how to find every bridge in one DFS pass, and why the obvious solution will absolutely time out.

What Makes a Bridge: No Backup Route

A bridge (also called a cut edge) is an edge whose removal increases the number of connected components in the graph.

Simpler: an edge is a bridge if and only if it is not part of any cycle. Cycles create redundancy. If two nodes share a cycle, pull out one edge and the other path picks up the slack. But if the only connection between two nodes is a single edge, that edge is load-bearing. Take it out and the graph splits.

This pattern shows up everywhere. The microservice every other service calls. The one engineer who knows how the deployment works. The one road out of town. All bridges.

A Concrete Example

Take this graph:

Two graphs side by side: left shows all edges highlighted as bridges, right shows how adding a cycle makes two edges non-bridges

1 -- 2 -- 3 -- 4
         |
         5

Walk through each edge:

Edge (1, 2): Remove it. Node 1 is isolated. Bridge.
Edge (2, 3): Remove it. Nodes 1 and 2 are cut off from 3, 4, 5. Bridge.
Edge (3, 4): Remove it. Node 4 is isolated. Bridge.
Edge (3, 5): Remove it. Node 5 is isolated. Bridge.

Every edge is a bridge because there are no cycles. Now add one edge: connect node 4 back to node 5.

1 -- 2 -- 3 -- 4
         |    |
         5 ---+

Now edges (3, 4) and (3, 5) are no longer bridges. Remove either one and you can still reach node 4 from node 5 through the other route. But (1, 2) and (2, 3) are still bridges. Removing either one disconnects nodes 1 and 2 from the rest.

A bridge is any edge with no detour around it.

The Naive Approach: It Times Out

The obvious solution: remove each edge, check whether the graph is still connected, then put the edge back.

def naive_bridges(n, edges):
    bridges = []
    adj = build_adjacency_list(n, edges)

    for u, v in edges:
        adj[u].remove(v)
        adj[v].remove(u)

        if not is_connected(n, adj):
            bridges.append((u, v))

        adj[u].append(v)
        adj[v].append(u)

    return bridges

Each connectivity check is O(V+E). You run it E times. Total: O(E * (V+E)).

For a graph with 1,000 nodes and 10,000 edges, that is 100 million operations. LeetCode 1192 has up to 100,000 nodes and 100,000 edges. Submit the naive solution and watch it hit the time limit while you are still explaining the approach.

The naive solution is useful exactly once: in an interview, you say it out loud, note the complexity, and move on. "I could check each edge individually in O(E * (V+E)), but that times out. Let me do better." Then do better.

Tarjan's Algorithm: One DFS Pass, O(V+E)

Robert Tarjan, 1972, realized you can figure out whether an edge is a bridge while running a single DFS, by tracking two values per node as you go.

disc[u] is the discovery time: the step number at which DFS first visited node u. First node visited gets disc = 0, next gets disc = 1, and so on. Think of it as a timestamp.

low[u] is the minimum discovery time reachable from u using any combination of tree edges and back edges (edges to already-visited ancestors). It answers one question: "how far back up the tree can u reach without using the edge it arrived on?"

DFS tree annotated with disc and low values at each node, showing that low[v] > disc[u] means the edge u-v is a bridge

The algorithm in three steps:

When you arrive at node u from parent p, set disc[u] = low[u] = timer++.
For each neighbor v of u: if unvisited, recurse then set low[u] = min(low[u], low[v]); if visited and not the parent, set low[u] = min(low[u], disc[v]).
After returning from child v: if low[v] > disc[u], edge (u, v) is a bridge.

Why does low[v] > disc[u] mean bridge? It means v and all of v's descendants cannot reach u or any ancestor of u through any back edge. The only path from v back to u is the tree edge (u, v) itself. Remove it and v's entire subtree disconnects.

The low value is effectively a panic metric. After finishing a subtree, how high can it climb back up without using the edge that got it there? If it cannot reach u's level, the edge connecting them is a bridge.

The Parent Edge Trap

This is where most implementations break. Including, statistically, yours on the first attempt.

In an undirected graph, every edge is stored twice. Visit v from u and both adj[u] contains v and adj[v] contains u. When DFS is at v scanning its neighbors, it sees u in the adjacency list. u is already visited. If you naively update low[v] = min(low[v], disc[u]), you are treating the edge you just came down as a back edge that lets v reach u.

It cannot do that. v did not discover a back edge. It rediscovered the tree edge it arrived on. You are letting the node call back home through the same wire it used to get there.

Track the parent, and skip the neighbor if it equals the parent.

for neighbor in adj[v]:
    if neighbor == parent:
        continue
    if visited[neighbor]:
        low[v] = min(low[v], disc[neighbor])
    else:
        dfs(neighbor, v)
        low[v] = min(low[v], low[neighbor])
        if low[neighbor] > disc[v]:
            bridges.append((v, neighbor))

One subtlety: if the graph has parallel edges (multiple edges between the same two nodes), skipping by node ID is not enough. You need to track edge IDs and skip only the specific edge you arrived on, not every edge going back to the parent.

Full Implementation

def critical_connections(n: int, connections: list[list[int]]) -> list[list[int]]:
    adj = [[] for _ in range(n)]
    for u, v in connections:
        adj[u].append(v)
        adj[v].append(u)

    disc = [-1] * n
    low = [0] * n
    bridges = []
    timer = [0]

    def dfs(node: int, parent: int) -> None:
        disc[node] = low[node] = timer[0]
        timer[0] += 1

        for neighbor in adj[node]:
            if neighbor == parent:
                continue
            if disc[neighbor] == -1:
                dfs(neighbor, node)
                low[node] = min(low[node], low[neighbor])
                if low[neighbor] > disc[node]:
                    bridges.append([node, neighbor])
            else:
                low[node] = min(low[node], disc[neighbor])

    for i in range(n):
        if disc[i] == -1:
            dfs(i, -1)

    return bridges

Time: O(V+E). Each node and edge is visited once. Space: O(V+E) for the adjacency list, the disc and low arrays, and the recursion stack.

Bridge vs. Articulation Point: One Character of Difference

These two concepts are related, and interviewers will occasionally ask you to compare them.

An articulation point (cut vertex) is a node whose removal disconnects the graph. A bridge is an edge whose removal disconnects the graph. The detection conditions look almost identical:

What	Condition
Bridge (edge u→v)	`low[v] > disc[u]` (strict greater-than)
Articulation point (node u)	`low[v] >= disc[u]` for some child v, with a root exception

The strict vs. loose inequality is literally the only difference in code. A bridge requires v's subtree to have no path back to u at all. An articulation point only requires that v cannot reach any node strictly before u in DFS order. The root of the DFS tree is a special case: it is an articulation point only if it has more than one DFS child.

Mess up the > vs >= and you get wrong answers on both problems. It is the kind of bug that is invisible to intuition and only shows up on specific test cases at 11pm.

For a deep dive on both, see Bridges and Articulation Points.

The Interview Problem: LeetCode 1192

LeetCode 1192 "Critical Connections in a Network" is the canonical bridge problem. It gives you n servers and a list of connections, and asks for every connection whose removal would isolate at least one server.

It is marked Hard. Not because the algorithm is deeply complicated, but because it has three distinct failure modes stacked in sequence:

Recognizing that "critical connections" means bridges is the first hurdle. Nothing in the problem statement uses the word "bridge." You are expected to make that translation yourself.
The naive O(E*(V+E)) approach times out. The problem constraints are basically designed to reject it.
Parent edge handling bugs produce wrong answers that look random when you try to trace them manually.

If you can implement this cleanly and explain the disc/low invariant out loud while writing the code, this problem turns into a strong performance. The explain-out-loud part is what actually gets you the hire write-up. Tools like SpaceComplexity let you practice exactly that: voice-based DSA mock interviews with rubric feedback on whether your verbal reasoning matches what you are typing.

Where Bridges Show Up

Network resilience. Any single link whose failure would isolate part of a network is a bridge by definition. Internet backbone engineers specifically find and eliminate bridges through redundant routing paths. Every data center with a single uplink is, technically, a graph bridge.

Dependency graphs. If module A is the only path to module B, that import is a bridge. Build systems and package managers reason about this to identify fragile dependencies. That one library that seventeen services depend on, which nobody touches because it works, is load-bearing.

Road networks. Infrastructure planners identify physical bridges and single-road connections to prioritize maintenance and justify adding alternate routes. If you have ever been stuck because one road closed and there was no other way, you experienced a bridge problem firsthand.

Social networks. A person who connects two otherwise separate clusters is a bridge in the social graph. Remove them and the two communities stop talking. This explains why "connectors" are both strategically important and perpetually exhausted.