Bridges in Graph: Finding Cut Edges
A bridge (or cut edge) in an undirected graph is an edge whose removal increases the number of connected components. Put simply, if you delete a bridge, you split the graph into two or more...
Key Insights
- A bridge is an edge whose removal disconnects the graph—identifying these critical edges is essential for network reliability analysis and infrastructure planning.
- Tarjan’s algorithm finds all bridges in O(V + E) time using a single DFS traversal, compared to the naive O(E × (V + E)) brute force approach.
- The key insight is comparing discovery times and low-link values: edge (u, v) is a bridge if low[v] > disc[u], meaning v cannot reach any ancestor of u through an alternate path.
Introduction to Bridges
A bridge (or cut edge) in an undirected graph is an edge whose removal increases the number of connected components. Put simply, if you delete a bridge, you split the graph into two or more disconnected pieces.
Consider a network of servers connected by cables. Some cables are redundant—multiple paths exist between the servers they connect. Others are critical: if that single cable fails, entire sections of your network become unreachable. Those critical cables are bridges.
Identifying bridges matters in several domains:
- Network reliability: Finding single points of failure in communication networks
- Infrastructure planning: Identifying critical roads, power lines, or pipelines
- Social network analysis: Discovering connections that hold communities together
- Circuit design: Finding edges that, if broken, disconnect circuit components
Naive Approach: Brute Force Detection
The straightforward approach is intuitive: remove each edge, check if the graph is still connected, then restore the edge. If removing an edge disconnects the graph, it’s a bridge.
from collections import defaultdict, deque
def is_connected(graph, num_vertices, excluded_edge):
"""Check if graph remains connected when excluding one edge."""
if num_vertices == 0:
return True
# Find a starting vertex that exists in the graph
start = next(iter(graph.keys()), None)
if start is None:
return True
visited = set()
queue = deque([start])
visited.add(start)
while queue:
node = queue.popleft()
for neighbor in graph[node]:
edge = tuple(sorted([node, neighbor]))
if edge == excluded_edge:
continue
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# Check if all vertices with edges are reachable
all_vertices = set(graph.keys())
return visited == all_vertices
def find_bridges_brute_force(graph, num_vertices):
"""Find bridges by removing each edge and checking connectivity."""
bridges = []
checked_edges = set()
for u in graph:
for v in graph[u]:
edge = tuple(sorted([u, v]))
if edge in checked_edges:
continue
checked_edges.add(edge)
if not is_connected(graph, num_vertices, edge):
bridges.append((u, v))
return bridges
# Example usage
graph = defaultdict(list)
edges = [(0, 1), (1, 2), (2, 0), (1, 3), (3, 4), (4, 5), (5, 3)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
print(find_bridges_brute_force(graph, 6)) # Output: [(1, 3)]
This works, but the time complexity is brutal: O(E × (V + E)). For each of the E edges, we run a BFS/DFS that takes O(V + E). On large graphs, this becomes impractical.
Tarjan’s Bridge-Finding Algorithm
Robert Tarjan developed an elegant algorithm that finds all bridges in a single DFS traversal, achieving O(V + E) time complexity. The algorithm relies on two key concepts:
Discovery time (disc[v]): When vertex v was first visited during DFS. Vertices discovered earlier have lower discovery times.
Low-link value (low[v]): The minimum discovery time reachable from the subtree rooted at v, including back edges. This tells us how “far back” in the DFS tree we can reach.
The critical insight: an edge (u, v) where u is the parent of v in the DFS tree is a bridge if and only if low[v] > disc[u]. This condition means that from v’s subtree, there’s no back edge reaching u or any of u’s ancestors. Without such a back edge, removing (u, v) disconnects v’s subtree from the rest of the graph.
from collections import defaultdict
class BridgeFinder:
def __init__(self, num_vertices):
self.V = num_vertices
self.graph = defaultdict(list)
self.time = 0
def add_edge(self, u, v):
self.graph[u].append(v)
self.graph[v].append(u)
def find_bridges(self):
visited = [False] * self.V
disc = [float('inf')] * self.V
low = [float('inf')] * self.V
parent = [-1] * self.V
bridges = []
def dfs(u):
visited[u] = True
disc[u] = self.time
low[u] = self.time
self.time += 1
for v in self.graph[u]:
if not visited[v]:
parent[v] = u
dfs(v)
# After DFS returns, update low[u] based on subtree
low[u] = min(low[u], low[v])
# Bridge condition: no back edge from v's subtree to u or above
if low[v] > disc[u]:
bridges.append((u, v))
elif v != parent[u]:
# Back edge found - update low[u]
low[u] = min(low[u], disc[v])
# Handle disconnected graphs
for i in range(self.V):
if not visited[i]:
dfs(i)
return bridges
# Example
g = BridgeFinder(6)
for u, v in [(0, 1), (1, 2), (2, 0), (1, 3), (3, 4), (4, 5), (5, 3)]:
g.add_edge(u, v)
print(g.find_bridges()) # Output: [(1, 3)]
Step-by-Step Walkthrough
Let’s trace through the algorithm with a debug version to see exactly how discovery times and low-link values propagate:
from collections import defaultdict
def find_bridges_debug(num_vertices, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = [False] * num_vertices
disc = [0] * num_vertices
low = [0] * num_vertices
parent = [-1] * num_vertices
bridges = []
time = [0] # Using list to allow modification in nested function
def dfs(u, depth=0):
indent = " " * depth
visited[u] = True
disc[u] = low[u] = time[0]
time[0] += 1
print(f"{indent}Visiting {u}: disc[{u}]={disc[u]}, low[{u}]={low[u]}")
for v in graph[u]:
if not visited[v]:
parent[v] = u
print(f"{indent} Exploring tree edge ({u}, {v})")
dfs(v, depth + 1)
old_low = low[u]
low[u] = min(low[u], low[v])
print(f"{indent} Returned from {v}: low[{u}] updated {old_low} -> {low[u]}")
if low[v] > disc[u]:
print(f"{indent} *** BRIDGE FOUND: ({u}, {v}) ***")
print(f"{indent} Reason: low[{v}]={low[v]} > disc[{u}]={disc[u]}")
bridges.append((u, v))
elif v != parent[u]:
old_low = low[u]
low[u] = min(low[u], disc[v])
print(f"{indent} Back edge ({u}, {v}): low[{u}] updated {old_low} -> {low[u]}")
for i in range(num_vertices):
if not visited[i]:
print(f"\n=== Starting DFS from vertex {i} ===")
dfs(i)
print(f"\nFinal disc values: {disc}")
print(f"Final low values: {low}")
return bridges
# Graph: 0--1--3--4
# | | |
# +--2 5--+
edges = [(0, 1), (1, 2), (2, 0), (1, 3), (3, 4), (4, 5), (5, 3)]
bridges = find_bridges_debug(6, edges)
print(f"\nBridges: {bridges}")
Running this produces output showing how vertex 3’s low-link value cannot reach back to vertex 1’s discovery time, confirming edge (1, 3) is a bridge.
Handling Edge Cases
Production code must handle several edge cases that the basic implementation ignores:
from collections import defaultdict
import sys
sys.setrecursionlimit(100000) # For large graphs
class RobustBridgeFinder:
def __init__(self):
self.graph = defaultdict(list)
self.vertices = set()
def add_edge(self, u, v):
# Skip self-loops - they can never be bridges
if u == v:
return
self.graph[u].append(v)
self.graph[v].append(u)
self.vertices.add(u)
self.vertices.add(v)
def find_bridges(self):
if len(self.vertices) <= 1:
return []
# Map vertices to contiguous indices for array-based storage
vertex_list = list(self.vertices)
vertex_to_idx = {v: i for i, v in enumerate(vertex_list)}
n = len(vertex_list)
visited = [False] * n
disc = [0] * n
low = [0] * n
bridges = []
time = [0]
def dfs(u_idx, parent_idx):
visited[u_idx] = True
disc[u_idx] = low[u_idx] = time[0]
time[0] += 1
u = vertex_list[u_idx]
# Track edge count to handle parallel edges
parent_edge_used = False
for v in self.graph[u]:
v_idx = vertex_to_idx[v]
if not visited[v_idx]:
dfs(v_idx, u_idx)
low[u_idx] = min(low[u_idx], low[v_idx])
if low[v_idx] > disc[u_idx]:
bridges.append((u, v))
elif v_idx == parent_idx and not parent_edge_used:
# First parent edge - skip it (tree edge going back)
parent_edge_used = True
else:
# Back edge or parallel edge to parent
low[u_idx] = min(low[u_idx], disc[v_idx])
# Handle disconnected components
for i in range(n):
if not visited[i]:
dfs(i, -1)
return bridges
# Test edge cases
finder = RobustBridgeFinder()
# Parallel edges: edge (0,1) appears twice - not a bridge
finder.add_edge(0, 1)
finder.add_edge(0, 1)
finder.add_edge(1, 2)
print(f"Bridges with parallel edge: {finder.find_bridges()}")
# Output: [(1, 2)] - only (1,2) is a bridge, not (0,1)
For directed graphs, the problem changes entirely—you’re looking for edges whose removal affects strong connectivity, which requires a different algorithm.
Practical Applications
Here’s a realistic example: analyzing a network topology to identify single points of failure.
from collections import defaultdict
class NetworkAnalyzer:
def __init__(self):
self.connections = defaultdict(list)
self.node_names = {}
self.name_to_id = {}
self.next_id = 0
def add_connection(self, node_a, node_b, link_name=None):
"""Add a network connection between two nodes."""
for node in [node_a, node_b]:
if node not in self.name_to_id:
self.name_to_id[node] = self.next_id
self.node_names[self.next_id] = node
self.next_id += 1
id_a, id_b = self.name_to_id[node_a], self.name_to_id[node_b]
self.connections[id_a].append((id_b, link_name))
self.connections[id_b].append((id_a, link_name))
def find_critical_links(self):
"""Find all connections that would partition the network if they fail."""
if self.next_id <= 1:
return []
visited = [False] * self.next_id
disc = [0] * self.next_id
low = [0] * self.next_id
critical = []
time = [0]
def dfs(u, parent):
visited[u] = True
disc[u] = low[u] = time[0]
time[0] += 1
for v, link_name in self.connections[u]:
if not visited[v]:
dfs(v, u)
low[u] = min(low[u], low[v])
if low[v] > disc[u]:
critical.append({
'from': self.node_names[u],
'to': self.node_names[v],
'link': link_name,
'severity': 'CRITICAL'
})
elif v != parent:
low[u] = min(low[u], disc[v])
for i in range(self.next_id):
if not visited[i]:
dfs(i, -1)
return critical
# Analyze a data center network
network = NetworkAnalyzer()
network.add_connection("core-switch-1", "core-switch-2", "trunk-1")
network.add_connection("core-switch-1", "agg-switch-1", "uplink-1")
network.add_connection("core-switch-2", "agg-switch-1", "uplink-2")
network.add_connection("agg-switch-1", "edge-switch-1", "downlink-1")
network.add_connection("edge-switch-1", "server-rack-1", "server-link")
critical_links = network.find_critical_links()
for link in critical_links:
print(f"[{link['severity']}] {link['from']} <-> {link['to']}")
Complexity Analysis & Optimization Tips
Time Complexity: O(V + E) — each vertex and edge is visited exactly once during the DFS traversal.
Space Complexity: O(V) for the arrays storing discovery times, low-link values, and visited status, plus O(V) for the recursion stack in the worst case (a linear graph).
For large graphs, consider these optimizations:
- Iterative DFS: Replace recursion with an explicit stack to avoid stack overflow on deep graphs
- Memory-mapped structures: For graphs that don’t fit in memory, use memory-mapped arrays
- Parallel processing: For disconnected graphs, process each component in parallel
For dynamic graphs where edges are added or removed, maintaining bridges incrementally is complex. Research structures like link-cut trees can help, but for most practical cases, re-running Tarjan’s algorithm after batched updates is simpler and fast enough.