Articulation Points in Graph in DSA Javascript - Execution Trace

Concept Flow - Articulation Points in Graph

Start DFS at a node

↓

Mark node visited, set discovery & low time

↓

For each neighbor

↓

If not visited

→DFS on neighbor

↓

Update low time of current node

↓

Check articulation condition

↓

Mark articulation point if condition met

↓

If visited and not parent

→Update low time

↓

Repeat for all nodes

↓

Collect all articulation points

↓

End

The algorithm uses DFS to visit nodes, tracks discovery and low times, and identifies articulation points by checking if removing a node increases disconnected components.

Execution Sample

DSA Javascript

function APUtil(u, visited, disc, low, parent, ap, time, graph) {
  visited[u] = true;
  disc[u] = low[u] = ++time.count;
  let children = 0;
  for (let v of graph[u]) {
    if (!visited[v]) {
      children++;
      parent[v] = u;
      APUtil(v, visited, disc, low, parent, ap, time, graph);
      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]);
    }
  }
}

This code runs DFS on graph nodes, updates discovery and low times, and marks articulation points based on conditions.

Execution Table

Step	Operation	Node Visited	Discovery Time (disc)	Low Time (low)	Parent	Children Count	Articulation Point Marked	Graph State
1	Start DFS at node 0	0	disc[0]=1	low[0]=1	parent[0]=-1	children=0	No	Visited: {0}
2	Visit neighbor 1 of 0	1	disc[1]=2	low[1]=2	parent[1]=0	children=0	No	Visited: {0,1}
3	Visit neighbor 2 of 1	2	disc[2]=3	low[2]=3	parent[2]=1	children=0	No	Visited: {0,1,2}
4	Visit neighbor 3 of 2	3	disc[3]=4	low[3]=4	parent[3]=2	children=0	No	Visited: {0,1,2,3}
5	Backtrack to 2, update low[2]	2	disc[2]=3	low[2]=3	parent[2]=1	children=1	No	Visited: {0,1,2,3}
6	Check articulation for 2	2	disc[2]=3	low[2]=3	parent[2]=1	children=1	Yes (low[3]>=disc[2])	AP: {2}
7	Backtrack to 1, update low[1]	1	disc[1]=2	low[1]=2	parent[1]=0	children=1	No	AP: {2}
8	Visit neighbor 4 of 1	4	disc[4]=5	low[4]=5	parent[4]=1	children=0	No	Visited: {0,1,2,3,4}
9	Backtrack to 1, update low[1]	1	disc[1]=2	low[1]=2	parent[1]=0	children=2	No	AP: {2}
10	Check articulation for 1	1	disc[1]=2	low[1]=2	parent[1]=0	children=2	Yes (root with >1 child)	AP: {1,2}
11	Backtrack to 0, update low[0]	0	disc[0]=1	low[0]=1	parent[0]=-1	children=1	No	AP: {1,2}
12	DFS complete	-	-	-	-	-	-	Final AP: {1,2}

💡 DFS finished for all nodes; articulation points identified where removal increases disconnected components.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 6	After Step 10	Final
visited	{}	{0:true}	{0:true,1:true,2:true}	{0:true,1:true,2:true,3:true,4:true}	{0:true,1:true,2:true,3:true,4:true}	{0:true,1:true,2:true,3:true,4:true}
disc	{}	{0:1}	{0:1,1:2,2:3}	{0:1,1:2,2:3,3:4,4:5}	{0:1,1:2,2:3,3:4,4:5}	{0:1,1:2,2:3,3:4,4:5}
low	{}	{0:1}	{0:1,1:2,2:3}	{0:1,1:2,2:3,3:4,4:5}	{0:1,1:2,2:3,3:4,4:5}	{0:1,1:2,2:3,3:4,4:5}
parent	{}	{0:-1}	{0:-1,1:0,2:1}	{0:-1,1:0,2:1,3:2,4:1}	{0:-1,1:0,2:1,3:2,4:1}	{0:-1,1:0,2:1,3:2,4:1}
ap	{}	{0:false}	{0:false,1:false,2:false}	{0:false,1:false,2:true}	{0:false,1:true,2:true}	{0:false,1:true,2:true}
children	0	1	1	1	2	2

Key Moments - 3 Insights

Why do we mark a node as articulation point only if low[v] >= disc[u] for a child v?

Because it means the child v or its descendants cannot reach an ancestor of u, so removing u disconnects the graph. See execution_table step 6 where low[3]=4 >= disc[2]=3 triggers marking node 2.

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

Root has no parent, so it is articulation point only if removing it disconnects multiple subtrees. In step 10, node 1 is root with 2 children, so it is marked.

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

This updates low[u] to the earliest discovered ancestor reachable via back edge, ensuring correct low time. See step 5 where low[2] updates after backtracking.

Visual Quiz - 3 Questions

Look at the execution_table, what is the discovery time of node 3 at step 4?

A 3

B 4

C 2

D 1

💡 Hint

Check the 'Discovery Time (disc)' column at step 4 in execution_table.

At which step does node 2 get marked as an articulation point?

A Step 5

B Step 7

C Step 6

D Step 10

💡 Hint

Look for 'Articulation Point Marked' column in execution_table where node 2 is marked.

If node 1 had only one child, would it be marked as an articulation point at step 10?

A No, because root with one child is not articulation point

B Yes, because it is visited first

C Yes, because low[v] >= disc[u]

D No, because it has no parent

💡 Hint

Refer to key_moments about root node articulation condition and execution_table step 10.

Concept Snapshot

Articulation Points in Graph:
- Use DFS to assign discovery and low times
- low[u] = earliest visited vertex reachable from u
- Node u is articulation point if:
  * u is root and has >1 child
  * u is not root and low[v] >= disc[u] for any child v
- Helps find nodes whose removal disconnects graph

Full Transcript

Articulation points are nodes in a graph that, if removed, increase the number of disconnected parts. We find them using a depth-first search (DFS). Each node gets a discovery time when first visited and a low time which is the earliest visited node reachable from it or its descendants. We track parents and children in DFS tree. If a node is root and has more than one child, it is an articulation point. If a node is not root and any child's low time is greater or equal to the node's discovery time, it is an articulation point. The execution table shows step-by-step how nodes are visited, times assigned, and articulation points marked. The variable tracker shows how arrays like visited, disc, low, parent, and ap change over time. Key moments clarify why certain conditions mark articulation points and how low times update. The visual quiz tests understanding of discovery times, marking steps, and root node conditions.

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