Bridges in Graph Tarjan's Algorithm in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Tarjan's Bridges Algorithm on a Simple Graph

What is the output (list of bridges) of the following TypeScript code that finds bridges in an undirected graph using Tarjan's algorithm?

DSA Typescript

class Graph {
  adjacencyList: Map<number, number[]> = new Map();
  time = 0;

  addEdge(u: number, v: number) {
    if (!this.adjacencyList.has(u)) this.adjacencyList.set(u, []);
    if (!this.adjacencyList.has(v)) this.adjacencyList.set(v, []);
    this.adjacencyList.get(u)!.push(v);
    this.adjacencyList.get(v)!.push(u);
  }

  findBridges(): [number, number][] {
    const visited = new Set<number>();
    const disc = new Map<number, number>();
    const low = new Map<number, number>();
    const parent = new Map<number, number | null>();
    const bridges: [number, number][] = [];

    const dfs = (u: number) => {
      visited.add(u);
      this.time++;
      disc.set(u, this.time);
      low.set(u, this.time);

      for (const v of this.adjacencyList.get(u) || []) {
        if (!visited.has(v)) {
          parent.set(v, u);
          dfs(v);
          low.set(u, Math.min(low.get(u)!, low.get(v)!));
          if (low.get(v)! > disc.get(u)!) {
            bridges.push([u, v]);
          }
        } else if (v !== parent.get(u)) {
          low.set(u, Math.min(low.get(u)!, disc.get(v)!));
        }
      }
    };

    for (const node of this.adjacencyList.keys()) {
      if (!visited.has(node)) {
        parent.set(node, null);
        dfs(node);
      }
    }

    return bridges;
  }
}

const g = new Graph();
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(3, 4);
g.addEdge(3, 5);
g.addEdge(4, 5);

console.log(g.findBridges());

A [[1, 2], [1, 3]]

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

C [[1, 2]]

D []

💡 Hint

Think about which edges, if removed, increase the number of connected components.

The graph has edges: 1-2, 1-3, 3-4, 3-5, 4-5.

Edges 3-4 and 3-5 form a cycle with 4-5, so removing them does not disconnect the graph.

Edge 1-3 connects node 1 to the cycle, so removing it disconnects node 1 from the rest.

Edge 1-2 is a leaf edge, removing it disconnects node 2.

Thus, bridges are edges [1, 2] and [1, 3].

🧠 Conceptual

intermediate

Understanding Low and Discovery Times in Tarjan's Algorithm

In Tarjan's algorithm for finding bridges, what does the 'low' value of a node represent?

A The total number of edges connected to the node.

B The earliest discovery time reachable from the node including itself and its descendants.

C The maximum depth of the node in the DFS tree.

D The number of connected components in the graph.

💡 Hint

Think about what 'low' helps to detect in the graph.

The 'low' value of a node is the smallest discovery time reachable from that node by following zero or more tree edges and then possibly one back edge.

This helps detect if there is a back edge connecting a descendant to an ancestor, which means no bridge on that path.

🔧 Debug

advanced

Identify the Bug in Tarjan's Bridge Detection Code

What error will the following TypeScript code produce when run, and why?

DSA Typescript

class Graph {
  adjacencyList: Map<number, number[]> = new Map();
  time = 0;

  addEdge(u: number, v: number) {
    if (!this.adjacencyList.has(u)) this.adjacencyList.set(u, []);
    if (!this.adjacencyList.has(v)) this.adjacencyList.set(v, []);
    this.adjacencyList.get(u)!.push(v);
    this.adjacencyList.get(v)!.push(u);
  }

  findBridges(): [number, number][] {
    const visited = new Set<number>();
    const disc = new Map<number, number>();
    const low = new Map<number, number>();
    const parent = new Map<number, number | null>();
    const bridges: [number, number][] = [];

    const dfs = (u: number) => {
      visited.add(u);
      this.time++;
      disc.set(u, this.time);
      low.set(u, this.time);

      for (const v of this.adjacencyList.get(u) || []) {
        if (!visited.has(v)) {
          parent.set(v, u);
          dfs(v);
          low.set(u, Math.min(low.get(u)!, low.get(v)!));
          if (low.get(v)! >= disc.get(u)!) {
            bridges.push([u, v]);
          }
        } else if (v !== parent.get(u)) {
          low.set(u, Math.min(low.get(u)!, disc.get(v)!));
        }
      }
    };

    for (const node of this.adjacencyList.keys()) {
      if (!visited.has(node)) {
        parent.set(node, null);
        dfs(node);
      }
    }

    return bridges;
  }
}

const g = new Graph();
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(3, 4);
g.addEdge(3, 5);
g.addEdge(4, 5);

console.log(g.findBridges());

A The code throws a runtime error because 'low.get(v)' can be undefined.

B The code outputs an empty list because the DFS never visits any node.

C The code outputs extra edges as bridges due to incorrect comparison operator in if condition.

D The code runs correctly and outputs [[1, 2], [1, 3]]

💡 Hint

Check the condition that decides if an edge is a bridge.

The condition if (low.get(v)! >= disc.get(u)!) is incorrect for bridges.

It should be if (low.get(v)! > disc.get(u)!) because equality means the edge is part of a cycle, not a bridge.

Using >= causes edges that are not bridges to be included.

🚀 Application

advanced

Number of Bridges in a Complete Graph

If you run Tarjan's algorithm to find bridges on a complete graph with 5 nodes (every node connected to every other node), how many bridges will it find?

A 0

B 10

C 5

D 1

💡 Hint

Think about cycles in a complete graph.

A complete graph has every possible edge between nodes.

Removing any edge does not disconnect the graph because there are many alternative paths.

Therefore, there are no bridges in a complete graph.

🧠 Conceptual

expert

Why Tarjan's Algorithm Uses DFS Time Instead of BFS

Why does Tarjan's algorithm for finding bridges use Depth-First Search (DFS) and discovery times instead of Breadth-First Search (BFS)?

A DFS uses less memory than BFS, which is critical for bridge detection.

B BFS is slower than DFS for all graph algorithms, so DFS is preferred.

C BFS cannot be implemented recursively, so it is not suitable for Tarjan's algorithm.

D DFS naturally builds a tree structure with discovery times that help identify back edges and cycles, which BFS does not provide.

💡 Hint

Consider how discovery times and back edges help detect bridges.

Tarjan's algorithm relies on discovery times from DFS to detect back edges and cycles.

BFS does not produce a DFS tree with discovery times, so it cannot identify bridges using this method.

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