Bridges in Graph Tarjan's Algorithm in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a bridge in a graph?

A bridge is an edge in a graph that, if removed, increases the number of connected components. It means the edge is critical for keeping the graph connected.

intermediate

What is the main idea behind Tarjan's algorithm for finding bridges?

Tarjan's algorithm uses Depth-First Search (DFS) to assign discovery times and low values to each node. An edge is a bridge if the low value of the connected node is greater than the discovery time of the current node.

intermediate

In Tarjan's algorithm, what does the 'low' value represent?

The 'low' value of a node is the earliest discovery time reachable from that node by following the DFS tree edges and at most one back edge.

advanced

Why do we compare low[v] > disc[u] to find a bridge between u and v?

If low[v] > disc[u], it means there is no back edge from v or its descendants to u or its ancestors, so removing edge (u, v) disconnects the graph, making it a bridge.

beginner

What data structures are commonly used in Tarjan's algorithm for bridges?

Arrays or lists to store discovery times (disc), low values (low), a visited set or array, and adjacency lists to represent the graph.

What happens if you remove a bridge edge from a connected graph?

A The graph becomes cyclic

B The graph remains connected

C The graph becomes a tree

D The graph becomes disconnected

Removing a bridge edge increases the number of connected components, so the graph becomes disconnected.

In Tarjan's algorithm, what does the discovery time represent?

A The number of edges connected to a node

B The shortest distance from the start node

C The order in which nodes are visited in DFS

D The number of bridges found so far

Discovery time is the order in which nodes are first visited during DFS traversal.

Which condition identifies an edge (u, v) as a bridge in Tarjan's algorithm?

A low[v] > disc[u]

B low[u] > disc[v]

C disc[u] > disc[v]

D low[u] == low[v]

If low[v] > disc[u], edge (u, v) is a bridge.

What is the time complexity of Tarjan's algorithm for finding bridges?

A O(V + E)

B O(V^2)

C O(E^2)

D O(log V)

Tarjan's algorithm runs in linear time relative to vertices and edges, O(V + E).

Which traversal method does Tarjan's algorithm use?

A Breadth-First Search (BFS)

B Depth-First Search (DFS)

C Dijkstra's algorithm

D Prim's algorithm

Tarjan's algorithm uses DFS to explore the graph.

Explain how Tarjan's algorithm finds bridges in a graph step-by-step.

Think about how DFS helps track back edges and discovery order.

Describe the role of 'low' values in detecting bridges and why they are important.

Focus on what low values tell us about connectivity.

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