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.