Bridges in Graph Tarjan's Algorithm in DSA Javascript - Build from Scratch

Bridges in Graph Tarjan's Algorithm

📖 Scenario: You are working as a network engineer. You want to find critical connections in a network. These connections, called bridges, if removed, will split the network into parts. Finding these bridges helps you know which connections are very important.

🎯 Goal: Build a program that finds all bridges in a given undirected graph using Tarjan's algorithm.

📋 What You'll Learn

Create a graph as an adjacency list with exact nodes and edges

Create variables to track discovery times and low values for each node

Implement Tarjan's DFS to find bridges using recursion

Print the list of bridges found in the graph

💡 Why This Matters

🌍 Real World

Network engineers use bridge detection to find critical connections that, if broken, can split the network and cause failures.

💼 Career

Understanding Tarjan's algorithm and graph traversal is important for roles in network design, cybersecurity, and software engineering involving graph data.

1

Create the graph as an adjacency list

Create a variable called graph as an object representing the undirected graph with these exact edges: 0 connected to 1 and 2, 1 connected to 0 and 2, 2 connected to 0, 1, and 3, and 3 connected to 2.

DSA Javascript

# Your code here

Hint

Use an object where keys are node numbers and values are arrays of connected nodes.

2

Create discovery and low arrays and a time counter

Create variables called discovery and low as arrays of length 4 filled with -1, and a variable called time set to 0.

DSA Javascript

const graph = {
  0: [1, 2],
  1: [0, 2],
  2: [0, 1, 3],
  3: [2]
};
# Your code here

Hint

Use arrays with -1 to mark unvisited nodes and a number variable for time.

3

Implement Tarjan's DFS function to find bridges

Write a function called dfs that takes node and parent as parameters. Inside, set discovery[node] and low[node] to time, then increment time. Loop over neighbors of node in graph[node]. If neighbor is parent, continue. If discovery[neighbor] is -1, call dfs(neighbor, node) recursively, then update low[node] to the minimum of low[node] and low[neighbor]. If low[neighbor] is greater than discovery[node], add the edge [node, neighbor] to a global array called bridges. Else, update low[node] to the minimum of low[node] and discovery[neighbor]. Also, create an empty array called bridges before the function.

DSA Javascript

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

const discovery = [-1, -1, -1, -1];
const low = [-1, -1, -1, -1];
let time = 0;

// Your code here

Hint

Follow Tarjan's algorithm steps carefully. Use recursion and update discovery and low arrays.

4

Run DFS and print the bridges

Run dfs(0, -1) to start DFS from node 0 with parent -1. Then print the bridges array using console.log(bridges).

DSA Javascript

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

const discovery = [-1, -1, -1, -1];
const low = [-1, -1, -1, -1];
let time = 0;

const bridges = [];

function dfs(node, parent) {
  discovery[node] = time;
  low[node] = time;
  time++;

  for (const neighbor of graph[node]) {
    if (neighbor === parent) continue;

    if (discovery[neighbor] === -1) {
      dfs(neighbor, node);
      low[node] = Math.min(low[node], low[neighbor]);

      if (low[neighbor] > discovery[node]) {
        bridges.push([node, neighbor]);
      }
    } else {
      low[node] = Math.min(low[node], discovery[neighbor]);
    }
  }
}

// Your code here

Hint

Start DFS from node 0 with parent -1. Then print the bridges array.

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