Bridges in Graph Tarjan's Algorithm in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the discovery time array with -1 for all nodes.

DSA Javascript

const disc = new Array(n).fill([1]);

Drag options to blanks, or click blank then click option'

Anull

B0

C-1

DInfinity

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 instead of -1 causes confusion with valid discovery times.

Using null or Infinity is not standard for discovery times.

We use -1 to mark nodes as unvisited before DFS starts.

2fill in blank

medium

Complete the code to update the low time of the current node after visiting a neighbor.

DSA Javascript

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

Drag options to blanks, or click blank then click option'

Alow[v]

Blow[u]

Cdisc[u]

Ddisc[v]

Attempts:

3 left

💡 Hint

Common Mistakes

Using disc[v] instead of low[v] misses updates from deeper recursion.

Using disc[u] or low[u] does not update based on neighbor's info.

We update low[u] with the lowest reachable discovery time from neighbor v.

3fill in blank

hard

Fix the error in the condition that detects a bridge edge between u and v.

DSA Javascript

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

Drag options to blanks, or click blank then click option'

Adisc[v]

Blow[v]

Clow[u]

Ddisc[u]

Attempts:

3 left

💡 Hint

Common Mistakes

Using disc[v] instead of low[v] misses the correct bridge condition.

Using low[u] or disc[u] incorrectly compares the wrong values.

A bridge is found if low[v] > disc[u], meaning v cannot reach u or its ancestors.

4fill in blank

hard

Fill both blanks to correctly perform DFS and update low time for back edges.

DSA Javascript

for (const v of graph[u]) {
  if (v === [1]) continue;
  if (disc[v] === -1) {
    dfs(v, u);
    low[u] = Math.min(low[u], [2]);
  } else {
    low[u] = Math.min(low[u], disc[v]);
  }
}

Drag options to blanks, or click blank then click option'

Aparent

Bdisc[u]

Clow[v]

Dv

Attempts:

3 left

💡 Hint

Common Mistakes

Not skipping parent causes infinite recursion.

Updating low[u] with disc[u] instead of low[v] misses deeper reachability.

Skip the parent node to avoid revisiting it, and update low[u] with low[v] after DFS.

5fill in blank

hard

Fill all three blanks to initialize and start DFS for all nodes in the graph.

DSA Javascript

const disc = new Array(n).fill(-1);
const low = new Array(n).fill(-1);
const bridges = [];
let time = 0;

function dfs(u, [1]) {
  disc[u] = time;
  low[u] = time;
  time++;

  for (const v of graph[u]) {
    if (disc[v] === -1) {
      dfs(v, u);
      low[u] = Math.min(low[u], low[v]);
      if (low[v] > disc[u]) {
        bridges.push([u, v]);
      }
    } else if (v !== [2]) {
      low[u] = Math.min(low[u], disc[v]);
    }
  }
}

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

Drag options to blanks, or click blank then click option'

Aparent

B-1

Cnull

Dundefined

Attempts:

3 left

💡 Hint

Common Mistakes

Using null or undefined instead of -1 for initial parent.

Using inconsistent variable names for parent.

The DFS function uses 'parent' to track the previous node; initial call uses -1 as no parent.

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