Find Bridges in Graph Using Tarjan's Algorithm (Time & Low Arrays)

Problem Statement❯

You are given a network of n servers numbered from 0 to n - 1 connected by undirected server-to-server connections, where each connection is represented as [a, b].

A critical connection is a connection that, if removed, will disconnect the network — making some servers unreachable from others.

Return all such critical connections in any order.

Note: In this problem, servers are treated as nodes of a graph, and connections as undirected edges. The goal is to find all bridges in the graph using Tarjan's Algorithm.

Examples❯

n	Connections	Output	Description
4	[[0,1],[1,2],[2,0],[1,3]]	[[1,3]]	Removing edge 1-3 disconnects node 3
5	[[0,1],[1,2],[2,3],[3,4],[4,2]]	[[0,1]]	Only 0-1 is a bridge; others are in a cycle
2	[[0,1]]	[[0,1]]	Single connection is always a bridge
3	[[0,1],[1,2],[2,0]]	[]	Fully connected triangle — no bridges
0	[]	[]	Empty graph, no edges or bridges

Visualization Player

Solution❯

Understanding the Problem

We are given a network of servers (nodes) connected by undirected edges. Each connection is a two-way link. Our goal is to find all critical connections, also known as bridges.

A bridge is an edge that, if removed, would increase the number of connected components in the graph. In simple terms, removing that edge disconnects part of the network. This is a classic graph problem, and we can solve it efficiently using Tarjan’s Algorithm, which is based on Depth-First Search (DFS).

Step-by-Step Solution with Example

step 1: Represent the Graph

We first build an adjacency list from the input list of connections. This allows us to efficiently explore all neighbors of a node during DFS.

step 2: Setup Required Structures

We initialize:

visited[]: to keep track of visited nodes
tin[]: stores the discovery time (insertion time) for each node
low[]: the lowest discovery time reachable from that node or its subtree
timer: a global counter to assign discovery times
result[]: a list to store all bridges found

step 3: Run DFS from Any Node

We begin DFS traversal from an unvisited node. During DFS:

We mark the node as visited and assign its tin and low values using the global timer.
For each neighbor:
- If the neighbor is the parent (the node we came from), we skip it.
- If the neighbor is already visited, it means a back edge exists. We update the current node’s low value using the neighbor’s tin.
- If the neighbor is unvisited, we recursively apply DFS on it. After returning, we update the current node’s low value based on the neighbor’s low. If low[neighbor] > tin[current], then [current, neighbor] is a bridge.

step 4: Example Walkthrough

Let's consider this input:

n = 5  
connections = [[0,1],[1,2],[2,0],[1,3],[3,4]]

This forms the following graph:

A cycle: 0–1–2–0
Two edges: 1–3 and 3–4 (which are not part of any cycle)

Running Tarjan's algorithm:

DFS visits nodes and assigns timestamps
When we backtrack, we find that removing 1–3 or 3–4 would increase the number of components

Output: [[3, 4], [1, 3]]

Edge Cases

Disconnected Graph: If the graph has multiple disconnected parts, run DFS for each unvisited node.
No Bridges: If the graph is fully connected with cycles (like a complete graph), then no bridge will be found.
Single Node: No connections to check, return an empty list.
Tree Structure: Every edge in a tree is a bridge since removing any edge disconnects the graph.

Finally

Tarjan’s Algorithm is an elegant and efficient solution to detect bridges in a graph. By tracking the discovery time and the lowest reachable ancestor for each node, we can find edges that, if removed, disconnect the graph. The algorithm runs in O(V + E) time and is highly suitable for large graphs.

Understanding the idea of back edges and how they affect the low value is key to mastering this approach. With step-by-step DFS and careful updates, even beginners can grasp the intuition behind finding critical connections in a network.

Algorithm Steps❯

Initialize graph as an adjacency list.
Create arrays: tin[], low[] and visited[] of size n.
Set a timer = 0.
For each unvisited node, run DFS:

Mark node as visited, set tin[node] = low[node] = timer++.
For each neighbor:

If it is the parent, continue.
If not visited, recurse and update low[node].
If low[neighbor] > tin[node], then [node, neighbor] is a bridge.
If already visited, update low[node] = min(low[node], tin[neighbor]).

Code

JavaScript

function criticalConnections(n, connections) {
  const graph = Array.from({ length: n }, () => []);
  for (const [u, v] of connections) {
    graph[u].push(v);
    graph[v].push(u);
  }

  const tin = new Array(n).fill(-1);
  const low = new Array(n).fill(-1);
  const visited = new Array(n).fill(false);
  const bridges = [];
  let timer = 0;

  function dfs(node, parent) {
    visited[node] = true;
    tin[node] = low[node] = timer++;

    for (const neighbor of graph[node]) {
      if (neighbor === parent) continue;

      if (!visited[neighbor]) {
        dfs(neighbor, node);
        low[node] = Math.min(low[node], low[neighbor]);

        if (low[neighbor] > tin[node]) {
          bridges.push([node, neighbor]);
        }
      } else {
        low[node] = Math.min(low[node], tin[neighbor]);
      }
    }
  }

  for (let i = 0; i < n; i++) {
    if (!visited[i]) {
      dfs(i, -1);
    }
  }

  return bridges;
}

console.log("Bridges:", criticalConnections(4, [[0,1],[1,2],[2,0],[1,3]]));

⬅ Previous TopicMaking a Large Island Using DSU

Next Topic ⮕Articulation Points in Graphs

Comments

Loading comments...