Articulation Points in Undirected Graphs

Problem Statement❯

In an undirected connected graph, an articulation point (or cut vertex) is a node that, when removed (along with its edges), increases the number of connected components in the graph.

Problem: Given an undirected graph with V vertices and an adjacency list adj, find all articulation points.

Indexing is 0-based, i.e., nodes are numbered from 0 to V-1.
There may be self-loops and multiple edges, but you should still identify articulation points based on connectivity.

Examples❯

Graph (Adjacency List)	Articulation Points	Description
{0:[1,2], 1:[0,2], 2:[0,1,3], 3:[2,4,5], 4:[3], 5:[3]}	[2,3]	Removing node 2 or 3 disconnects parts of the graph
{0:[1], 1:[0,2], 2:[1,3], 3:[2]}	[1,2]	Removing nodes 1 or 2 disconnects the chain
{0:[1,2], 1:[0], 2:[0]}	[0]	Node 0 connects two leaf nodes
{0:[1], 1:[0]}	[]	Two nodes connected by a single edge, neither is an articulation point
{0:[1,2], 1:[0,2], 2:[0,1]}	[]	Triangle graph, fully connected — no articulation points

Solution❯

To find articulation points, we perform a Depth-First Search (DFS) traversal and track two arrays for each node:

tin[u]: The time when node u is visited (discovery time)
low[u]: The lowest discovery time reachable from u or its descendants

We mark a node u as an articulation point if:

Case 1 (Root): If u is the root of DFS and has more than one child.
Case 2 (Bridge): If u is not root, and there's a child v such that low[v] >= tin[u].

These conditions ensure that removing u would cut off at least one subtree from the rest of the graph.

Algorithm Steps❯

Initialize tin[], low[], visited[], and timer to track DFS discovery times.
Perform DFS traversal starting from any node.
For each unvisited child v of u:

Call DFS recursively on v.
Update low[u] = min(low[u], low[v]).
Check articulation conditions for u.

For visited child v (not parent), update low[u] = min(low[u], tin[v]).
Collect all articulation points from marked vertices.

Code

JavaScript

function findArticulationPoints(V, adj) {
  let timer = 0;
  const tin = new Array(V).fill(-1);
  const low = new Array(V).fill(-1);
  const visited = new Array(V).fill(false);
  const isArticulation = new Array(V).fill(false);

  function dfs(u, parent) {
    visited[u] = true;
    tin[u] = low[u] = timer++;
    let children = 0;

    for (const v of adj[u]) {
      if (v === parent) continue;
      if (visited[v]) {
        low[u] = Math.min(low[u], tin[v]);
      } else {
        dfs(v, u);
        low[u] = Math.min(low[u], low[v]);
        if (low[v] >= tin[u] && parent !== -1) {
          isArticulation[u] = true;
        }
        children++;
      }
    }

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

  for (let i = 0; i < V; i++) {
    if (!visited[i]) {
      dfs(i, -1);
    }
  }

  const result = [];
  for (let i = 0; i < V; i++) {
    if (isArticulation[i]) result.push(i);
  }
  return result;
}

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

const V = Object.keys(graph).length;
console.log("Articulation Points:", findArticulationPoints(V, graph));

⬅ Previous TopicBridges in Graph using Tarjan's Algorithm

Next Topic ⮕Strongly Connected Components using Kosaraju's Algorithm