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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Tarjan's Algorithm for Bridges

What is the output (list of bridges) of the following Tarjan's algorithm code on the given graph?

DSA Javascript

const graph = {
  0: [1, 2],
  1: [0, 2],
  2: [0, 1, 3],
  3: [2, 4],
  4: [3]
};

function findBridges(graph) {
  const n = Object.keys(graph).length;
  const visited = new Array(n).fill(false);
  const disc = new Array(n).fill(-1);
  const low = new Array(n).fill(-1);
  const bridges = [];
  let time = 0;

  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]);
      }
    }
  }

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

  return bridges;
}

console.log(findBridges(graph));

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

B [[0, 2], [2, 3]]

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

D []

💡 Hint

Look for edges where the low time of the connected node is greater than the discovery time of the current node.

The edges (2,3) and (3,4) are bridges because removing them increases the number of connected components. The other edges are part of cycles.

🧠 Conceptual

intermediate

Understanding Low and Discovery Times

In Tarjan's algorithm for finding bridges, what does the 'low' array represent?

A The time when the node was last visited in DFS.

B The number of edges connected to the node.

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

D The maximum discovery time of all nodes 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 or its descendants, including back edges.

🔧 Debug

advanced

Identify the Bug in Tarjan's Bridge Code

What error will the following code produce when run on a connected graph?

DSA Javascript

function findBridges(graph) {
  const n = Object.keys(graph).length;
  const visited = new Array(n).fill(false);
  const disc = new Array(n).fill(-1);
  const low = new Array(n).fill(-1);
  const bridges = [];
  let time = 0;

  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]);
      }
    }
  }

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

  return bridges;
}

A It will incorrectly include edges that are not bridges.

B It will throw a ReferenceError due to 'time' being undefined.

C It will miss some bridges because of wrong comparison operator.

D It will cause an infinite recursion error.

💡 Hint

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

The condition 'low[v] >= disc[u]' is incorrect for bridges; it should be 'low[v] > disc[u]'. Using '>=' causes edges that are not bridges to be included.

🚀 Application

advanced

Number of Bridges in a Complex Graph

Given the graph edges below, how many bridges does Tarjan's algorithm find?

DSA Javascript

const graph = {
  0: [1, 2],
  1: [0, 2, 3],
  2: [0, 1, 4],
  3: [1, 5],
  4: [2],
  5: [3, 6],
  6: [5]
};

// Assume correct Tarjan's algorithm is run on this graph.

A 2

B 3

C 1

D 4

💡 Hint

Identify edges whose removal increases connected components.

The bridges are edges (1,3), (2,4), (3,5), and (5,6) because removing them increases the number of connected components. The other edges are part of cycles.

🧠 Conceptual

expert

Why Tarjan's Algorithm Uses DFS for Bridges

Why does Tarjan's algorithm use Depth-First Search (DFS) to find bridges in a graph?

A Because DFS uses less memory than BFS in all cases.

B Because DFS explores as far as possible along each branch, allowing discovery and low times to detect back edges and bridges.

C Because DFS is faster than BFS in all graph problems.

D Because BFS cannot detect cycles in a graph.

💡 Hint

Think about how discovery and low times relate to DFS traversal.

DFS allows tracking the discovery time of nodes and the earliest reachable ancestor (low time), which is essential to identify 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