Find Bridges in a Graph

Find all bridges (critical edges) in an undirected graph using Tarjan's algorithm

Language Selection

Choose your preferred programming language

Showing: Python

Find Bridges in a Graph

Problem Statement

Given an undirected connected graph, find all bridges in the graph. A bridge (or cut edge) is an edge whose removal increases the number of connected components in the graph.

In network analysis, bridges represent critical connections - removing them would disconnect parts of the network, making them important for network reliability.

Input/Output Specifications

Input: An undirected graph represented as:
- n vertices (numbered 0 to n-1)
- List of edges connections where each edge is [u, v]
Output: List of all bridges as pairs [u, v]

Constraints

1 <= n <= 10^5
n-1 <= connections.length <= 10^5
0 <= connections[i][0], connections[i][1] < n
connections[i][0] != connections[i][1]
No duplicate edges

Examples

Example 1:

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation:
Graph: 0---1---3
       |   |
       2---/
Bridge: 1-3 (removing it disconnects vertex 3)

Example 2:

Input: n = 2, connections = [[0,1]]
Output: [[0,1]]
Explanation:
Graph: 0---1
The only edge is a bridge

Example 3:

Input: n = 6, connections = [[0,1],[1,2],[2,0],[1,3],[3,4],[4,5],[5,3]]
Output: [[1,3]]
Explanation:
Graph has two components connected by bridge 1-3
Component 1: triangle 0-1-2
Component 2: triangle 3-4-5

Solution Approaches

Approach 1: Tarjan’s Algorithm with DFS (Optimal)

Algorithm Explanation:

Use DFS to traverse the graph and assign discovery times
For each vertex, calculate low-link value (lowest discovery time reachable)
An edge (u,v) is a bridge if low[v] > disc[u] (v cannot reach back to u’s ancestors)
Use parent tracking to avoid false positives from direct parent edges

Implementation:

Python:

def find_bridges(n, connections):
    """
    Find all bridges using Tarjan's algorithm
    Time: O(V + E)
    Space: O(V)
    """
    from collections import defaultdict
    
    # Build adjacency list
    graph = defaultdict(list)
    for u, v in connections:
        graph[u].append(v)
        graph[v].append(u)
    
    # Initialize arrays
    disc = [-1] * n  # Discovery times
    low = [-1] * n   # Low-link values
    parent = [-1] * n  # Parent in DFS tree
    visited = [False] * n
    bridges = []
    time = [0]  # Use list to make it mutable in nested function
    
    def dfs(u):
        # Mark current vertex as visited
        visited[u] = True
        disc[u] = low[u] = time[0]
        time[0] += 1
        
        # Visit all adjacent vertices
        for v in graph[u]:
            if not visited[v]:
                # v is not visited, make it child of u in DFS tree
                parent[v] = u
                dfs(v)
                
                # Update low value of u for parent function calls
                low[u] = min(low[u], low[v])
                
                # If low[v] > disc[u], then u-v is a bridge
                if low[v] > disc[u]:
                    bridges.append([u, v])
            
            elif v != parent[u]:  # Back edge (not parent)
                # Update low value of u
                low[u] = min(low[u], disc[v])
    
    # Call DFS from all unvisited vertices (handles disconnected components)
    for i in range(n):
        if not visited[i]:
            dfs(i)
    
    return bridges

def find_bridges_iterative(n, connections):
    """
    Iterative implementation to avoid recursion stack overflow
    Time: O(V + E)
    Space: O(V)
    """
    from collections import defaultdict
    
    graph = defaultdict(list)
    for u, v in connections:
        graph[u].append(v)
        graph[v].append(u)
    
    disc = [-1] * n
    low = [-1] * n
    parent = [-1] * n
    visited = [False] * n
    bridges = []
    time = 0
    
    for start in range(n):
        if visited[start]:
            continue
        
        stack = [start]
        path = []
        
        while stack:
            u = stack[-1]
            
            if not visited[u]:
                visited[u] = True
                disc[u] = low[u] = time
                time += 1
                path.append(u)
            
            # Find next unvisited neighbor
            next_vertex = None
            for v in graph[u]:
                if not visited[v]:
                    next_vertex = v
                    break
            
            if next_vertex is not None:
                parent[next_vertex] = u
                stack.append(next_vertex)
            else:
                # Backtrack
                stack.pop()
                if path and path[-1] == u:
                    path.pop()
                
                # Update low values and check for bridges
                for v in graph[u]:
                    if v != parent[u]:
                        if visited[v] and disc[v] < disc[u]:
                            # Back edge
                            low[u] = min(low[u], disc[v])
                        elif parent[v] == u:
                            # Tree edge
                            low[u] = min(low[u], low[v])
                            if low[v] > disc[u]:
                                bridges.append([u, v])
    
    return bridges

Java:

class Solution {
    /**
     * Find all bridges using Tarjan's algorithm
     * Time: O(V + E)
     * Space: O(V)
     */
    public List<List<Integer>> findBridges(int n, int[][] connections) {
        // Build adjacency list
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        
        for (int[] edge : connections) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        
        int[] disc = new int[n];
        int[] low = new int[n];
        int[] parent = new int[n];
        boolean[] visited = new boolean[n];
        List<List<Integer>> bridges = new ArrayList<>();
        
        Arrays.fill(disc, -1);
        Arrays.fill(low, -1);
        Arrays.fill(parent, -1);
        
        int[] time = {0};
        
        // Call DFS for all unvisited vertices
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                bridgeUtil(i, graph, disc, low, parent, visited, bridges, time);
            }
        }
        
        return bridges;
    }
    
    private void bridgeUtil(int u, List<List<Integer>> graph, int[] disc, int[] low,
                           int[] parent, boolean[] visited, List<List<Integer>> bridges, int[] time) {
        visited[u] = true;
        disc[u] = low[u] = time[0]++;
        
        for (int v : graph.get(u)) {
            if (!visited[v]) {
                parent[v] = u;
                bridgeUtil(v, graph, disc, low, parent, visited, bridges, time);
                
                // Update low value
                low[u] = Math.min(low[u], low[v]);
                
                // Check if edge u-v is a bridge
                if (low[v] > disc[u]) {
                    bridges.add(Arrays.asList(u, v));
                }
            } else if (v != parent[u]) {
                // Back edge
                low[u] = Math.min(low[u], disc[v]);
            }
        }
    }
    
    // Alternative with cleaner structure
    public List<List<Integer>> findBridgesClean(int n, int[][] connections) {
        List<List<Integer>> graph = buildGraph(n, connections);
        TarjanBridges tarjan = new TarjanBridges(n);
        return tarjan.findBridges(graph);
    }
    
    private List<List<Integer>> buildGraph(int n, int[][] connections) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        
        for (int[] edge : connections) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        
        return graph;
    }
    
    class TarjanBridges {
        private int[] disc, low, parent;
        private boolean[] visited;
        private List<List<Integer>> bridges;
        private int time;
        
        public TarjanBridges(int n) {
            disc = new int[n];
            low = new int[n];
            parent = new int[n];
            visited = new boolean[n];
            bridges = new ArrayList<>();
            time = 0;
            
            Arrays.fill(disc, -1);
            Arrays.fill(low, -1);
            Arrays.fill(parent, -1);
        }
        
        public List<List<Integer>> findBridges(List<List<Integer>> graph) {
            int n = graph.size();
            for (int i = 0; i < n; i++) {
                if (!visited[i]) {
                    dfs(i, graph);
                }
            }
            return bridges;
        }
        
        private void dfs(int u, List<List<Integer>> graph) {
            visited[u] = true;
            disc[u] = low[u] = time++;
            
            for (int v : graph.get(u)) {
                if (!visited[v]) {
                    parent[v] = u;
                    dfs(v, graph);
                    low[u] = Math.min(low[u], low[v]);
                    
                    if (low[v] > disc[u]) {
                        bridges.add(Arrays.asList(u, v));
                    }
                } else if (v != parent[u]) {
                    low[u] = Math.min(low[u], disc[v]);
                }
            }
        }
    }
}

Go:

// findBridges - Find all bridges using Tarjan's algorithm
// Time: O(V + E)
// Space: O(V)
func findBridges(n int, connections [][]int) [][]int {
    // Build adjacency list
    graph := make([][]int, n)
    for _, edge := range connections {
        u, v := edge[0], edge[1]
        graph[u] = append(graph[u], v)
        graph[v] = append(graph[v], u)
    }
    
    disc := make([]int, n)
    low := make([]int, n)
    parent := make([]int, n)
    visited := make([]bool, n)
    bridges := [][]int{}
    time := 0
    
    // Initialize arrays
    for i := 0; i < n; i++ {
        disc[i] = -1
        low[i] = -1
        parent[i] = -1
    }
    
    var dfs func(u int)
    dfs = func(u int) {
        visited[u] = true
        disc[u] = time
        low[u] = time
        time++
        
        for _, v := range graph[u] {
            if !visited[v] {
                parent[v] = u
                dfs(v)
                
                // Update low value
                if low[v] < low[u] {
                    low[u] = low[v]
                }
                
                // Check if edge u-v is a bridge
                if low[v] > disc[u] {
                    bridges = append(bridges, []int{u, v})
                }
            } else if v != parent[u] {
                // Back edge
                if disc[v] < low[u] {
                    low[u] = disc[v]
                }
            }
        }
    }
    
    // Call DFS for all unvisited vertices
    for i := 0; i < n; i++ {
        if !visited[i] {
            dfs(i)
        }
    }
    
    return bridges
}

// TarjanBridges struct for cleaner implementation
type TarjanBridges struct {
    disc, low, parent []int
    visited           []bool
    bridges          [][]int
    time             int
}

func NewTarjanBridges(n int) *TarjanBridges {
    tb := &TarjanBridges{
        disc:    make([]int, n),
        low:     make([]int, n),
        parent:  make([]int, n),
        visited: make([]bool, n),
        bridges: [][]int{},
        time:    0,
    }
    
    for i := 0; i < n; i++ {
        tb.disc[i] = -1
        tb.low[i] = -1
        tb.parent[i] = -1
    }
    
    return tb
}

func (tb *TarjanBridges) FindBridges(graph [][]int) [][]int {
    n := len(graph)
    for i := 0; i < n; i++ {
        if !tb.visited[i] {
            tb.dfs(i, graph)
        }
    }
    return tb.bridges
}

func (tb *TarjanBridges) dfs(u int, graph [][]int) {
    tb.visited[u] = true
    tb.disc[u] = tb.time
    tb.low[u] = tb.time
    tb.time++
    
    for _, v := range graph[u] {
        if !tb.visited[v] {
            tb.parent[v] = u
            tb.dfs(v, graph)
            
            tb.low[u] = min(tb.low[u], tb.low[v])
            
            if tb.low[v] > tb.disc[u] {
                tb.bridges = append(tb.bridges, []int{u, v})
            }
        } else if v != tb.parent[u] {
            tb.low[u] = min(tb.low[u], tb.disc[v])
        }
    }
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

JavaScript:

/**
 * Find all bridges using Tarjan's algorithm
 * Time: O(V + E)
 * Space: O(V)
 */
function findBridges(n, connections) {
    // Build adjacency list
    const graph = Array.from({length: n}, () => []);
    for (const [u, v] of connections) {
        graph[u].push(v);
        graph[v].push(u);
    }
    
    const disc = new Array(n).fill(-1);
    const low = new Array(n).fill(-1);
    const parent = new Array(n).fill(-1);
    const visited = new Array(n).fill(false);
    const bridges = [];
    let time = 0;
    
    function dfs(u) {
        visited[u] = true;
        disc[u] = low[u] = time++;
        
        for (const v of graph[u]) {
            if (!visited[v]) {
                parent[v] = u;
                dfs(v);
                
                // Update low value
                low[u] = Math.min(low[u], low[v]);
                
                // Check if edge u-v is a bridge
                if (low[v] > disc[u]) {
                    bridges.push([u, v]);
                }
            } else if (v !== parent[u]) {
                // Back edge
                low[u] = Math.min(low[u], disc[v]);
            }
        }
    }
    
    // Call DFS for all unvisited vertices
    for (let i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i);
        }
    }
    
    return bridges;
}

/**
 * Class-based implementation for better organization
 */
class TarjanBridges {
    constructor(n) {
        this.n = n;
        this.disc = new Array(n).fill(-1);
        this.low = new Array(n).fill(-1);
        this.parent = new Array(n).fill(-1);
        this.visited = new Array(n).fill(false);
        this.bridges = [];
        this.time = 0;
    }
    
    findBridges(graph) {
        for (let i = 0; i < this.n; i++) {
            if (!this.visited[i]) {
                this.dfs(i, graph);
            }
        }
        return this.bridges;
    }
    
    dfs(u, graph) {
        this.visited[u] = true;
        this.disc[u] = this.low[u] = this.time++;
        
        for (const v of graph[u]) {
            if (!this.visited[v]) {
                this.parent[v] = u;
                this.dfs(v, graph);
                
                this.low[u] = Math.min(this.low[u], this.low[v]);
                
                if (this.low[v] > this.disc[u]) {
                    this.bridges.push([u, v]);
                }
            } else if (v !== this.parent[u]) {
                this.low[u] = Math.min(this.low[u], this.disc[v]);
            }
        }
    }
}

// Usage
function findBridgesWithClass(n, connections) {
    const graph = Array.from({length: n}, () => []);
    for (const [u, v] of connections) {
        graph[u].push(v);
        graph[v].push(u);
    }
    
    const tarjan = new TarjanBridges(n);
    return tarjan.findBridges(graph);
}

// Alternative iterative approach
function findBridgesIterative(n, connections) {
    const graph = Array.from({length: n}, () => []);
    for (const [u, v] of connections) {
        graph[u].push(v);
        graph[v].push(u);
    }
    
    const disc = new Array(n).fill(-1);
    const low = new Array(n).fill(-1);
    const parent = new Array(n).fill(-1);
    const visited = new Array(n).fill(false);
    const bridges = [];
    let time = 0;
    
    for (let start = 0; start < n; start++) {
        if (visited[start]) continue;
        
        const stack = [{node: start, neighbors: [...graph[start]], index: 0}];
        const path = [];
        
        while (stack.length > 0) {
            const current = stack[stack.length - 1];
            const u = current.node;
            
            if (!visited[u]) {
                visited[u] = true;
                disc[u] = low[u] = time++;
                path.push(u);
            }
            
            if (current.index < current.neighbors.length) {
                const v = current.neighbors[current.index++];
                
                if (!visited[v]) {
                    parent[v] = u;
                    stack.push({node: v, neighbors: [...graph[v]], index: 0});
                } else if (v !== parent[u]) {
                    low[u] = Math.min(low[u], disc[v]);
                }
            } else {
                // Backtrack
                stack.pop();
                
                // Update low values and check bridges
                for (const v of graph[u]) {
                    if (parent[v] === u) {
                        low[u] = Math.min(low[u], low[v]);
                        if (low[v] > disc[u]) {
                            bridges.push([u, v]);
                        }
                    }
                }
            }
        }
    }
    
    return bridges;
}

C#:

public class Solution {
    /// <summary>
    /// Find all bridges using Tarjan's algorithm
    /// Time: O(V + E)
    /// Space: O(V)
    /// </summary>
    public IList<IList<int>> FindBridges(int n, int[][] connections) {
        // Build adjacency list
        var graph = new List<int>[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
        }
        
        foreach (var edge in connections) {
            graph[edge[0]].Add(edge[1]);
            graph[edge[1]].Add(edge[0]);
        }
        
        int[] disc = new int[n];
        int[] low = new int[n];
        int[] parent = new int[n];
        bool[] visited = new bool[n];
        var bridges = new List<IList<int>>();
        
        Array.Fill(disc, -1);
        Array.Fill(low, -1);
        Array.Fill(parent, -1);
        
        int time = 0;
        
        // Call DFS for all unvisited vertices
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                BridgeUtil(i, graph, disc, low, parent, visited, bridges, ref time);
            }
        }
        
        return bridges;
    }
    
    private void BridgeUtil(int u, List<int>[] graph, int[] disc, int[] low,
                           int[] parent, bool[] visited, IList<IList<int>> bridges, ref int time) {
        visited[u] = true;
        disc[u] = low[u] = time++;
        
        foreach (int v in graph[u]) {
            if (!visited[v]) {
                parent[v] = u;
                BridgeUtil(v, graph, disc, low, parent, visited, bridges, ref time);
                
                // Update low value
                low[u] = Math.Min(low[u], low[v]);
                
                // Check if edge u-v is a bridge
                if (low[v] > disc[u]) {
                    bridges.Add(new List<int> { u, v });
                }
            } else if (v != parent[u]) {
                // Back edge
                low[u] = Math.Min(low[u], disc[v]);
            }
        }
    }
    
    /// <summary>
    /// Class-based implementation for better organization
    /// </summary>
    public class TarjanBridges {
        private int[] disc, low, parent;
        private bool[] visited;
        private IList<IList<int>> bridges;
        private int time;
        
        public TarjanBridges(int n) {
            disc = new int[n];
            low = new int[n];
            parent = new int[n];
            visited = new bool[n];
            bridges = new List<IList<int>>();
            time = 0;
            
            Array.Fill(disc, -1);
            Array.Fill(low, -1);
            Array.Fill(parent, -1);
        }
        
        public IList<IList<int>> FindBridges(List<int>[] graph) {
            int n = graph.Length;
            for (int i = 0; i < n; i++) {
                if (!visited[i]) {
                    Dfs(i, graph);
                }
            }
            return bridges;
        }
        
        private void Dfs(int u, List<int>[] graph) {
            visited[u] = true;
            disc[u] = low[u] = time++;
            
            foreach (int v in graph[u]) {
                if (!visited[v]) {
                    parent[v] = u;
                    Dfs(v, graph);
                    low[u] = Math.Min(low[u], low[v]);
                    
                    if (low[v] > disc[u]) {
                        bridges.Add(new List<int> { u, v });
                    }
                } else if (v != parent[u]) {
                    low[u] = Math.Min(low[u], disc[v]);
                }
            }
        }
    }
    
    // LINQ-based graph building
    public IList<IList<int>> FindBridgesLinq(int n, int[][] connections) {
        var graph = Enumerable.Range(0, n).Select(_ => new List<int>()).ToArray();
        
        foreach (var edge in connections) {
            graph[edge[0]].Add(edge[1]);
            graph[edge[1]].Add(edge[0]);
        }
        
        var tarjan = new TarjanBridges(n);
        return tarjan.FindBridges(graph);
    }
}

Complexity Analysis:

Time Complexity: O(V + E) - Each vertex and edge is visited exactly once
Space Complexity: O(V) - For DFS recursion stack and auxiliary arrays

Trade-offs:

Recursive vs Iterative: Recursive is cleaner but may cause stack overflow for large graphs
Class-based vs Function-based: Class provides better organization for complex implementations

Key Insights

Bridge Definition: Edge (u,v) is a bridge if removing it increases connected components
Low-Link Values: Track the lowest discovery time reachable from a vertex
Bridge Condition: low[v] > disc[u] means v cannot reach back to u’s ancestors
Back Edges: Update low values but don’t create bridges

Edge Cases

Single Edge: Only edge in graph is always a bridge
No Bridges: Graph with cycles may have no bridges
Disconnected Graph: Algorithm handles multiple components
Self-loops: Not applicable in simple graphs (excluded by constraints)
Multiple Edges: Algorithm works correctly with duplicate edges

How Solutions Handle Edge Cases:

Single edge: Correctly identified as bridge
No bridges: Returns empty list
Disconnected graph: DFS called for each component
Tree structure: All edges are bridges
Linear chain: All edges except in cycles are bridges

Test Cases

def test_find_bridges():
    # Basic case with one bridge
    assert find_bridges(4, [[0,1],[1,2],[2,0],[1,3]]) == [[1,3]]
    
    # Single edge
    assert find_bridges(2, [[0,1]]) == [[0,1]]
    
    # No bridges (cycle)
    assert find_bridges(3, [[0,1],[1,2],[2,0]]) == []
    
    # Tree (all edges are bridges)
    bridges = find_bridges(4, [[0,1],[1,2],[1,3]])
    assert len(bridges) == 3
    
    # Linear chain
    bridges = find_bridges(4, [[0,1],[1,2],[2,3]])
    assert len(bridges) == 3
    
    # Complex graph with multiple bridges
    bridges = find_bridges(7, [[0,1],[1,2],[2,0],[1,3],[3,4],[4,5],[5,3],[3,6]])
    assert [3,6] in bridges or [6,3] in bridges
    assert [1,3] in bridges or [3,1] in bridges
    
    # Disconnected components
    bridges = find_bridges(4, [[0,1],[2,3]])
    assert len(bridges) == 2
    
    print("All tests passed!")

test_find_bridges()

Follow-up Questions

Articulation Points: How would you find articulation points (vertices whose removal disconnects the graph)?
Bridge-Connected Components: How to find components that remain connected after removing all bridges?
Dynamic Bridges: Handle edge insertions/deletions while maintaining bridge information?
Weighted Bridges: In weighted graphs, find bridges that are also minimum weight edges?
Parallel Edges: How does the algorithm handle multiple edges between same vertices?

Common Mistakes

Wrong Bridge Condition: Using low[v] >= disc[u] instead of low[v] > disc[u]
- Problem: Includes non-bridge edges
- Solution: Use strict inequality
Parent Edge Confusion: Not excluding parent edges in back edge detection
- Problem: False bridge detection
- Solution: Check v != parent[u]
Incorrect Low Update: Wrong logic for updating low values
- Problem: Incorrect bridge identification
- Solution: Update low[u] = min(low[u], low[v]) for tree edges
Discovery Time Errors: Not incrementing time correctly
- Problem: Incorrect discovery time assignments
- Solution: Increment time for each vertex visit

Interview Tips

Algorithm Understanding: Know the intuition behind low-link values
Implementation Details: Be prepared to code Tarjan’s algorithm from scratch
Edge Case Discussion: Always mention disconnected components
Complexity Analysis: Explain why it’s linear time
Applications: Understand network reliability and critical infrastructure problems

Concept Explanations

Tarjan’s Algorithm: Uses DFS to compute discovery times and low-link values. The key insight is that an edge (u,v) is a bridge if and only if there’s no back edge crossing the edge or connecting a descendant of v to an ancestor of u.

Low-Link Value: For a vertex v, low[v] is the smallest discovery time of any vertex reachable from v through its DFS subtree, including back edges.

Bridge vs Articulation Point: Bridges are edges whose removal increases components, while articulation points are vertices whose removal increases components.

When to Apply: Use bridge finding for:

Network reliability analysis
Finding critical connections in infrastructure
Graph connectivity problems
Social network analysis (critical relationships)