Find bridge in a graph
Problem Statement
Given an undirected graph, find all bridges. A bridge is an edge whose removal disconnects the graph (or increases the number of connected components).
Example:
- Input:
V = 5, edges = [(0,1), (0,2), (1,2), (1,3), (3,4)] - Output:
Bridges: (1,3), (3,4)
Noob-Friendly Explanation
Imagine a network of islands connected by bridges (the real kind!). Some bridges are super important — if one of them breaks, some islands become unreachable. Those are the "bridge" edges we need to find.
For example, if island A and island B are connected by only one bridge, removing that bridge means you can't get from A to B anymore. But if there are two different paths between two islands, removing one bridge still leaves them connected.
Approach 1: Brute Force
Intuition
For each edge, temporarily remove it from the graph and check if the graph is still connected. If removing the edge disconnects the graph, it's a bridge.
Algorithm
- For each edge (u, v) in the graph: a. Remove the edge. b. Run BFS/DFS to check if all vertices are still reachable from vertex 0. c. If not, (u, v) is a bridge. d. Add the edge back.
import java.util.*;
public class BridgeBruteForce {
public static List<int[]> findBridges(int V, List<int[]> edges) {
List<int[]> bridges = new ArrayList<>();
Map<Integer, List<Integer>> adj = new HashMap<>();
for (int i = 0; i < V; i++) adj.put(i, new ArrayList<>());
for (int[] e : edges) {
adj.get(e[0]).add(e[1]);
adj.get(e[1]).add(e[0]);
}
for (int[] edge : edges) {
// Remove this edge
adj.get(edge[0]).remove(Integer.valueOf(edge[1]));
adj.get(edge[1]).remove(Integer.valueOf(edge[0]));
// Check connectivity using BFS
boolean[] visited = new boolean[V];
Queue<Integer> queue = new LinkedList<>();
queue.offer(0);
visited[0] = true;
int count = 1;
while (!queue.isEmpty()) {
int node = queue.poll();
for (int neigh : adj.get(node)) {
if (!visited[neigh]) {
visited[neigh] = true;
count++;
queue.offer(neigh);
}
}
}
if (count < V) {
bridges.add(edge);
}
// Add edge back
adj.get(edge[0]).add(edge[1]);
adj.get(edge[1]).add(edge[0]);
}
return bridges;
}
public static void main(String[] args) {
int V = 5;
List<int[]> edges = new ArrayList<>();
edges.add(new int[]{0, 1});
edges.add(new int[]{0, 2});
edges.add(new int[]{1, 2});
edges.add(new int[]{1, 3});
edges.add(new int[]{3, 4});
List<int[]> bridges = findBridges(V, edges);
System.out.println("Bridges:");
for (int[] b : bridges) {
System.out.println(b[0] + " - " + b[1]);
}
}
}Complexity Analysis
- Time Complexity: O(E * (V + E)) - for each of E edges, we run a BFS/DFS which is O(V + E)
- Space Complexity: O(V + E) - for the adjacency list and visited array
Approach 2: Optimal (Tarjan's Algorithm)
Intuition
Use DFS and track discovery times and low-link values. The discovery time is when a node is first visited. The low-link value is the smallest discovery time reachable from the subtree rooted at that node. An edge (u, v) is a bridge if low[v] > disc[u], meaning there's no back edge from the subtree of v that reaches u or its ancestors.
Algorithm
- Run DFS from any node, assigning discovery times.
- For each node, compute its low-link value (min of its own discovery time, discovery times of back-edge ancestors, and low values of children).
- If
low[v] > disc[u], edge (u → v) is a bridge.
import java.util.*;
public class BridgeTarjan {
static int timer = 0;
public static List<int[]> findBridges(int V, List<List<Integer>> adj) {
int[] disc = new int[V];
int[] low = new int[V];
boolean[] visited = new boolean[V];
List<int[]> bridges = new ArrayList<>();
Arrays.fill(disc, -1);
Arrays.fill(low, -1);
for (int i = 0; i < V; i++) {
if (!visited[i]) {
dfs(i, -1, adj, disc, low, visited, bridges);
}
}
return bridges;
}
static void dfs(int u, int parent, List<List<Integer>> adj,
int[] disc, int[] low, boolean[] visited, List<int[]> bridges) {
visited[u] = true;
disc[u] = low[u] = timer++;
for (int v : adj.get(u)) {
if (v == parent) continue;
if (visited[v]) {
low[u] = Math.min(low[u], disc[v]);
} else {
dfs(v, u, adj, disc, low, visited, bridges);
low[u] = Math.min(low[u], low[v]);
if (low[v] > disc[u]) {
bridges.add(new int[]{u, v});
}
}
}
}
public static void main(String[] args) {
int V = 5;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
int[][] edges = {{0,1},{0,2},{1,2},{1,3},{3,4}};
for (int[] e : edges) {
adj.get(e[0]).add(e[1]);
adj.get(e[1]).add(e[0]);
}
List<int[]> bridges = findBridges(V, adj);
System.out.println("Bridges:");
for (int[] b : bridges) {
System.out.println(b[0] + " - " + b[1]);
}
}
}Complexity Analysis
- Time Complexity: O(V + E) - single DFS traversal
- Space Complexity: O(V + E) - for adjacency list, disc, low, visited arrays