Bridges in Graph Tarjan's Algorithm in DSA Javascript

Mental Model

A bridge is an edge that, if removed, splits the graph into more pieces. Tarjan's algorithm finds these by exploring nodes deeply and tracking the earliest reachable node from each subtree.

Analogy: Imagine a network of islands connected by bridges. Some bridges are the only way to reach certain islands. If you remove such a bridge, the islands get separated. Tarjan's algorithm helps find these critical bridges by exploring paths and seeing which bridges connect isolated parts.

Graph:
  1 --- 2
  |   / |
  |  /  |
  3     4

Bridges are edges that if cut, increase the number of disconnected parts.
Example bridge: edge 2-4 if removed splits the graph.

Representation:
1 -> [2,3]
2 -> [1,3,4]
3 -> [1,2]
4 -> [2]

Dry Run Walkthrough

Input: Graph edges: (1-2), (1-3), (2-3), (2-4)

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

Step 1: Start DFS from node 1, assign discovery time and low value = 1

disc: {1:1}, low: {1:1}, stack: [], bridges: []

Why: We begin exploring from node 1, marking its discovery time and low value

Step 2: Visit neighbor 2 from 1, assign discovery time and low value = 2

disc: {1:1, 2:2}, low: {1:1, 2:2}, stack: [], bridges: []

Why: We explore node 2 next, setting its discovery and low values

Step 3: Visit neighbor 3 from 2, assign discovery time and low value = 3

disc: {1:1, 2:2, 3:3}, low: {1:1, 2:2, 3:3}, stack: [], bridges: []

Why: We explore node 3, marking discovery and low values

Step 4: From 3, visit neighbor 1 which is already visited and not parent, update low[3] = min(low[3], disc[1]) = 1

disc: {1:1, 2:2, 3:3}, low: {1:1, 2:2, 3:1}, stack: [], bridges: []

Why: Back edge from 3 to 1 lowers low value of 3, indicating a cycle

Step 5: Backtrack to 2, update low[2] = min(low[2], low[3]) = 1

disc: {1:1, 2:2, 3:3}, low: {1:1, 2:1, 3:1}, stack: [], bridges: []

Why: Low value of 2 updated from subtree 3

Step 6: From 2, visit neighbor 4, assign discovery time and low value = 4

disc: {1:1, 2:2, 3:3, 4:4}, low: {1:1, 2:1, 3:1, 4:4}, stack: [], bridges: []

Why: Explore node 4, new node with discovery time 4

Step 7: From 4, visit neighbor 2 which is parent, ignore

disc: {1:1, 2:2, 3:3, 4:4}, low: {1:1, 2:1, 3:1, 4:4}, stack: [], bridges: []

Why: Ignore parent to avoid trivial cycle

Step 8: Backtrack to 2, update low[2] = min(low[2], low[4]) = 1; since low[4] > disc[2], edge (2-4) is a bridge

disc: {1:1, 2:2, 3:3, 4:4}, low: {1:1, 2:1, 3:1, 4:4}, bridges: [(2,4)]

Why: Low value of 4 is greater than discovery time of 2, so edge (2-4) is a bridge

Result:

Final bridges: (2-4)
Graph state:
1 -> 2 -> 3 -> null
2 -> 1 -> 3 -> 4 -> null
3 -> 1 -> 2 -> null
4 -> 2 -> null

Annotated Code

DSA Javascript

class Graph {
  constructor(vertices) {
    this.V = vertices;
    this.adj = new Array(vertices + 1).fill(0).map(() => []);
  }

  addEdge(u, v) {
    this.adj[u].push(v);
    this.adj[v].push(u);
  }

  bridgeUtil(u, visited, disc, low, parent, bridges, time) {
    visited[u] = true;
    disc[u] = low[u] = ++time.count;

    for (const v of this.adj[u]) {
      if (!visited[v]) {
        parent[v] = u;
        this.bridgeUtil(v, visited, disc, low, parent, bridges, time);
        low[u] = Math.min(low[u], low[v]); // update low[u] from subtree

        if (low[v] > disc[u]) {
          bridges.push([u, v]); // found bridge
        }
      } else if (v !== parent[u]) {
        low[u] = Math.min(low[u], disc[v]); // back edge updates low[u]
      }
    }
  }

  findBridges() {
    const visited = new Array(this.V + 1).fill(false);
    const disc = new Array(this.V + 1).fill(-1);
    const low = new Array(this.V + 1).fill(-1);
    const parent = new Array(this.V + 1).fill(-1);
    const bridges = [];
    const time = { count: 0 };

    for (let i = 1; i <= this.V; i++) {
      if (!visited[i]) {
        this.bridgeUtil(i, visited, disc, low, parent, bridges, time);
      }
    }
    return bridges;
  }
}

// Driver code
const g = new Graph(4);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(2, 3);
g.addEdge(2, 4);

const bridges = g.findBridges();
for (const [u, v] of bridges) {
  console.log(`${u} - ${v}`);
}

visited[u] = true; disc[u] = low[u] = ++time.count;

Mark node u visited and set discovery and low times

for (const v of this.adj[u]) {

Traverse all neighbors of u

if (!visited[v]) { parent[v] = u; this.bridgeUtil(v, visited, disc, low, parent, bridges, time);

Visit unvisited neighbor v recursively

low[u] = Math.min(low[u], low[v]);

Update low[u] based on subtree low[v]

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

If low[v] > disc[u], edge u-v is a bridge

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

Update low[u] for back edge to ancestor

for (let i = 1; i <= this.V; i++) { if (!visited[i]) { this.bridgeUtil(i, visited, disc, low, parent, bridges, time);

Start DFS from unvisited nodes to cover all components

Output

2 - 4

Complexity Analysis

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

Space: O(V) for arrays storing discovery, low, parent, and visited status

vs Alternative: Naive approach checks connectivity after removing each edge, costing O(E*(V+E)) which is much slower

Edge Cases

Graph with no edges

No bridges found as there are no edges

DSA Javascript

for (let i = 1; i <= this.V; i++) {
  if (!visited[i]) {
    this.bridgeUtil(i, visited, disc, low, parent, bridges, time);

Graph with single node

No bridges found as no edges exist

DSA Javascript

for (let i = 1; i <= this.V; i++) {
  if (!visited[i]) {
    this.bridgeUtil(i, visited, disc, low, parent, bridges, time);

Graph with multiple disconnected components

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

DSA Javascript

for (let i = 1; i <= this.V; i++) {
  if (!visited[i]) {
    this.bridgeUtil(i, visited, disc, low, parent, bridges, time);

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 one DFS pass.

Common Mistakes

Mistake: Not updating low[u] correctly on back edges to ancestors
Fix: Update low[u] = min(low[u], disc[v]) when v is visited and not parent[u]

Mistake: Checking low[v] >= disc[u] instead of low[v] > disc[u] for bridges
Fix: Use strict greater than (>) to identify bridges correctly

Mistake: Not initializing discovery and low arrays properly
Fix: Initialize disc and low arrays with -1 or appropriate default values before DFS

Summary

Finds edges in a graph that, if removed, increase the number of disconnected parts.

Use when you need to identify critical connections or weak points in a network.

The key insight is tracking the earliest reachable ancestor from each node's subtree to detect bridges.

Practice

1. What is the main purpose of Tarjan's algorithm when finding bridges in a graph?

easy

A. To detect cycles in a graph

B. To identify edges that, if removed, increase the number of connected components

C. To find the shortest path between two nodes

D. To count the total number of nodes in the graph

Solution

1. Step 1: Understand the definition of a bridge

   A bridge is an edge that, when removed, increases the number of connected components in a graph.

2. Step 2: Relate Tarjan's algorithm to bridges

   Tarjan's algorithm efficiently finds such edges by using DFS and tracking discovery and low times.

3. Final Answer:

   To identify edges that, if removed, increase the number of connected components -> Option B

4. Quick Check:

   Bridges = edges increasing components when removed [OK]

Hint: Bridges disconnect graph if removed [OK]

Common Mistakes:

• Confusing bridges with cycles
• Thinking it finds shortest paths
• Assuming it counts nodes

2. Which of the following is the correct way to initialize the discovery time array in JavaScript for Tarjan's algorithm?

easy

A. const disc = new Array(n).fill(-1);

B. const disc = Array(n).map(() => 0);

C. const disc = new Array(n).map(0);

D. const disc = Array.fill(n, -1);

Solution

1. Step 1: Understand array initialization in JavaScript

   Using new Array(n).fill(value) correctly fills all elements with the given value.

2. Step 2: Check each option

   A: const disc = new Array(n).fill(-1); correctly creates an array of length n filled with -1. B: const disc = Array(n).map(() => 0); fills with 0 instead of -1. C: const disc = new Array(n).map(0); passes non-function to map, causing TypeError. D: const disc = Array.fill(n, -1); uses incorrect syntax (no static Array.fill).

3. Final Answer:

   const disc = new Array(n).fill(-1); -> Option A

4. Quick Check:

   Use fill() to initialize arrays [OK]

Hint: Use new Array(n).fill(value) to initialize arrays [OK]

Common Mistakes:

• Initializing with 0 instead of -1
• Passing non-function to map
• Wrong syntax for Array.fill

3. What will be the output bridges found by the following code snippet for the graph edges: [[0,1],[1,2],[2,0],[1,3]]?

const graph = [[1],[0,2,3],[1,0],[1]];
// Assume Tarjan's algorithm is correctly implemented and called
// Output bridges are printed as pairs of nodes

medium

A. []

B. [[0,1],[1,3]]

C. [[0,1],[1,2],[2,0]]

D. [[1,3]]

Solution

1. Step 1: Analyze the graph structure

   The graph has a triangle between nodes 0,1,2 and a single edge from 1 to 3.

2. Step 2: Identify bridges

   The triangle edges are part of a cycle, so none are bridges. The edge [1,3] connects node 3 alone, so removing it increases components.

3. Final Answer:

   [[1,3]] -> Option D

4. Quick Check:

   Only edge to isolated node is bridge [OK]

Hint: Edges in cycles are not bridges [OK]

Common Mistakes:

• Marking cycle edges as bridges
• Ignoring isolated node connections
• Confusing node indices

4. Identify the bug in this Tarjan's algorithm snippet for finding bridges:

function dfs(u, parent) {
  visited[u] = true;
  disc[u] = low[u] = time++;
  for (const v of graph[u]) {
    if (!visited[v]) {
      dfs(v, u);
      low[u] = Math.min(low[u], low[v]);
      if (low[v] > disc[u]) {
        bridges.push([u, v]);
      }
    } else if (v !== parent) {
      low[u] = Math.min(low[u], disc[v]);
    }
  }
}

medium

A. The 'visited' array is not initialized

B. The condition 'low[v] > disc[u]' should be 'low[v] >= disc[u]'

C. The 'time' variable is not incremented correctly

D. The else if condition should check 'v === parent' instead of 'v !== parent'

Solution

1. Step 1: Check variable initialization

   The code uses 'visited' array but does not show its initialization, which is necessary before DFS.

2. Step 2: Verify other parts

   The condition 'low[v] > disc[u]' is correct for bridges. The time variable is incremented properly. The else if condition correctly checks 'v !== parent'.

3. Final Answer:

   The 'visited' array is not initialized -> Option A

4. Quick Check:

   Initialize visited before DFS [OK]

Hint: Always initialize visited array before DFS [OK]

Common Mistakes:

• Changing correct bridge condition
• Misunderstanding parent check
• Forgetting to initialize arrays

5. Given a graph with nodes 0 to 4 and edges [[0,1],[1,2],[2,0],[1,3],[3,4]], which edges are bridges using Tarjan's algorithm?

hard

A. [[0,1],[1,2],[2,0]]

B. [[0,1],[3,4]]

C. [[1,3],[3,4]]

D. [[1,2],[1,3]]

Solution

1. Step 1: Analyze the graph structure

   Nodes 0,1,2 form a cycle, so edges among them are not bridges. Edges [1,3] and [3,4] connect nodes outside the cycle.

2. Step 2: Identify bridges

   Removing [1,3] or [3,4] increases connected components, so these are bridges.

3. Final Answer:

   [[1,3],[3,4]] -> Option C

4. Quick Check:

   Edges connecting cycle to outside are bridges [OK]

Hint: Edges outside cycles connecting nodes are bridges [OK]

Common Mistakes:

• Marking cycle edges as bridges
• Ignoring edges connecting outside nodes
• Confusing node indices