Bridges in Graph Tarjan's Algorithm in DSA Typescript

Mental Model

A bridge is an edge that, if removed, increases the number of disconnected parts in a graph. Tarjan's algorithm finds these by exploring nodes deeply and tracking the earliest reachable node from each subtree.

Analogy: Imagine a city connected by roads. A bridge is a road that, if closed, splits the city into two parts with no way to travel between them. Tarjan's algorithm is like a detective tracing paths to find these critical roads.

Graph:
  1 --- 2
   \   |
    3  4

Bridges:
Edge 1-3 is a bridge because removing it disconnects node 3.

Dry Run Walkthrough

Input: Graph with edges: 1-2, 1-3, 2-4

Goal: Find all bridges in the graph using Tarjan's algorithm

Step 1: Start DFS at node 1, set discovery time and low value to 1

disc[1]=1, low[1]=1, stack empty

Why: Initialize discovery and low values for the first node

Step 2: Visit node 2 from node 1, set disc[2]=2, low[2]=2

disc[1]=1, low[1]=1; disc[2]=2, low[2]=2

Why: Explore neighbor node 2 and record discovery time

Step 3: Visit node 4 from node 2, set disc[4]=3, low[4]=3

disc[1]=1, low[1]=1; disc[2]=2, low[2]=2; disc[4]=3, low[4]=3

Why: Explore neighbor node 4 and record discovery time

Step 4: Node 4 has no unvisited neighbors, backtrack to node 2, update low[2] = min(low[2], low[4]) = 2

disc[1]=1, low[1]=1; disc[2]=2, low[2]=2; disc[4]=3, low[4]=3

Why: Update low value of node 2 based on subtree rooted at 4

Step 5: Check if edge 2-4 is a bridge: low[4] > disc[2] (3 > 2) true, so edge 2-4 is a bridge

Bridge found: 2-4

Why: If low value of child is greater than discovery time of parent, edge is a bridge

Step 6: Backtrack to node 1, update low[1] = min(low[1], low[2]) = 1

disc[1]=1, low[1]=1; disc[2]=2, low[2]=2

Why: Update low value of node 1 based on subtree rooted at 2

Step 7: Visit node 3 from node 1, set disc[3]=4, low[3]=4

disc[1]=1, low[1]=1; disc[3]=4, low[3]=4

Why: Explore neighbor node 3 and record discovery time

Step 8: Node 3 has no unvisited neighbors, backtrack to node 1, update low[1] = min(low[1], low[3]) = 1

disc[1]=1, low[1]=1; disc[3]=4, low[3]=4

Why: Update low value of node 1 based on subtree rooted at 3

Step 9: Check if edge 1-3 is a bridge: low[3] > disc[1] (4 > 1) true, so edge 1-3 is a bridge

Bridge found: 1-3

Why: Edge 1-3 is a bridge because low[3] > disc[1]

Result:

Bridges found: 2-4 and 1-3

Annotated Code

DSA Typescript

class Graph {
  adjacencyList: Map<number, number[]>;
  time: number;
  disc: number[];
  low: number[];
  visited: boolean[];
  bridges: [number, number][];

  constructor(vertices: number) {
    this.adjacencyList = new Map();
    for (let i = 1; i <= vertices; i++) {
      this.adjacencyList.set(i, []);
    }
    this.time = 0;
    this.disc = Array(vertices + 1).fill(-1);
    this.low = Array(vertices + 1).fill(-1);
    this.visited = Array(vertices + 1).fill(false);
    this.bridges = [];
  }

  addEdge(u: number, v: number) {
    this.adjacencyList.get(u)?.push(v);
    this.adjacencyList.get(v)?.push(u);
  }

  dfs(u: number, parent: number) {
    this.visited[u] = true;
    this.time++;
    this.disc[u] = this.time;
    this.low[u] = this.time;

    for (const v of this.adjacencyList.get(u) || []) {
      if (v === parent) continue; // Skip the edge to parent

      if (!this.visited[v]) {
        this.dfs(v, u); // Explore deeper
        this.low[u] = Math.min(this.low[u], this.low[v]); // Update low[u]

        if (this.low[v] > this.disc[u]) {
          this.bridges.push([u, v]); // Found a bridge
        }
      } else {
        this.low[u] = Math.min(this.low[u], this.disc[v]); // Update low[u] for back edge
      }
    }
  }

  findBridges() {
    for (let i = 1; i < this.visited.length; i++) {
      if (!this.visited[i]) {
        this.dfs(i, -1);
      }
    }
    return this.bridges;
  }
}

// Driver code
const graph = new Graph(4);
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 4);
const bridges = graph.findBridges();
for (const [u, v] of bridges) {
  console.log(`${u} - ${v}`);
}

this.visited[u] = true;

Mark current node as visited to avoid revisiting

this.time++; this.disc[u] = this.time; this.low[u] = this.time;

Set discovery time and low value for current node

if (v === parent) continue;

Skip the edge leading back to parent node

if (!this.visited[v]) { this.dfs(v, u); this.low[u] = Math.min(this.low[u], this.low[v]); }

Explore unvisited neighbor and update low[u] after recursion

if (this.low[v] > this.disc[u]) { this.bridges.push([u, v]); }

If child's low is greater than current's discovery, edge is a bridge

else { this.low[u] = Math.min(this.low[u], this.disc[v]); }

Update low[u] for back edge to ancestor

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

Start DFS from each unvisited node to cover disconnected graph

Output

2 - 4

1 - 3

Complexity Analysis

Time: O(V + E) because each vertex and edge is visited once during DFS

Space: O(V + E) for adjacency list and arrays storing discovery, low, and visited states

vs Alternative: Naive approach checks connectivity after removing each edge, costing O(E*(V+E)), much slower than Tarjan's linear time

Edge Cases

Empty graph with no edges

No bridges found, algorithm handles gracefully

DSA Typescript

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

Graph with a single node

No edges, so no bridges

DSA Typescript

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

Graph with multiple disconnected components

Algorithm runs DFS on each component to find bridges in all parts

DSA Typescript

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

When to Use This Pattern

When asked to find critical connections or edges whose removal disconnects the graph, use Tarjan's algorithm for bridges because it efficiently finds them in linear time.

Common Mistakes

Mistake: Not updating low[u] with discovery time of visited neighbors (back edges)
Fix: Add else clause to update low[u] = min(low[u], disc[v]) for back edges

Mistake: Not skipping the parent node during DFS, causing false bridge detection
Fix: Add condition to continue loop if neighbor is parent node

Summary

Finds edges that disconnect the graph if removed (bridges).

Use when you need to identify critical connections in networks or graphs.

Track discovery and low times during DFS to detect bridges efficiently.