Articulation Points in Graph in DSA Javascript

Mental Model

An articulation point is a node in a graph that, if removed, breaks the graph into more pieces. It shows where the graph is fragile.

Analogy: Imagine a city connected by roads. An articulation point is like a critical bridge or intersection; if it closes, parts of the city become unreachable from each other.

Graph:
  1
 / \
2 - 3
|
4

Articulation points: 2

1 -> 2 -> 3
|
4

Dry Run Walkthrough

Input: Graph with edges: 1-2, 1-3, 2-3, 2-4

Goal: Find nodes that, if removed, increase the number of disconnected parts in the graph

Step 1: Start DFS from node 1, set discovery time and low value

Visited: 1 (disc=1, low=1)
Stack: [1]

Why: We begin exploring the graph from node 1 to find articulation points

Step 2: Visit node 2 from 1, set discovery and low values

Visited: 1 (disc=1, low=1), 2 (disc=2, low=2)
Stack: [1,2]

Why: We explore neighbors to find back edges and update low values

Step 3: Visit node 3 from 2, set discovery and low values

Visited: 1 (disc=1, low=1), 2 (disc=2, low=2), 3 (disc=3, low=3)
Stack: [1,2,3]

Why: Continue DFS to explore all nodes

Step 4: Node 3 has neighbor 1 already visited, update low[3] to min(low[3], disc[1]) = 1

Visited: 1 (disc=1, low=1), 2 (disc=2, low=2), 3 (disc=3, low=1)
Stack: [1,2,3]

Why: Back edge found from 3 to 1, update low to reflect cycle

Step 5: Backtrack to node 2, update low[2] to min(low[2], low[3]) = 1

Visited: 1 (disc=1, low=1), 2 (disc=2, low=1), 3 (disc=3, low=1)
Stack: [1,2]

Why: Low value of child 3 affects parent 2

Step 6: Visit node 4 from 2, set discovery and low values

Visited: 1 (disc=1, low=1), 2 (disc=2, low=1), 3 (disc=3, low=1), 4 (disc=4, low=4)
Stack: [1,2,4]

Why: Explore all neighbors to find articulation points

Step 7: Node 4 has no unvisited neighbors, backtrack and update low[2] to min(low[2], low[4]) = 1

Visited: 1 (disc=1, low=1), 2 (disc=2, low=1), 3 (disc=3, low=1), 4 (disc=4, low=4)
Stack: [1,2]

Why: Backtracking updates low values to detect articulation points

Step 8: Check articulation point condition for node 2: low[4] >= disc[2] (4 >= 2) true, mark 2 as articulation point

Articulation points: 2
Stack: [1,2]

Why: Node 2 is a cut vertex because removing it disconnects node 4

Step 9: Backtrack to node 1, update low[1] to min(low[1], low[2]) = 1

Visited: 1 (disc=1, low=1), 2 (disc=2, low=1), 3 (disc=3, low=1), 4 (disc=4, low=4)
Stack: [1]

Why: Update low value of root after exploring children

Step 10: Check articulation point condition for root node 1: has only one child (2), do not mark 1 as articulation point

Articulation points: 2
Stack: [1]

Why: Root is an articulation point only if it has more than one child in the DFS tree

Result:

Articulation points: 2

Annotated Code

DSA Javascript

class Graph {
  constructor(vertices) {
    this.V = vertices;
    this.adj = new Array(vertices + 1).fill(0).map(() => []);
  }

  addEdge(u, v) {
    this.adj[u].push(v);
    this.adj[v].push(u);
  }

  APUtil(u, visited, disc, low, parent, ap, time) {
    visited[u] = true;
    disc[u] = low[u] = ++time.count;
    let children = 0;

    for (const v of this.adj[u]) {
      if (!visited[v]) {
        children++;
        parent[v] = u;
        this.APUtil(v, visited, disc, low, parent, ap, time);
        low[u] = Math.min(low[u], low[v]);

        if (parent[u] === -1 && children > 1) ap[u] = true;

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

  findAPs() {
    const visited = new Array(this.V + 1).fill(false);
    const disc = new Array(this.V + 1).fill(Infinity);
    const low = new Array(this.V + 1).fill(Infinity);
    const parent = new Array(this.V + 1).fill(-1);
    const ap = new Array(this.V + 1).fill(false);
    const time = { count: 0 };

    for (let i = 1; i <= this.V; i++) {
      if (!visited[i]) this.APUtil(i, visited, disc, low, parent, ap, time);
    }

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

// Driver code
const g = new Graph(4);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(2, 3);
g.addEdge(2, 4);

const articulationPoints = g.findAPs();
console.log('Articulation points:', articulationPoints.join(', '));

visited[u] = true; disc[u] = low[u] = ++time.count;

Mark node u as visited and set discovery and low times

for (const v of this.adj[u]) {

Traverse all neighbors of u

if (!visited[v]) {

If neighbor v is not visited, explore it recursively

children++; parent[v] = u; this.APUtil(v, visited, disc, low, parent, ap, time);

Count children and recurse to update low values

low[u] = Math.min(low[u], low[v]);

Update low[u] based on child's low value

if (parent[u] === -1 && children > 1) ap[u] = true;

Root node with multiple children is articulation point

if (parent[u] !== -1 && low[v] >= disc[u]) ap[u] = true;

Non-root node is articulation point if child's low >= discovery of u

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

Update low[u] for back edge to ancestor

Output

Articulation points: 2

Complexity Analysis

Time: O(V + E) because each vertex and edge is visited once during DFS

Space: O(V) for arrays storing visited, discovery, low, parent, and articulation points

vs Alternative: Naive approach checks connectivity after removing each node, costing O(V*(V+E)) which is much slower

Edge Cases

Graph with no edges

No articulation points because no node removal disconnects graph

DSA Javascript

if (!visited[i]) this.APUtil(i, visited, disc, low, parent, ap, time);

Single node graph

No articulation points because graph is already minimal

DSA Javascript

if (!visited[i]) this.APUtil(i, visited, disc, low, parent, ap, time);

Graph with multiple disconnected components

Algorithm runs DFS on each component separately to find articulation points

DSA Javascript

for (let i = 1; i <= this.V; i++) { if (!visited[i]) this.APUtil(i, visited, disc, low, parent, ap, time); }

When to Use This Pattern

When a problem asks for nodes whose removal breaks connectivity, use articulation points detection with DFS and low-link values.

Common Mistakes

Mistake: Not updating low[u] for back edges to ancestors
Fix: Add else if condition to update low[u] with disc[v] when v is visited and not parent

Mistake: Marking root node as articulation point without checking number of children
Fix: Only mark root as articulation point if it has more than one child in DFS tree

Summary

Find nodes in a graph that disconnect it if removed.

Use when you need to identify critical points in network connectivity.

Track discovery and low times during DFS to detect articulation points.

Practice

1. What is an articulation point in a graph?

easy

A. A vertex that, when removed, increases the number of connected components

B. A vertex with the highest degree in the graph

C. A vertex connected to all other vertices

D. A vertex that has no edges connected to it

Solution

1. Step 1: Understand the definition of articulation point

   An articulation point is a vertex that, if removed, increases the number of disconnected parts in the graph.

2. Step 2: Compare options with definition

   Only A vertex that, when removed, increases the number of connected components matches this definition exactly.

3. Final Answer:

   A vertex that, when removed, increases the number of connected components -> Option A

4. Quick Check:

   Articulation point = vertex increasing components when removed [OK]

Hint: Articulation point breaks graph connectivity when removed [OK]

Common Mistakes:

• Confusing articulation point with highest degree vertex
• Thinking articulation point is always connected to all vertices
• Assuming isolated vertices are articulation points

2. Which of the following is the correct way to initialize a graph adjacency list in JavaScript for articulation point detection?

easy

A. const graph = Array.from({ length: n }, () => []);

B. const graph = new Array(n).fill([]);

C. const graph = Array(n).fill(null);

D. const graph = new Map();

Solution

1. Step 1: Understand adjacency list initialization

   We need an array of separate empty arrays for each vertex to store neighbors.

2. Step 2: Analyze options

   const graph = new Array(n).fill([]); uses fill([]), which fills all positions with the same array reference (wrong). const graph = Array.from({ length: n }, () => []); uses Array.from with a function returning new arrays, so each vertex has its own array (correct). const graph = Array(n).fill(null); fills with null, not arrays. const graph = new Map(); uses Map, which is valid but not the typical adjacency list array.

3. Final Answer:

   const graph = Array.from({ length: n }, () => []); -> Option A

4. Quick Check:

   Separate arrays per vertex = const graph = Array.from({ length: n }, () => []); [OK]

Hint: Use Array.from with function to create separate arrays [OK]

Common Mistakes:

• Using fill([]) creates shared references causing bugs
• Initializing with null instead of arrays
• Confusing Map with adjacency list array

3. Consider the following JavaScript code snippet for finding articulation points in a graph with 4 vertices (0 to 3):

const graph = [[1,2],[0],[0,3],[2]];
const visited = [false, false, false, false];
const disc = [0, 0, 0, 0];
const low = [0, 0, 0, 0];
const parent = [-1, -1, -1, -1];
const ap = [false, false, false, false];
let time = 0;

function dfs(u) {
  visited[u] = true;
  disc[u] = low[u] = ++time;
  let children = 0;
  for (const v of graph[u]) {
    if (!visited[v]) {
      children++;
      parent[v] = u;
      dfs(v);
      low[u] = Math.min(low[u], low[v]);
      if (parent[u] === -1 && children > 1) ap[u] = true;
      if (parent[u] !== -1 && low[v] >= disc[u]) ap[u] = true;
    } else if (v !== parent[u]) {
      low[u] = Math.min(low[u], disc[v]);
    }
  }
}

dfs(0);
console.log(ap);

What will be the output printed?

medium

A. [false, false, false, false]

B. [true, false, true, false]

C. [true, true, false, false]

D. [false, true, true, false]

Solution

1. Step 1: Trace DFS and articulation point logic

   Start DFS at 0: children are 1 and 2. For root (0), if children > 1, ap[0] = true. So 0 is articulation point. For vertex 2, low[3] >= disc[2] triggers ap[2] = true.

2. Step 2: Determine articulation points array

   Vertices 0 and 2 are articulation points, others are not. So ap = [true, false, true, false].

3. Final Answer:

   [true, false, true, false] -> Option B

4. Quick Check:

   Root with >1 child and low[v]>=disc[u] mark articulation points [OK]

Hint: Root with multiple children and low[v]>=disc[u] mark articulation points [OK]

Common Mistakes:

• Ignoring root special case with multiple children
• Confusing low and disc arrays
• Not updating low[u] on back edges

4. The following code attempts to find articulation points but has a bug:

function dfs(u) {
  visited[u] = true;
  disc[u] = low[u] = ++time;
  let children = 0;
  for (const v of graph[u]) {
    if (!visited[v]) {
      children++;
      parent[v] = u;
      dfs(v);
      low[u] = Math.min(low[u], low[v]);
      if (low[v] >= disc[u]) ap[u] = true;
    } else if (v !== parent[u]) {
      low[u] = Math.min(low[u], disc[v]);
    }
  }
}

What is the bug in this code?

medium

A. It does not mark visited vertices

B. It uses '>' instead of '>=' in the articulation point check

C. It does not update parent array correctly

D. It misses the root vertex articulation point condition

Solution

1. Step 1: Analyze articulation point conditions

   The code checks if low[v] >= disc[u] to mark articulation points but misses the special case for root vertex which requires children > 1.

2. Step 2: Identify missing root condition

   Without checking if u is root and has multiple children, root articulation points won't be detected.

3. Final Answer:

   It misses the root vertex articulation point condition -> Option D

4. Quick Check:

   Root articulation point requires separate children > 1 check [OK]

Hint: Always check root vertex children count separately [OK]

Common Mistakes:

• Forgetting root vertex special case
• Using wrong comparison operator in articulation check
• Not updating parent array before DFS call

5. Given a connected undirected graph with 5 vertices and edges: 0-1, 1-2, 2-0, 1-3, 3-4, which vertices are articulation points?

hard

A. [1]

B. [0, 1, 3]

C. [1, 3]

D. [3, 4]

Solution

1. Step 1: Visualize the graph and connections

   Vertices 0,1,2 form a triangle. Vertex 1 connects to 3, which connects to 4.

2. Step 2: Identify articulation points

   Removing 1 disconnects 3 and 4 from the rest, so 1 is articulation point. Removing 3 disconnects 4, so 3 is articulation point. 0,2,4 are not articulation points.

3. Final Answer:

   [1, 3] -> Option C

4. Quick Check:

   Vertices connecting subgraphs are articulation points [OK]

Hint: Articulation points connect separate graph parts [OK]

Common Mistakes:

• Including vertices inside cycles as articulation points
• Missing leaf node articulation points
• Confusing articulation points with bridges