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.

Practice

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

easy

A. To sort nodes in topological order

B. To find the shortest path between two nodes

C. To detect cycles in a graph

D. To find edges that, if removed, increase the number of connected components

Solution

1. Step 1: Understand what a bridge is in a graph

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

2. Step 2: Identify Tarjan's algorithm goal

   Tarjan's algorithm is used to find such edges efficiently by using DFS and tracking discovery and low times.

3. Final Answer:

   To find edges that, if removed, increase the number of connected components -> Option D

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
• Mixing with topological sorting

2. Which of the following is the correct TypeScript syntax to declare the discovery time array for Tarjan's algorithm?

easy

A. let disc = Array(n).fill('undefined');

B. let disc: number = new Array(n);

C. let disc: number[] = new Array(n).fill(-1);

D. let disc: number[] = new Array(n);

Solution

1. Step 1: Understand array declaration with initial values in TypeScript

   To create an array of numbers with size n and initialize all values to -1, use new Array(n).fill(-1).

2. Step 2: Check type correctness

   TypeScript syntax requires disc to be number[] for an array of numbers.

3. Final Answer:

   let disc: number[] = new Array(n).fill(-1); -> Option C

4. Quick Check:

   Array<number> with fill(-1) = correct initialization [OK]

Hint: Use new Array(n).fill(-1) for initialized arrays [OK]

Common Mistakes:

• Using wrong type annotation
• Not initializing array values
• Filling with string instead of number

3. Consider the following TypeScript code snippet using Tarjan's algorithm to find bridges. What will be the output bridges for the given graph?

const graph = [[1, 2], [0, 2], [0, 1, 3], [2, 4], [3]];
// Edges: 0-1, 0-2, 1-2, 2-3, 3-4
// Find bridges
const bridges = findBridges(graph);
console.log(bridges);

medium

A. [[2, 3], [3, 4]]

B. [[0, 1], [1, 2]]

C. [[0, 2], [2, 3]]

D. []

Solution

1. Step 1: Analyze the graph edges and connectivity

   The graph edges are 0-1, 0-2, 1-2 forming a triangle, and 2-3, 3-4 forming a chain. The triangle edges are not bridges because removing one does not disconnect the graph.

2. Step 2: Identify bridges

   Edges 2-3 and 3-4 are bridges because removing either disconnects node 4 or node 3 from the rest.

3. Final Answer:

   [[2, 3], [3, 4]] -> Option A

4. Quick Check:

   Bridges disconnect graph = [[2,3],[3,4]] [OK]

Hint: Bridges are edges not in any cycle [OK]

Common Mistakes:

• Including edges inside cycles as bridges
• Missing chain edges as bridges
• Confusing node indices

4. The following TypeScript function attempts to find bridges using Tarjan's algorithm but has a bug. What is the bug?

function dfs(u: number, parent: number) {
  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 condition 'low[v] > disc[u]' should be 'low[v] >= disc[u]'

B. The 'visited' array is not initialized before DFS

C. The 'time' variable is not incremented correctly

D. The parent node check 'v !== parent' is missing

Solution

1. Step 1: Check initialization of visited array

   The code uses 'visited[u]' but does not show initialization. Without initializing, visited may be undefined causing runtime errors.

2. Step 2: Verify other parts

   The condition 'low[v] > disc[u]' is correct for bridges. The parent check is present. The time increment is correct.

3. Final Answer:

   The 'visited' array is not initialized before DFS -> Option B

4. Quick Check:

   Uninitialized visited array causes errors [OK]

Hint: Always initialize visited before DFS [OK]

Common Mistakes:

• Changing correct bridge condition
• Ignoring visited initialization
• Removing parent check

5. Given a connected undirected graph with nodes 0 to 5 and edges: 0-1, 1-2, 2-0, 1-3, 3-4, 4-5, 5-3, which edges are bridges according to Tarjan's algorithm?

hard

A. [[1, 3]]

B. [[3, 4], [4, 5]]

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

D. []

Solution

1. Step 1: Analyze graph structure

   Edges 0-1, 1-2, 2-0 form a triangle (cycle). Edges 3-4, 4-5, 5-3 form another cycle. Edge 1-3 connects these two cycles.

2. Step 2: Identify bridges

   Only edge 1-3 is a bridge because removing it disconnects the two cycles. Other edges are part of cycles and not bridges.

3. Final Answer:

   [[1, 3]] -> Option A

4. Quick Check:

   Bridge connects two cycles = [[1, 3]] [OK]

Hint: Bridges connect separate cycles or components [OK]

Common Mistakes:

• Marking cycle edges as bridges
• Missing the connecting bridge edge
• Confusing node pairs