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

Bridges in Graph using Tarjan's Algorithm

📖 Scenario: Imagine you are a network engineer checking a computer network. You want to find all the critical connections (called bridges) in the network. A bridge is a connection that, if removed, will split the network into two parts.We will use Tarjan's algorithm to find these bridges in a graph representing the network.

🎯 Goal: Build a TypeScript program that finds all bridges in an undirected graph using Tarjan's algorithm.You will create the graph, set up helper variables, implement the core DFS logic to find bridges, and finally print the list of bridges.

📋 What You'll Learn

Create an adjacency list to represent the graph with exact edges

Create arrays for discovery time and low values with exact names

Implement Tarjan's DFS function with exact variable names

Print the list of bridges exactly as an array of pairs

💡 Why This Matters

🌍 Real World

Network engineers use bridge detection to find critical connections that can cause network failure if removed.

💼 Career

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

1

Create the graph as an adjacency list

Create a variable called graph as an array of arrays of numbers with 5 nodes (0 to 4). Add these edges exactly: 0-1, 1-2, 2-0, 1-3, 3-4.

DSA Typescript

// Your code here

Hint

Use an array of arrays where each index represents a node and contains a list of connected nodes.

2

Create helper arrays and variables

Create arrays called disc and low of length 5 filled with -1. Create a variable time set to 0. Create an empty array bridges to store pairs of numbers.

DSA Typescript

const graph: number[][] = [
  [1, 2],    // edges from node 0
  [0, 2, 3], // edges from node 1
  [0, 1],    // edges from node 2
  [1, 4],    // edges from node 3
  [3]        // edges from node 4
];
// Your code here

Hint

Use new Array(5).fill(-1) to create arrays filled with -1.

3

Implement Tarjan's DFS function to find bridges

Write a function called dfs that takes u and parent as numbers. Inside, set disc[u] and low[u] to time, then increment time. Loop over neighbors v in graph[u]. If disc[v] is -1, call dfs(v, u), update low[u] to Math.min(low[u], low[v]). If low[v] > disc[u], push [u, v] to bridges. Else if v !== parent, update low[u] to Math.min(low[u], disc[v]). Then, run dfs(0, -1).

DSA Typescript

const graph: number[][] = [
  [1, 2],    // edges from node 0
  [0, 2, 3], // edges from node 1
  [0, 1],    // edges from node 2
  [1, 4],    // edges from node 3
  [3]        // edges from node 4
];

const disc: number[] = new Array(5).fill(-1);
const low: number[] = new Array(5).fill(-1);
let time = 0;
const bridges: [number, number][] = [];

// Your code here

Hint

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

4

Print the list of bridges found

Write console.log(bridges) to print the array bridges.

DSA Typescript

const graph: number[][] = [
  [1, 2],    // edges from node 0
  [0, 2, 3], // edges from node 1
  [0, 1],    // edges from node 2
  [1, 4],    // edges from node 3
  [3]        // edges from node 4
];

const disc: number[] = new Array(5).fill(-1);
const low: number[] = new Array(5).fill(-1);
let time = 0;
const bridges: [number, number][] = [];

function dfs(u: number, parent: number): void {
  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 !== parent) {
      low[u] = Math.min(low[u], disc[v]);
    }
  }
}

dfs(0, -1);

// Your code here

Hint

The bridges in this graph are edges [1,3] and [3,4].