Tarjan's Bridge Detection Algorithm
What is a Bridge?
A bridge (also called a cut edge) in an undirected graph is an edge whose removal increases the number of connected components. In simpler terms, if you remove a bridge, the graph falls apart into two or more disconnected pieces.
Graph with a Bridge
Edge 0-2 is a bridge. Remove it and nodes {0,1} disconnect from {2,3,4}.
Graph Without Bridges
Adding edge 1-4 creates a cycle. Now no single edge removal disconnects the graph.
The Naive Approach
The brute-force method is straightforward: for every edge (u, v) in the graph, temporarily remove it and run BFS/DFS to check whether the graph remains connected.
| Aspect | Complexity |
|---|---|
| Edges checked | O(E) |
| Connectivity check per edge | O(V + E) |
| Total | O(E × (V + E)) |
For a graph with 100,000 edges, that is around 1010 operations. Far too slow. Tarjan's algorithm solves this in a single DFS pass: O(V + E).
DFS Trees and Back Edges
When you run DFS on an undirected graph, every edge falls into exactly one of two categories:
- Tree edge: The edge used to discover a new (unvisited) node. These edges form a spanning tree.
- Back edge: An edge to an already-visited node (not the parent). These create cycles in the graph.
Visualizing the DFS Tree
Consider a graph with 6 nodes. The DFS starting from node 0 produces a spanning tree (solid green) with back edges (dashed purple):
Discovery Time and Low Values
Tarjan's algorithm relies on two arrays that are filled as DFS explores the graph. Understanding these two arrays is the single most important part of the algorithm. Let us build intuition for each one before combining them.
disc[v]: Discovery Time
We keep a global counter (starting at 0) that increments every time we visit a new node. disc[v] records the value of this counter when node v is visited for the first time.
Think of it as a timestamp: the earlier a node is discovered, the smaller its disc value.
Animation: Watch disc values get assigned as DFS visits each node
low[v]: Low-Link Value
This is the trickier concept. low[v] answers the question:
Starting from node v, if I go down through tree edges and then take at most one back edge upward, what is the earliest discovered ancestor I can reach?
Initially, low[v] = disc[v] (the best you know is yourself). Then it gets updated in two situations:
Case 1: Direct Back Edge
If node v has a back edge to an already-visited ancestor w, then v can reach w directly. So:
We use disc[w] (not low[w]) because we are using one back edge to reach w itself.
Case 2: Propagation from Child
If v has a child c in the DFS tree, and c (or something in c's subtree) can reach an ancestor, then v can reach it too through c. So:
The child passes its best reachability upward when DFS backtracks.
low[w] instead of disc[w] for back edges. For bridges, both give the same answer. But for articulation points, using low[w] can produce wrong results. Always use disc[w] for correctness in both problems.
Deep Dive: Why the Two Updates Use Different Sources
The two update rules for low[] are where most learners get confused. They look almost identical — both use min() — but the second argument is critically different. Let us dissect each one individually, understand why it must use that particular source, and see what goes wrong if you swap them.
Update 1 — Back Edge: low[u] = min(low[u], disc[v])
When does this fire? During the DFS from node u, we examine a neighbor v and find that v has already been visited (it is on our DFS call stack — an ancestor). Crucially, v is not the parent of u, so the edge u→v is a back edge.
Why disc[v] and not low[v]?
- The back edge is a direct, one-hop connection from u to the ancestor v. It proves that u can physically reach the node discovered at time
disc[v]. That is a concrete fact about u's reachability. - The back edge does not traverse v's subtree. It goes to node v, not through it. Whatever v's subtree can reach (captured by
low[v]) is irrelevant here — u is not entering v's subtree via this edge. - Using
low[v]would "borrow" information u has no right to claim.low[v]might be lower thandisc[v]because some node deep inside v's subtree has its own back edge to an even earlier ancestor. But u's back edge only reaches v — not that earlier ancestor. - For bridges specifically, it turns out both
disc[v]andlow[v]produce the same final bridge set. But for articulation points, usinglow[v]can falsely lower a node'slow[]value, causing the algorithm to miss cut vertices. Usingdisc[v]is always correct for both problems.
Think of it this way: A back edge is like spotting a friend (ancestor v) directly across the room. You know you can reach that friend (disc[v]). You don't automatically know about everyone that friend can reach through their connections (low[v]).
Update 2 — Child Return: low[u] = min(low[u], low[v])
When does this fire? We called DFS(v) from DFS(u), and now v's DFS has completely finished. The edge u→v is a tree edge. At this point, low[v] has been fully computed — it reflects the earliest ancestor reachable from v's entire subtree.
Why low[v] and not disc[v]?
- u→v is a tree edge — u owns v's subtree. Everything reachable from v's subtree is also reachable from u (go down to v, then follow whatever path v's subtree uses). So u inherits the full reachability information:
low[v]. - Using
disc[v]here would be catastrophically wrong. It would tell u: "the best I get from my child's subtree is when child v was discovered" — completely discarding all back-edge information that v's subtree discovered. The entire propagation mechanism would break. - This is the propagation step — the reason
low[]values "flow upward" during DFS backtracking. Without this rule, back-edge reachability would be stuck at the single node that found the back edge, and no parent would ever learn about it.
Think of it this way: Your child v went on a scouting mission (DFS through v's subtree) and came back with a report: "the earliest ancestor my team can reach is low[v]." Since you (u) sent the scout, you get to use the full report.
low[u] equals the minimum of these three quantities:
disc[u]— the node's own discovery time (the base case)disc[w]for every ancestor w reachable from u via a single back edgelow[c]for every child c of u in the DFS tree (propagated reachability)
Component (2) comes from Update 1 (back edges). Component (3) comes from Update 2 (child returns). Together they ensure that low[u] captures the full "earliest reachable ancestor" information for the entire subtree rooted at u.
Interactive Animation: Watching Both Updates in Action
Below is a 6-node graph with both a back edge and a deep chain so you can see Update 1 (back edge) and Update 2 (child propagation) happen concretely. DFS starts from node 0. Follow each step — the description tells you exactly which update fires and why.
disc[v] — "where can I reach directly?" Child returns use low[v] — "what did my child's subtree discover?" This distinction is the heart of Tarjan's algorithm. Confusing the two is the #1 source of bugs in bridge/articulation-point code.
⚠ What Goes Wrong: A Concrete Articulation-Point Bug
Everything above might still feel theoretical. Let us now look at a specific graph where using low[v] instead of disc[v] for back edges produces the wrong answer for articulation points. This is the kind of counter-example an interviewer might construct.
Graph: Edges 0–1, 1–2, 2–3, 1–4, 4–5. Back edges: 3→0 and 5→1. DFS order: 0 → 1 → 2 → 3 → (back) → 4 → 5 → (back). Node 1 is highlighted red — is it an articulation point?
Reality check: If we remove node 1, nodes {4, 5} are completely cut off — the back edge 5→1 is useless because 1 is gone. So node 1 IS an articulation point.
✔ Correct: using disc[v] for back edges
3 back→0: low[3]=min(3,disc[0])=0
ret 3→2: low[2]=min(2,low[3])=0
ret 2→1: low[1]=min(1,low[2])=0
5 back→1: low[5]=min(5,disc[1])=1
ret 5→4: low[4]=min(4,low[5])=1
ret 4→1: low[1]=min(0,low[4])=0
AP check at node 1:
- Child 2: low[2]=0 < disc[1]=1 → ✔ OK
- Child 4: low[4]=1 ≥ disc[1]=1 → ⚠ YES!
Node 1 IS an articulation point. ✔ Correct!
✘ Wrong: using low[v] for back edges
3 back→0: low[3]=min(3,low[0])=0
ret 3→2: low[2]=min(2,low[3])=0
ret 2→1: low[1]=min(1,low[2])=0
5 back→1: low[5]=min(5,low[1])=0
ret 5→4: low[4]=min(4,low[5])=0
ret 4→1: low[1]=min(0,low[4])=0
AP check at node 1:
- Child 2: low[2]=0 < disc[1]=1 → ✔ OK
- Child 4: low[4]=0 < disc[1]=1 → OK?!
Node 1 is NOT flagged as AP. ✘ Wrong!
What happened? The critical moment is the line highlighted in red: when node 5 encounters its back edge to node 1, it used low[1]=0 instead of disc[1]=1. Node 1's low was already lowered to 0 by its earlier child (2→3→0). This made node 5 think: "I can reach node 0 via node 1!" — which is true only if node 1 exists. But for the articulation-point check, we ask: "What if node 1 is removed?" In that scenario, node 5 can only reach node 1's position — and node 1 is gone.
When node 5 sees a back edge to node 1, it can reach node 1 itself — nothing more. But
low[1]=0 encodes the fact that node 1's subtree (specifically the path 1→2→3→0) can reach node 0. If node 5 claims low[5]=0 by using low[1], it is implicitly saying "I can reach node 0 via 1's subtree." But that path goes through node 1. Remove node 1 and the path 5→1→…→0 is destroyed.
Using
disc[1]=1 is honest: "I can reach the node discovered at time 1 (which is node 1 itself), nothing further." This correctly means low[5]=1, and since low[4]=1 ≥ disc[1]=1, node 1 is flagged as an articulation point.
Interactive: Watch the Bug Happen Step-by-Step
Step through the DFS on the graph above. The right panel shows the low[] computation using both methods side-by-side so you can see exactly where they diverge.
| Node | disc | low (disc[v]) ✓ | low (low[v]) ✗ |
|---|---|---|---|
| 0 | – | – | – |
| 1 | – | – | – |
| 2 | – | – | – |
| 3 | – | – | – |
| 4 | – | – | – |
| 5 | – | – | – |
disc[v] and not low[v]?" the crisp answer is:
"A back edge from u to v proves u can reach v directly — not wherever v's subtree can reach.
disc[v] captures this precisely. Using low[v] would overcount reachability by borrowing information that v obtained through its own subtree — information that becomes invalid if v is removed (the articulation-point scenario). For bridges the bug is masked, but for articulation points it causes missed cut vertices."
How low values propagate: step-by-step
Let us trace exactly how low values are computed on a small graph. This is a chain 0 → 1 → 2 → 3 with one back edge from 3 to 0. The back edge creates a cycle, which means no edge here should be a bridge.
Contrast: what happens without a back edge
Now remove the back edge 3→0 from the same chain. Watch how low values do not propagate:
Without back edges, low[v] = disc[v] for every node. Every edge is a bridge because each child's low is strictly greater than its parent's disc.
- disc[v] = the order DFS visits node v (a timestamp)
- low[v] = the earliest ancestor reachable from v's subtree via back edges
- If a back edge exists, low values propagate upward during backtracking, making them smaller
- If no back edge exists, low[v] stays equal to disc[v], signaling that the subtree is isolated
The Bridge Condition
After computing disc and low arrays via DFS, the bridge detection rule is remarkably simple:
A tree edge (u, v) where u is the parent of v is a bridge if and only if:
Why does this work?
low[v] > disc[u] means the subtree rooted at v cannot reach node u or any of u's ancestors through back edges. The only connection from v's subtree to the rest of the graph is through the edge (u, v). Remove it and the subtree becomes disconnected.
Conversely, if low[v] ≤ disc[u], then some node in v's subtree has a back edge reaching u or an ancestor. Even without (u, v), there is still a path.
Bridge: low[v] > disc[u]
No back edges from v's subtree reaching u. Subtree is isolated without (u,v).
Not a Bridge: low[v] ≤ disc[u]
Back edge provides an alternate path. Removing (u,v) does not disconnect.
Complete Algorithm
C++ Implementation
parent = -1 trick ensures that if there are multiple edges between u and v, we only skip one of them. If we skip all, we might miss that duplicate edges prevent a bridge.
Step-by-Step Walkthrough
Let us trace the algorithm on a 7-node graph with exactly two bridges. Use the step buttons to advance through each DFS action.
Edge Cases and Pitfalls
1. Parallel (Multiple) Edges
If nodes u and v are connected by two edges, neither is a bridge (removing one still leaves the other). The standard parent-skip logic skips ALL edges to the parent, which is wrong for multigraphs.
parent = -1 trick shown in the implementation. After skipping one occurrence, set parent to -1 so subsequent edges to the same node are treated as back edges.
2. Self Loops
A self-loop (u, u) is never a bridge. Since v == parent when v == u, the standard algorithm naturally skips it. No special handling needed.
3. Disconnected Graphs
The outer loop (for each node u: if disc[u] == -1: dfs(u, -1)) handles disconnected components. Each component is processed independently.
4. Single Node / Single Edge
- Single node, no edges: No bridges. The algorithm does nothing meaningful.
- Two nodes, one edge: That edge is a bridge. disc[0]=0, disc[1]=1, low[1]=1. Since low[1]=1 > disc[0]=0, the edge is correctly identified.
5. A Tree (No Cycles)
Every edge in a tree is a bridge. Since trees have no back edges, low[v] = disc[v] for every node v. For every parent-child pair, low[child] = disc[child] > disc[parent], so every edge is flagged.
Time and Space Complexity
| Resource | Complexity | Explanation |
|---|---|---|
| Time | O(V + E) | Single DFS traversal. Each node visited once, each edge examined twice (once from each endpoint). |
| Space: disc[] and low[] | O(V) | Two integer arrays of size V. |
| Space: Recursion stack | O(V) worst case | For a path graph (chain), the DFS recursion depth equals V. |
| Space: Adjacency list | O(V + E) | Standard graph storage. |
| Total Space | O(V + E) | Dominated by the adjacency list. |
Why is it O(V + E) and not O(V × E)?
The naive approach checks connectivity after removing each edge, leading to O(E) work per edge. Tarjan's algorithm avoids this by encoding reachability information in the low-link values during a single DFS. The low values capture whether a subtree can "escape" via back edges, so we check the bridge condition in O(1) per edge as we backtrack.
Stack Overflow Risk
For very large graphs (V > 105), the recursive version may overflow the call stack. Solutions:
- Increase stack size (e.g.,
ulimit -s unlimitedon Linux, or create a thread with larger stack) - Convert to iterative DFS using an explicit stack
Dry Run on a Larger Graph
Let us trace through a 10-node graph to build confidence. This graph has 3 bridges.
Next: Articulation Points
Bridges and articulation points share the same DFS framework with disc/low arrays. The key difference is the condition: for articulation points we check low[v] ≥ disc[u] (with a special case for the root). The next page covers this in detail with its own step-through animations.