Practice Now
Graph Theory
Bridge-Finding Algorithms
Non-Recursive Methods
Computer Science
Data Structures

Finding bridges in graph without recursion

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms
AlgorithmsData Structures

Introduction

A bridge (or cut-edge) in an undirected graph is an edge whose removal disconnects the graph (or increases the number of connected components). The classic algorithm by Tarjan finds bridges using DFS with disc[] and low[] arrays. The recursive version is straightforward but can cause stack overflow on large graphs. An iterative version simulates the DFS call stack explicitly, achieving the same O(V + E) time complexity without recursion depth limits.

Recursive Bridge Finding (Tarjan's Algorithm)

The recursive version for reference:

python
1def find_bridges_recursive(graph, n):
2    disc = [-1] * n
3    low = [-1] * n
4    bridges = []
5    timer = [0]
6
7    def dfs(u, parent):
8        disc[u] = low[u] = timer[0]
9        timer[0] += 1
10
11        for v in graph[u]:
12            if disc[v] == -1:  # Not visited
13                dfs(v, u)
14                low[u] = min(low[u], low[v])
15                if low[v] > disc[u]:
16                    bridges.append((u, v))
17            elif v != parent:
18                low[u] = min(low[u], disc[v])
19
20    for i in range(n):
21        if disc[i] == -1:
22            dfs(i, -1)
23
24    return bridges

This works but fails on graphs with thousands of vertices due to Python's default recursion limit of 1000.

Iterative Bridge Finding

The iterative version uses an explicit stack to simulate DFS:

python
1def find_bridges_iterative(graph, n):
2    disc = [-1] * n
3    low = [-1] * n
4    parent = [-1] * n
5    bridges = []
6    timer = 0
7
8    for start in range(n):
9        if disc[start] != -1:
10            continue
11
12        # Stack stores (node, iterator_over_neighbors)
13        stack = [(start, iter(graph[start]))]
14        disc[start] = low[start] = timer
15        timer += 1
16
17        while stack:
18            u, neighbors = stack[-1]
19            try:
20                v = next(neighbors)
21                if disc[v] == -1:
22                    # Tree edge: visit v
23                    parent[v] = u
24                    disc[v] = low[v] = timer
25                    timer += 1
26                    stack.append((v, iter(graph[v])))
27                elif v != parent[u]:
28                    # Back edge: update low
29                    low[u] = min(low[u], disc[v])
30            except StopIteration:
31                # All neighbors processed — backtrack
32                stack.pop()
33                if stack:
34                    u_parent = stack[-1][0]
35                    low[u_parent] = min(low[u_parent], low[u])
36                    if low[u] > disc[u_parent]:
37                        bridges.append((u_parent, u))
38
39    return bridges

How It Works

The key insight is that the DFS recursion stack is simulated explicitly:

  1. Push the starting node with an iterator over its neighbors
  2. For each node on the stack, advance to the next unvisited neighbor
  3. When a neighbor is visited (tree edge), push it onto the stack
  4. When a neighbor is already visited (back edge), update low[u]
  5. When all neighbors are exhausted (StopIteration), pop the node and propagate low values to the parent
  6. Check the bridge condition (low[v] > disc[u]) during backtracking

Example Usage

python
1# Build adjacency list
2def build_graph(n, edges):
3    graph = [[] for _ in range(n)]
4    for u, v in edges:
5        graph[u].append(v)
6        graph[v].append(u)
7    return graph
8
9# Example graph:
10# 0---1---2---3---4
11#             |   |
12#             +---5
13edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (3, 5)]
14graph = build_graph(6, edges)
15
16bridges = find_bridges_iterative(graph, 6)
17print(bridges)  # [(0, 1), (1, 2)]
18# Edge (0,1) and (1,2) are bridges
19# Edges (2,3), (3,4), (4,5), (3,5) form a cycle — not bridges

Handling Multigraphs (Parallel Edges)

The basic algorithm breaks with parallel edges (multiple edges between the same pair). Track edge indices instead of just parent nodes:

python
1def find_bridges_multigraph(graph_edges, n, m):
2    # graph_edges[u] = [(v, edge_index), ...]
3    disc = [-1] * n
4    low = [-1] * n
5    bridges = []
6    timer = 0
7
8    for start in range(n):
9        if disc[start] != -1:
10            continue
11
12        stack = [(start, iter(graph_edges[start]), -1)]  # (node, neighbors, parent_edge_idx)
13        disc[start] = low[start] = timer
14        timer += 1
15
16        while stack:
17            u, neighbors, parent_edge = stack[-1]
18            try:
19                v, edge_idx = next(neighbors)
20                if edge_idx == parent_edge:
21                    continue  # Skip the edge we came from
22                if disc[v] == -1:
23                    disc[v] = low[v] = timer
24                    timer += 1
25                    stack.append((v, iter(graph_edges[v]), edge_idx))
26                else:
27                    low[u] = min(low[u], disc[v])
28            except StopIteration:
29                stack.pop()
30                if stack:
31                    parent_node = stack[-1][0]
32                    low[parent_node] = min(low[parent_node], low[u])
33                    if low[u] > disc[parent_node]:
34                        bridges.append((parent_node, u))
35
36    return bridges

Performance

Both recursive and iterative versions have the same time and space complexity:

MetricComplexity
TimeO(V + E)
SpaceO(V + E) for adjacency list + O(V) for stack

The iterative version avoids Python's recursion limit and uses heap memory (which is much larger) instead of the call stack.

python
1# Increase recursion limit for the recursive version (not recommended for production)
2import sys
3sys.setrecursionlimit(100000)
4
5# Better: use the iterative version for large graphs

Common Pitfalls

  • Not handling disconnected graphs: The algorithm must loop over all vertices and start DFS from each unvisited one. A single DFS call from vertex 0 misses components not connected to vertex 0.
  • Using parent node instead of parent edge for multigraphs: In graphs with parallel edges between u and v, checking v != parent[u] incorrectly skips valid back edges. Track the edge index of the parent edge instead.
  • Forgetting to propagate low values during backtracking: When popping a node from the stack, its low value must be propagated to its parent. Missing this step means the parent never learns about back edges in the subtree, causing false bridge detections.
  • Modifying the iterator during iteration: The stack stores iterators over neighbor lists. If the graph's adjacency list is modified during the algorithm, iterators become invalid. Build the graph before starting the algorithm.
  • Python's recursion limit: Python defaults to 1000 recursive calls. The recursive Tarjan's algorithm crashes on graphs with more than 1000 vertices. Use the iterative version or sys.setrecursionlimit() (less safe).

Summary

  • A bridge is an edge whose removal disconnects the graph
  • Tarjan's algorithm finds all bridges in O(V + E) using disc[] and low[] arrays
  • The iterative version simulates the DFS call stack with an explicit stack of (node, neighbor_iterator) pairs
  • An edge (u, v) is a bridge if low[v] > disc[u] (no back edge from v's subtree reaches u or above)
  • Use edge indices instead of parent nodes to correctly handle multigraphs
  • The iterative version avoids stack overflow on large graphs (10K+ vertices)
Related reading
Course
Intermediate
27 lessons
15 hours
DSA Fundamentals

Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.

View the course
Track what you have practised

A free account saves your progress, solutions and study plan across every problem on Codemia.

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms
Codemia
© 2026 Codemia
Resources
Legal
Social
All Rights Reserved.