Articulation Points in Graph in DSA Typescript

Mental Model

An articulation point is a node in a network that, if removed, breaks the network into separate parts.

Analogy: Imagine a city connected by roads. Some intersections are so important that if they close, parts of the city become unreachable from each other.

Graph:
  1
 / \
2 - 3
|
4

Articulation points: 2 because removing 2 disconnects 4 from the rest.

Dry Run Walkthrough

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

Goal: Find all 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 to 1

discovery: {1:1}, low: {1:1}, visited: {1}, parent: {1:null}

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

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

discovery: {1:1, 2:2}, low: {1:1, 2:2}, visited: {1,2}, parent: {1:null, 2:1}

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

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

discovery: {1:1, 2:2, 3:3}, low: {1:1, 2:2, 3:3}, visited: {1,2,3}, parent: {1:null, 2:1, 3:2}

Why: Continue DFS to explore all nodes

Step 4: Node 3 has neighbor 1 which is visited and not parent, update low[3] to min(low[3], discovery[1]) = 1

low: {1:1, 2:2, 3:1}

Why: Back edge found from 3 to 1, update low to reflect earliest reachable ancestor

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

low: {1:1, 2:1, 3:1}

Why: Low value of child affects parent's low value

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

discovery: {1:1, 2:2, 3:3, 4:4}, low: {1:1, 2:1, 3:1, 4:4}, visited: {1,2,3,4}, parent: {1:null, 2:1, 3:2, 4:2}

Why: Explore all nodes to find articulation points

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

low: {1:1, 2:1, 3:1, 4:4}

Why: Update low values after exploring child

Step 8: Check articulation point condition at node 2: low[4] >= discovery[2] (4 >= 2), so node 2 is articulation point

Articulation points: {2}

Why: If child's low is not less than parent's discovery, parent is articulation point

Result:

Articulation points: 2
Graph state unchanged

Annotated Code

DSA Typescript

class Graph {
  adjacencyList: Map<number, number[]>;
  time: number;
  constructor() {
    this.adjacencyList = new Map();
    this.time = 0;
  }

  addEdge(u: number, v: number) {
    if (!this.adjacencyList.has(u)) this.adjacencyList.set(u, []);
    if (!this.adjacencyList.has(v)) this.adjacencyList.set(v, []);
    this.adjacencyList.get(u)!.push(v);
    this.adjacencyList.get(v)!.push(u);
  }

  findArticulationPoints(): number[] {
    const visited = new Map<number, boolean>();
    const disc = new Map<number, number>();
    const low = new Map<number, number>();
    const parent = new Map<number, number | null>();
    const ap = new Set<number>();

    const dfs = (u: number) => {
      visited.set(u, true);
      this.time++;
      disc.set(u, this.time); // discovery time
      low.set(u, this.time);  // low value
      let children = 0;

      for (const v of this.adjacencyList.get(u) || []) {
        if (!visited.get(v)) {
          children++;
          parent.set(v, u);
          dfs(v);
          low.set(u, Math.min(low.get(u)!, low.get(v)!)); // update low[u]

          // If u is root and has two or more children
          if (parent.get(u) === null && children > 1) {
            ap.add(u);
          }

          // If u is not root and low[v] >= disc[u]
          if (parent.get(u) !== null && low.get(v)! >= disc.get(u)!) {
            ap.add(u);
          }
        } else if (v !== parent.get(u)) {
          low.set(u, Math.min(low.get(u)!, disc.get(v)!)); // back edge
        }
      }
    };

    for (const node of this.adjacencyList.keys()) {
      if (!visited.get(node)) {
        parent.set(node, null);
        dfs(node);
      }
    }

    return Array.from(ap).sort((a, b) => a - b);
  }
}

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

const articulationPoints = graph.findArticulationPoints();
console.log("Articulation points:", articulationPoints.join(", "));

visited.set(u, true); this.time++; disc.set(u, this.time); low.set(u, this.time);

Mark node u visited and set discovery and low times

for (const v of this.adjacencyList.get(u) || []) {

Traverse all neighbors of u

if (!visited.get(v)) {

If neighbor v not visited, explore it

children++; parent.set(v, u); dfs(v);

Count children and recurse DFS on v

low.set(u, Math.min(low.get(u)!, low.get(v)!));

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

if (parent.get(u) === null && children > 1) { ap.add(u); }

Root node with multiple children is articulation point

if (parent.get(u) !== null && low.get(v)! >= disc.get(u)!) { ap.add(u); }

Non-root node where child's low >= discovery is articulation point

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

Update low[u] for back edge to ancestor

Output

Articulation points: 2

Complexity Analysis

Time: O(V + E) because we visit each node and edge once during DFS

Space: O(V) for storing discovery, low, parent, visited, and recursion stack

vs Alternative: Naive approach checks connectivity after removing each node, costing O(V*(V+E)), much slower than DFS-based O(V+E)

Edge Cases

Graph with no edges

No articulation points because no node removal disconnects graph

DSA Typescript

if (!visited.get(node)) { parent.set(node, null); dfs(node); }

Graph with single node

No articulation points because removing the only node leaves empty graph

DSA Typescript

if (!visited.get(node)) { parent.set(node, null); dfs(node); }

Graph with multiple disconnected components

Algorithm runs DFS on each component separately and finds articulation points in each

DSA Typescript

for (const node of this.adjacencyList.keys()) { if (!visited.get(node)) { parent.set(node, null); dfs(node); } }

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 handling root node separately for articulation point condition
Fix: Check if root has more than one child to mark it as articulation point

Mistake: Updating low value incorrectly by not considering back edges
Fix: Update low[u] with discovery time of visited neighbors that are not parent

Summary

Find nodes in a graph that disconnect it if removed.

Use when you want to identify critical points in networks or connectivity.

Use DFS with discovery and low times to detect articulation points efficiently.