Articulation Points in Graph in DSA Typescript - Build from Scratch

Articulation Points in Graph

📖 Scenario: You are working as a network engineer. You want to find critical computers in a network. If these computers fail, the network breaks into disconnected parts. These critical computers are called articulation points.The network is represented as a graph where each computer is a node and connections are edges.

🎯 Goal: Build a TypeScript program to find all articulation points in a given undirected graph using DFS and low-link values.

📋 What You'll Learn

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

Add a variable to track discovery time of nodes

Implement DFS to find articulation points using discovery and low arrays

Print the list of articulation points found in the graph

💡 Why This Matters

🌍 Real World

Finding articulation points helps identify critical nodes in networks like computer networks, social networks, or transportation systems where failure of these nodes disrupts connectivity.

💼 Career

Network engineers, system architects, and software developers use articulation point algorithms to design robust and fault-tolerant systems.

1

Create the graph as an adjacency list

Create a variable called graph as a Map<number, number[]> with these exact edges:
0 connected to 1 and 2,
1 connected to 0, 2, and 3,
2 connected to 0 and 1,
3 connected to 1 and 4,
4 connected to 3 and 5,
5 connected to 4

DSA Typescript

// Your code here

Hint

Use new Map() with an array of key-value pairs where keys are node numbers and values are arrays of connected nodes.

2

Add discovery time and low arrays

Create two arrays called disc and low of length 6 filled with -1. Also create a boolean array called visited of length 6 filled with false. Create a variable time and set it to 0.

DSA Typescript

const graph: Map = new Map([
  [0, [1, 2]],
  [1, [0, 2, 3]],
  [2, [0, 1]],
  [3, [1, 4]],
  [4, [3, 5]],
  [5, [4]]
]);
// Your code here

Hint

Use Array(6).fill(-1) for disc and low, and Array(6).fill(false) for visited.

3

Implement DFS to find articulation points

Write a function called dfs with parameters u: number, parent: number | null, and ap: boolean[]. Inside, mark visited[u] as true, set disc[u] and low[u] to time, then increment time. Use a variable children set to 0. For each v in graph.get(u) || [], if v is not visited, increment children, call dfs(v, u, ap), update low[u] to Math.min(low[u], low[v]). If parent !== null and low[v] >= disc[u], set ap[u] to true. Else if v !== parent, update low[u] to Math.min(low[u], disc[v]). After the loop, if parent === null and children > 1, set ap[u] to true.

DSA Typescript

const graph: Map = new Map([
  [0, [1, 2]],
  [1, [0, 2, 3]],
  [2, [0, 1]],
  [3, [1, 4]],
  [4, [3, 5]],
  [5, [4]]
]);

const disc: number[] = Array(6).fill(-1);
const low: number[] = Array(6).fill(-1);
const visited: boolean[] = Array(6).fill(false);
let time = 0;

// Your code here

Hint

Follow the standard DFS articulation point algorithm using discovery and low arrays.

4

Find and print articulation points

Create a boolean array called ap of length 6 filled with false. Loop i from 0 to 5, if visited[i] is false, call dfs(i, null, ap). Then create an array result containing all indices i where ap[i] is true. Finally, print result.

DSA Typescript

const graph: Map = new Map([
  [0, [1, 2]],
  [1, [0, 2, 3]],
  [2, [0, 1]],
  [3, [1, 4]],
  [4, [3, 5]],
  [5, [4]]
]);

const disc: number[] = Array(6).fill(-1);
const low: number[] = Array(6).fill(-1);
const visited: boolean[] = Array(6).fill(false);
let time = 0;

function dfs(u: number, parent: number | null, ap: boolean[]): void {
  visited[u] = true;
  disc[u] = time;
  low[u] = time;
  time++;
  let children = 0;

  for (const v of graph.get(u) || []) {
    if (!visited[v]) {
      children++;
      dfs(v, u, ap);
      low[u] = Math.min(low[u], low[v]);

      if (parent !== null && low[v] >= disc[u]) {
        ap[u] = true;
      }
    } else if (v !== parent) {
      low[u] = Math.min(low[u], disc[v]);
    }
  }

  if (parent === null && children > 1) {
    ap[u] = true;
  }
}

// Your code here

Hint

Run DFS from all unvisited nodes, collect articulation points in ap, then print their indices.