Articulation Points in Graph in DSA Java - Execution Trace

Concept Flow - Articulation Points in Graph

Start DFS from a node

↓

Mark node visited, set discovery & low time

↓

For each neighbor

↓

If not visited

↓

Recurse DFS on neighbor

↓

Update low[node

↓

Check articulation condition

↓

Mark node as articulation if condition met

↓

Return to parent

↓

Repeat for all nodes

↓

Collect all articulation points

↓

End

Start DFS from each node, track discovery and low times, update low values, and mark articulation points when conditions meet.

Execution Sample

DSA Java

void dfs(int u, int parent) {
  visited[u] = true;
  disc[u] = low[u] = time++;
  int children = 0;
  for (int v : adj[u]) {
    if (!visited[v]) {
      children++;
      dfs(v, u);
      low[u] = Math.min(low[u], low[v]);
      if (parent == -1 && children > 1) ap[u] = true;
      if (parent != -1 && low[v] >= disc[u]) ap[u] = true;
    } else if (v != parent) {
      low[u] = Math.min(low[u], disc[v]);
    }
  }
}

This DFS finds articulation points by tracking discovery and low times, updating low values, and checking conditions.

Execution Table

Step	Operation	Current Node (u)	Parent Node	Children Count	Visited Set	Discovery Times (disc)	Low Times (low)	Articulation Points Marked	Visual State
1	Start DFS at node 0	0	-1	0	[0]	disc[0]=0	low[0]=0	None	Graph: 0--1--2--3--4--5--6 Visited: 0 AP: None
2	Visit neighbor 1	1	0	0	[0,1]	disc[1]=1	low[1]=1	None	Visited: 0,1 AP: None
3	Visit neighbor 2	2	1	0	[0,1,2]	disc[2]=2	low[2]=2	None	Visited: 0,1,2 AP: None
4	Visit neighbor 3	3	2	0	[0,1,2,3]	disc[3]=3	low[3]=3	None	Visited: 0,1,2,3 AP: None
5	Visit neighbor 4	4	3	0	[0,1,2,3,4]	disc[4]=4	low[4]=4	None	Visited: 0,1,2,3,4 AP: None
6	Visit neighbor 5	5	4	0	[0,1,2,3,4,5]	disc[5]=5	low[5]=5	None	Visited: 0,1,2,3,4,5 AP: None
7	Visit neighbor 6	6	5	0	[0,1,2,3,4,5,6]	disc[6]=6	low[6]=6	None	Visited: 0,1,2,3,4,5,6 AP: None
8	Backtrack from 6 to 5	5	4	1	[0,1,2,3,4,5,6]	disc[5]=5	low[5]=5	ap[5]=true	low[5] updated to min(5,6)=5 low[6]>=disc[5] (6>=5) true, ap[5]=true Visited: all AP: 5
9	Backtrack from 5 to 4	4	3	1	[0,1,2,3,4,5,6]	disc[4]=4	low[4]=4	ap[4]=true	low[4] updated to min(4,5)=4 low[5]>=disc[4] (5>=4) true, ap[4]=true AP: 4,5
10	Backtrack from 4 to 3	3	2	1	[0,1,2,3,4,5,6]	disc[3]=3	low[3]=3	ap[3]=true	low[3] updated to min(3,4)=3 low[4]>=disc[3] (4>=3) true, ap[3]=true AP: 3,4,5
11	Backtrack from 3 to 2	2	1	1	[0,1,2,3,4,5,6]	disc[2]=2	low[2]=2	ap[2]=true	low[2] updated to min(2,3)=2 low[3]>=disc[2] (3>=2) true, ap[2]=true AP: 2,3,4,5
12	Backtrack from 2 to 1	1	0	1	[0,1,2,3,4,5,6]	disc[1]=1	low[1]=1	ap[1]=true	low[1] updated to min(1,2)=1 low[2]>=disc[1] (2>=1) true, ap[1]=true AP: 1,2,3,4,5
13	Check articulation at node 1	1	0	1	[0,1,2,3,4,5,6]	disc[1]=1	low[1]=1	ap[1]=true	Condition low[2]>=disc[1] (2>=1) true, parent != -1 AP: 1,2,3,4,5
14	Backtrack from 1 to 0	0	-1	1	[0,1,2,3,4,5,6]	disc[0]=0	low[0]=0	None	low[0] updated to min(0,1)=0 AP: 1,2,3,4,5
15	Check articulation at node 0	0	-1	1	[0,1,2,3,4,5,6]	disc[0]=0	low[0]=0	No	Root with 1 child is not AP AP: 1,2,3,4,5
16	DFS complete	-	-	-	[0,1,2,3,4,5,6]	disc=[0,1,2,3,4,5,6]	low=[0,1,2,3,4,5,6]	AP: 1,2,3,4,5	All nodes visited, articulation points found: 1,2,3,4,5

💡 DFS finished for all nodes, articulation points identified where conditions met

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10	After Step 11	After Step 12	After Step 13	After Step 14	Final
visited	[]	[0]	[0,1]	[0,1,2]	[0,1,2,3]	[0,1,2,3,4]	[0,1,2,3,4,5]	[0,1,2,3,4,5,6]	[0,1,2,3,4,5,6]	[0,1,2,3,4,5,6]	[0,1,2,3,4,5,6]	[0,1,2,3,4,5,6]	[0,1,2,3,4,5,6]	[0,1,2,3,4,5,6]	[0,1,2,3,4,5,6]	[0,1,2,3,4,5,6]
disc	[-1,-1,-1,-1,-1,-1,-1]	[0,-1,-1,-1,-1,-1,-1]	[0,1,-1,-1,-1,-1,-1]	[0,1,2,-1,-1,-1,-1]	[0,1,2,3,-1,-1,-1]	[0,1,2,3,4,-1,-1]	[0,1,2,3,4,5,-1]	[0,1,2,3,4,5,6]	[0,1,2,3,4,5,6]	[0,1,2,3,4,5,6]	[0,1,2,3,4,5,6]	[0,1,2,3,4,5,6]	[0,1,2,3,4,5,6]	[0,1,2,3,4,5,6]	[0,1,2,3,4,5,6]	[0,1,2,3,4,5,6]
low	[-1,-1,-1,-1,-1,-1,-1]	[0,-1,-1,-1,-1,-1,-1]	[0,1,-1,-1,-1,-1,-1]	[0,1,2,-1,-1,-1,-1]	[0,1,2,3,-1,-1,-1]	[0,1,2,3,4,-1,-1]	[0,1,2,3,4,5,-1]	[0,1,2,3,4,5,6]	[0,1,2,3,4,5,6]	[0,1,2,3,4,5,6]	[0,1,2,3,4,5,6]	[0,1,2,3,4,5,6]	[0,1,2,3,4,5,6]	[0,1,2,3,4,5,6]	[0,1,2,3,4,5,6]	[0,1,2,3,4,5,6]
children	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
ap	[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,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,false]	[false,false,false,false,true,true,false]	[false,false,false,true,true,true,false]	[false,false,true,true,true,true,false]	[false,true,true,true,true,true,false]	[false,true,true,true,true,true,false]	[false,true,true,true,true,true,false]	[false,true,true,true,true,true,false]

Key Moments - 3 Insights

Why do we update low[u] with low[v] after DFS call on neighbor v?

Because low[v] represents the earliest visited node reachable from v or its descendants. Updating low[u] with low[v] helps u know if there's a back edge from v's subtree to u or above, which is key to finding articulation points. See execution_table rows 8-12 where low values are updated.

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 in DFS tree, removing it disconnects the graph. If it has only one child, removing it doesn't disconnect. This is checked in execution_table row 15.

Why do we ignore the edge to parent when updating low[u] with disc[v]?

Because the edge to parent is the one we came from, not a back edge. We only update low[u] with disc[v] for back edges to ancestors other than parent. This prevents incorrect low values. See execution_table row 7 where this condition is applied.

Visual Quiz - 3 Questions

Look at the execution_table at step 8, what is the low time of node 5 after backtracking from node 6?

A 4

B 6

C 5

D 3

💡 Hint

Check the 'Low Times (low)' column at step 8 in execution_table.

At which step does the algorithm check if the root node is an articulation point?

A Step 15

B Step 13

C Step 10

D Step 7

💡 Hint

Look for the step mentioning 'Check articulation at node 0' in execution_table.

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

A Node 1 would be marked as articulation point

B Node 0 would be marked as articulation point

C No change in articulation points

D Node 6 would be marked as articulation point

💡 Hint

Refer to the condition for articulation points in the code and the 'children' count in variable_tracker.

Concept Snapshot

Articulation Points in Graph (Cut Vertices):
- Use DFS to assign discovery and low times to nodes.
- low[u] = earliest visited node reachable from u or its descendants.
- A node u is articulation if:
  * u is root and has >1 child
  * u is not root and low[v] >= disc[u] for any child v
- Update low[u] after DFS on neighbors.
- Mark articulation points during DFS traversal.

Full Transcript

Articulation points are nodes in a graph which, if removed, increase the number of connected components. We find them using DFS by tracking discovery times and low values. The low value of a node is the earliest visited node reachable from it or its descendants. During DFS, we update low values and check conditions: if the node is root with more than one child, or if a child's low value is greater or equal to the node's discovery time, then the node is an articulation point. We ignore the parent edge when updating low values to avoid false positives. This process is repeated for all nodes to find all articulation points.

Practice

1. What is an articulation point in a graph?

easy

A. A vertex that forms a cycle in the graph

B. A vertex with the highest degree in the graph

C. A vertex connected to all other vertices

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

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 which, when removed, increases the number of connected components matches this definition exactly.

3. Final Answer:

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

4. Quick Check:

   Articulation point = vertex breaking connectivity [OK]

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

Common Mistakes:

• Confusing articulation point with highest degree vertex
• Thinking articulation point forms cycles
• Assuming articulation point connects to all vertices

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

easy

A. int graph[][] = new int[];

B. HashMap graph = new HashMap<>();

C. ArrayList graph = new ArrayList<>();

D. List<Integer> graph = new List<>();

Solution

1. Step 1: Understand adjacency list structure

   An adjacency list for a graph is usually a list of lists, where each inner list holds neighbors of a vertex.

2. Step 2: Check Java syntax for adjacency list

   ArrayList graph = new ArrayList<>(); correctly declares an ArrayList of ArrayLists of Integers, suitable for adjacency list.

3. Final Answer:

   ArrayList graph = new ArrayList<>(); -> Option C

4. Quick Check:

   Adjacency list = list of lists [OK]

Hint: Adjacency list uses list of lists in Java [OK]

Common Mistakes:

• Using 2D array without size initialization
• Using HashMap with wrong value type
• Trying to instantiate interface List directly

3. Consider the following Java code snippet for articulation point detection. What will be the output when the graph has edges: 0-1, 1-2, 1-3?

int V = 4;
ArrayList graph = new ArrayList<>();
for (int i = 0; i < V; i++) graph.add(new ArrayList<>());
graph.get(0).add(1);
graph.get(1).add(0);
graph.get(1).add(2);
graph.get(2).add(1);
graph.get(1).add(3);
graph.get(3).add(1);
// Articulation points found: 1

medium

A. []

B. [1]

C. [2, 3]

D. [0, 1]

Solution

1. Step 1: Analyze the graph structure

   The graph has vertices 0,1,2,3 with edges 0-1, 1-2, 1-3. Vertex 1 connects to all others.

2. Step 2: Identify articulation points

   Removing vertex 1 disconnects the graph into three parts, so 1 is an articulation point. Others are not.

3. Final Answer:

   [1] -> Option B

4. Quick Check:

   Only vertex 1 breaks connectivity [OK]

Hint: Check which vertex removal splits graph [OK]

Common Mistakes:

• Assuming leaf nodes are articulation points
• Including vertices with degree 1 as articulation points
• Ignoring connectivity after removal

4. The following Java code snippet is intended to find articulation points but has a bug. What is the error?

void dfs(int u, int parent) {
  visited[u] = true;
  disc[u] = low[u] = time++;
  int children = 0;
  for (int v : 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])
        articulation[u] = true;
    } else if (v != parent) {
      low[u] = Math.min(low[u], disc[v]);
    }
  }
  if (parent == -1 && children > 1)
    articulation[u] = true;
}

medium

A. The time variable is not initialized before DFS

B. The condition for root articulation point is incorrect

C. The low array is not updated correctly for back edges

D. The visited array is not marked true for vertex u

Solution

1. Step 1: Check initialization of time variable

   The variable 'time' is used to assign discovery times but must be initialized before DFS starts.

2. Step 2: Verify other parts of DFS

   Conditions for root and back edges are correct; visited[u] is marked true properly.

3. Final Answer:

   The time variable is not initialized before DFS -> Option A

4. Quick Check:

   Uninitialized time causes wrong discovery times [OK]

Hint: Initialize time counter before DFS call [OK]

Common Mistakes:

• Forgetting to initialize time before DFS
• Misusing parent check for root node
• Not updating low values for back edges

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, 3]

B. [0, 2]

C. [3]

D. [1]

Solution

1. Step 1: Analyze the graph structure

   Vertices 0,1,2 form a triangle (cycle). Edges 1-3 and 3-4 form a chain attached to vertex 1.

2. Step 2: Identify articulation points

   Removing vertex 1 disconnects 3 and 4 from the cycle, so 1 is an articulation point. Removing 3 disconnects 4, so 3 is also an articulation point. Vertices 0 and 2 are in a cycle, so not articulation points.

3. Final Answer:

   [1, 3] -> Option A

4. Quick Check:

   Vertices breaking connectivity: 1 and 3 [OK]

Hint: Check vertices whose removal splits graph into parts [OK]

Common Mistakes:

• Assuming cycle vertices are articulation points
• Missing vertex 3 as articulation point
• Only considering vertex 1 as articulation point