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

Visualization Player

Solution❯

Understanding the Problem

We are given an undirected graph. Our goal is to find all the articulation points in this graph. An articulation point (or cut vertex) is a node that, if removed, increases the number of connected components in the graph.

In simple terms, these are the critical nodes that hold parts of the graph together. If any of them are removed, some nodes may no longer be reachable from others.

This is especially useful in network design and fault-tolerant systems where you want to identify single points of failure.

Step-by-Step Solution with Example

step 1: Represent the graph

We begin by representing the graph using an adjacency list. For example, let's take this graph:

{
  0: [1, 2],
  1: [0, 2],
  2: [0, 1, 3, 5],
  3: [2, 4],
  4: [3],
  5: [2, 6, 8],
  6: [5, 7],
  7: [6],
  8: [5]
}

This graph has 9 nodes (0 to 8), and is connected in such a way that removing some nodes would disconnect parts of it.

step 2: Perform DFS traversal and track timestamps

We use Depth-First Search (DFS) to explore the graph and keep track of:

tin[u]: The discovery time of node u
low[u]: The lowest discovery time reachable from u or any of its descendants

We initialize both of these arrays with -1 and use a global timer to assign timestamps as we go.

step 3: Apply articulation point conditions during DFS

While traversing each node u, we apply the following logic:

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

step 4: Update low values properly

After visiting a neighbor v of u, we update low[u] based on:

If v is a child: low[u] = min(low[u], low[v])
If v is already visited and is not parent of u: low[u] = min(low[u], tin[v])

step 5: Collect all articulation points

We use a boolean array isArticulation[u] to mark nodes that satisfy the above conditions. After DFS is complete, we collect all nodes marked as articulation points.

Edge Cases

Single Node: A graph with only one node has no articulation points.
Disconnected Graph: Apply DFS from every unvisited node to ensure all components are covered.
Tree Graph: In a tree, all non-leaf nodes (except the root with one child) can be articulation points.
Cyclic Graph: Presence of back edges affects the low values and prevents over-marking articulation points.

Finally

The key to solving this problem is understanding how DFS works in combination with discovery and low times. By tracking when we visit a node and the lowest point reachable from it, we can detect where the graph would split if a node is removed.

This method is efficient (O(V + E)) and elegant, using classic DFS with a few smart checks to find critical points in any connected or disconnected undirected 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

Comments

Loading comments...