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.

Practice

1. What is an articulation point (or cut vertex) 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, breaks the graph into more pieces (connected components).

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 connects to all vertices
• Assuming isolated vertex is articulation point

2. Which of the following is the correct TypeScript function signature to find articulation points in an undirected graph represented as adjacency list?

easy

A. function findArticulationPoints(graph: number): number[]

B. function findArticulationPoints(graph: number[][]): void

C. function findArticulationPoints(graph: string): number[]

D. function findArticulationPoints(graph: Map): number[]

Solution

1. Step 1: Identify the graph representation type

   An adjacency list is best represented as a Map from node number to array of connected nodes.

2. Step 2: Check function signature compatibility

   function findArticulationPoints(graph: Map): number[] uses Map and returns number[] which fits the problem.

3. Final Answer:

   function findArticulationPoints(graph: Map<number, number[]>): number[] -> Option D

4. Quick Check:

   Adjacency list as Map with number arrays returns number array [OK]

Hint: Use Map for adjacency list in TypeScript [OK]

Common Mistakes:

• Using string type for graph input
• Returning void instead of list of articulation points
• Passing graph as a single number

3. Given the following TypeScript code snippet to find articulation points, what will be the output for the graph edges: [[0,1],[1,2],[2,0],[1,3]]?

const graph = new Map();
graph.set(0, [1, 2]);
graph.set(1, [0, 2, 3]);
graph.set(2, [0, 1]);
graph.set(3, [1]);

const articulationPoints = findArticulationPoints(graph);
console.log(articulationPoints);

medium

A. [0, 1]

B. [3]

C. [1]

D. []

Solution

1. Step 1: Analyze the graph structure

   The graph has a triangle between 0,1,2 and a leaf node 3 connected to 1.

2. Step 2: Identify articulation points

   Removing node 1 disconnects node 3 from the rest, so 1 is an articulation point. Nodes 0 and 2 are part of a cycle, so not articulation points. Node 3 is a leaf, not articulation point.

3. Final Answer:

   [1] -> Option C

4. Quick Check:

   Only node 1 disconnects graph when removed [OK]

Hint: Check if removing node splits graph into more parts [OK]

Common Mistakes:

• Thinking nodes in cycle are articulation points
• Including leaf nodes as articulation points
• Ignoring connectivity after removal

4. The following TypeScript code attempts to find articulation points but has a bug. What is the bug?

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

medium

A. The 'visited' array is not initialized before DFS

B. The root node condition for articulation point is checked after the loop

C. The variable 'time' is not incremented correctly

D. The condition 'low[v] >= disc[u]' should be 'low[v] > disc[u]'

Solution

1. Step 1: Review DFS variables initialization

   The code uses 'visited' array but does not show its initialization before DFS calls.

2. Step 2: Identify missing initialization impact

   If 'visited' is not initialized to false for all nodes, DFS may skip nodes or behave incorrectly.

3. Final Answer:

   The 'visited' array is not initialized before DFS -> Option A

4. Quick Check:

   Uninitialized visited array causes DFS errors [OK]

Hint: Always initialize visited array before DFS traversal [OK]

Common Mistakes:

• Assuming time increments incorrectly
• Misunderstanding root node articulation condition
• Changing condition from >= to > incorrectly

5. You have a network of computers represented as an undirected graph. You want to find all critical computers whose failure would split the network. The graph has 7 nodes with edges: [[0,1],[1,2],[2,0],[1,3],[3,4],[4,5],[5,3],[4,6]]. Which nodes are articulation points?

hard

A. [0, 2, 5]

B. [1, 3, 4]

C. [3, 5, 6]

D. [1, 4, 6]

Solution

1. Step 1: Analyze graph components and cycles

   Nodes 0,1,2 form a triangle (cycle). Nodes 3,4,5 form another cycle. Node 6 is connected only to 4.

2. Step 2: Identify articulation points

   Removing 1 disconnects node 3 and its cycle from 0,2. Removing 3 disconnects 4,5,6 from 1. Removing 4 disconnects node 6 from rest. So articulation points are 1, 3, and 4.

3. Final Answer:

   [1, 3, 4] -> Option B

4. Quick Check:

   Nodes connecting cycles and leaf nodes are articulation points [OK]

Hint: Look for nodes connecting cycles or leaf nodes [OK]

Common Mistakes:

• Including nodes inside cycles as articulation points
• Missing nodes connecting leaf nodes
• Confusing leaf nodes as articulation points