Finding bridges in graph without recursion

Graph Theory

Bridge-Finding Algorithms

Non-Recursive Methods

Computer Science

Data Structures

Finding bridges in graph without recursion

Master System Design with Codemia

Enhance your system design skills with over 120 practice problems, detailed solutions, and hands-on exercises.

Start Practicing Learn More

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:

Push the starting node with an iterator over its neighbors
For each node on the stack, advance to the next unvisited neighbor
When a neighbor is visited (tree edge), push it onto the stack
When a neighbor is already visited (back edge), update low[u]
When all neighbors are exhausted (StopIteration), pop the node and propagate low values to the parent
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:

Metric	Complexity
Time	O(V + E)
Space	O(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)