Articulation Points in Graph in DSA Typescript - Execution Trace

Concept Flow - Articulation Points in Graph

Start DFS at node u

↓

Mark u visited, set disc[u

↓

For each neighbor v of u

↓

If v not visited

↓

Set parent[v

↓

DFS(v)

↓

Check articulation condition

↓

If u is root and has >1 child, u is articulation

↓

If u not root and low[v

↓

Repeat for all nodes

↓

Output all articulation points

This flow shows how DFS visits nodes, updates discovery and low times, and identifies articulation points by checking conditions on low and discovery values.

Execution Sample

DSA Typescript

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

This code runs DFS from node u, tracks discovery and low times, and marks articulation points based on conditions.

Execution Table

Step	Operation	Node Visited	Parent	disc[]	low[]	Children Count	Articulation Points	Visual State
1	Start DFS at node 0	0	-1	[0:0,1:-,2:-,3:-,4:-]	[0:0,1:-,2:-,3:-,4:-]	0	[]	0(visited)
2	Visit neighbor 1 of 0	1	0	[0:0,1:1,2:-,3:-,4:-]	[0:0,1:1,2:-,3:-,4:-]	1	[]	0->1
3	Visit neighbor 2 of 1	2	1	[0:0,1:1,2:2,3:-,4:-]	[0:0,1:1,2:2,3:-,4:-]	1	[]	0->1->2
4	Visit neighbor 3 of 2	3	2	[0:0,1:1,2:2,3:3,4:-]	[0:0,1:1,2:2,3:3,4:-]	1	[]	0->1->2->3
5	Visit neighbor 4 of 3	4	3	[0:0,1:1,2:2,3:3,4:4]	[0:0,1:1,2:2,3:3,4:4]	0	[]	0->1->2->3->4
6	Backtrack from 4 to 3	4	3	[0:0,1:1,2:2,3:3,4:4]	[0:0,1:1,2:2,3:3,4:4]	0	[]	0->1->2->3->4
7	Update low[3] = min(low[3], low[4])	3	2	[0:0,1:1,2:2,3:3,4:4]	[0:0,1:1,2:2,3:3,4:4]	1	[]	0->1->2->3->4
8	Check articulation for 3	3	2	[0:0,1:1,2:2,3:3,4:4]	[0:0,1:1,2:2,3:3,4:4]	1	[3]	Articulation point at 3 (low[4] >= disc[3])
9	Backtrack from 3 to 2	3	2	[0:0,1:1,2:2,3:3,4:4]	[0:0,1:1,2:2,3:3,4:4]	1	[3]	0->1->2->3->4
10	Update low[2] = min(low[2], low[3])	2	1	[0:0,1:1,2:2,3:3,4:4]	[0:0,1:1,2:2,3:3,4:4]	1	[3]	0->1->2->3->4
11	Check articulation for 2	2	1	[0:0,1:1,2:2,3:3,4:4]	[0:0,1:1,2:2,3:3,4:4]	1	[2,3]	Articulation point at 2 (low[3] >= disc[2])
12	Backtrack from 2 to 1	2	1	[0:0,1:1,2:2,3:3,4:4]	[0:0,1:1,2:2,3:3,4:4]	1	[2,3]	0->1->2->3->4
13	Update low[1] = min(low[1], low[2])	1	0	[0:0,1:1,2:2,3:3,4:4]	[0:0,1:1,2:2,3:3,4:4]	1	[2,3]	0->1->2->3->4
14	Check articulation for 1	1	0	[0:0,1:1,2:2,3:3,4:4]	[0:0,1:1,2:2,3:3,4:4]	1	[1,2,3]	Articulation point at 1 (low[2] >= disc[1])
15	Backtrack from 1 to 0	1	0	[0:0,1:1,2:2,3:3,4:4]	[0:0,1:1,2:2,3:3,4:4]	1	[1,2,3]	0->1->2->3->4
16	Check articulation for 0	0	-1	[0:0,1:1,2:2,3:3,4:4]	[0:0,1:1,2:2,3:3,4:4]	1	[1,2,3]	No articulation at 0 (only 1 child)
17	End DFS	-	-	[0:0,1:1,2:2,3:3,4:4]	[0:0,1:1,2:2,3:3,4:4]	-	[1,2,3]	All nodes visited, articulation points identified

💡 DFS completed for all nodes, articulation points 1,2,3 identified based on low and disc arrays

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
visited	[false,false,false,false,false]	[true,false,false,false,false]	[true,true,false,false,false]	[true,true,true,false,false]	[true,true,true,true,false]	[true,true,true,true,true]	[true,true,true,true,true]
disc	[-,-,-,-,-]	[0,-,-,-,-]	[0,1,-,-,-]	[0,1,2,-,-]	[0,1,2,3,-]	[0,1,2,3,4]	[0,1,2,3,4]
low	[-,-,-,-,-]	[0,-,-,-,-]	[0,1,-,-,-]	[0,1,2,-,-]	[0,1,2,3,-]	[0,1,2,3,4]	[0,1,2,3,4]
parent	[-1,-1,-1,-1,-1]	[-1,-1,-1,-1,-1]	[-1,0,-1,-1,-1]	[-1,0,1,-1,-1]	[-1,0,1,2,-1]	[-1,0,1,2,3]	[-1,0,1,2,3]
children count	0	0	1	1	1	0	N/A
articulation	[false,false,false,false,false]	[false,false,false,false,false]	[false,false,false,false,false]	[false,false,false,false,false]	[false,false,false,false,false]	[false,false,false,false,false]	[false,true,true,true,false]

Key Moments - 3 Insights

Why do we check if low[v] >= disc[u] to decide if u is an articulation point?

Because if low[v] (lowest reachable discovery time from v) is greater or equal to disc[u], it means v and its subtree cannot reach an ancestor of u, so removing u disconnects the graph. See execution_table rows 8, 11, 14 where low[v] >= disc[u] triggers articulation points.

Why is the root node an articulation point only if it has more than one child?

The root is special because it has no parent. If it has more than one child, removing it disconnects those children. This is shown in execution_table row 16 where root's children count is checked.

Why do we update low[u] with disc[v] when v is already visited and not parent?

This means there's a back edge to an ancestor, so low[u] is updated to the earliest discovery time reachable. This prevents false articulation detection.

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what is the value of low[3] after update?

A 2

B 3

C 4

D 1

💡 Hint

Check the 'low[]' column at step 7 in execution_table

At which step does node 2 get marked as visited?

A Step 4

B Step 2

C Step 3

D Step 5

💡 Hint

Look at the 'Node Visited' column in execution_table for when node 2 appears

If node 0 had two children instead of one, what would change in the articulation points?

A Node 0 would be marked as articulation point

B Node 1 would be marked as articulation point

C No change in articulation points

D Node 4 would be marked as articulation point

💡 Hint

Refer to key_moments about root node articulation condition and execution_table step 16

Concept Snapshot

Articulation Points in Graph:
- Use DFS to assign discovery (disc) and low values
- low[u] = earliest visited vertex reachable from u
- u is articulation if:
  * u is root and has >1 child
  * u not root and low[v] >= disc[u] for any child v
- Helps find critical nodes disconnecting graph
- Track parent, disc, low, visited arrays during DFS

Full Transcript

Articulation points are nodes in a graph which, if removed, increase the number of connected components. We find them using a DFS traversal that assigns each node a discovery time and a low value. The low value tells the earliest visited node reachable from that node. During DFS, if a node u is root and has more than one child, it is an articulation point. Also, if u is not root and for any child v, low[v] is greater or equal to disc[u], then u is an articulation point. We track these values and mark articulation points accordingly. This process helps identify critical nodes in networks.