Articulation Points in Graph in DSA Python - Execution Trace

Concept Flow - Articulation Points in Graph

Start DFS from a node

↓

Mark node visited, set discovery & low time

↓

For each neighbor

↓

If neighbor not visited

↓

Recurse DFS

↓

Check articulation condition

↓

Mark articulation point if condition true

↓

Repeat for all nodes

↓

Output all articulation points

The algorithm uses DFS to find nodes which, if removed, increase graph components by tracking discovery and low times.

Execution Sample

DSA Python

def APUtil(u, visited, ap, parent, low, disc, time, graph):
    visited[u] = True
    disc[u] = time
    low[u] = time
    time += 1
    children = 0
    for v in graph[u]:
        if not visited[v]:
            parent[v] = u
            children += 1
            APUtil(v, visited, ap, parent, low, disc, time, graph)
            low[u] = min(low[u], low[v])
            if parent[u] is None and children > 1:
                ap[u] = True
            if parent[u] is not None and low[v] >= disc[u]:
                ap[u] = True
        elif v != parent[u]:
            low[u] = min(low[u], disc[v])

This code snippet starts DFS from node u, marks it visited, sets discovery and low times, and explores neighbors recursively.

Execution Table

Step	Operation	Node Visited	Discovery Time	Low Time	Parent	Children Count	Articulation Point Marked	Graph State
1	Start DFS at node 0	0	0	0	None	0	No	Visited: {0}, AP: {}
2	Visit neighbor 1	1	1	1	0	0	No	Visited: {0,1}, AP: {}
3	Visit neighbor 2	2	2	2	1	0	No	Visited: {0,1,2}, AP: {}
4	Backtrack to 1, update low[1]	1	1	1	0	1	No	Visited: {0,1,2}, AP: {}
5	Visit neighbor 3	3	3	3	1	0	No	Visited: {0,1,2,3}, AP: {}
6	Visit neighbor 4	4	4	4	3	0	No	Visited: {0,1,2,3,4}, AP: {}
7	Backtrack to 3, update low[3]	3	3	3	1	1	No	Visited: {0,1,2,3,4}, AP: {}
8	Backtrack to 1, update low[1]	1	1	1	0	2	Yes	Visited: {0,1,2,3,4}, AP: {1}
9	Backtrack to 0, update low[0]	0	0	0	None	1	No	Visited: {0,1,2,3,4}, AP: {1}
10	Visit neighbor 5	5	5	5	0	0	No	Visited: {0,1,2,3,4,5}, AP: {1}
11	Visit neighbor 6	6	6	6	5	0	No	Visited: {0,1,2,3,4,5,6}, AP: {1}
12	Backtrack to 5, update low[5]	5	5	5	0	1	No	Visited: {0,1,2,3,4,5,6}, AP: {1}
13	Backtrack to 0, update low[0]	0	0	0	None	2	Yes	Visited: {0,1,2,3,4,5,6}, AP: {0,1}
14	DFS complete	-	-	-	-	-	-	Final AP set: {0,1}

💡 All nodes visited, DFS complete, articulation points identified.

Variable Tracker

Variable	Start	After Step 1	After Step 5	After Step 8	After Step 13	Final
visited	{}	{0}	{0,1,2,3}	{0,1,2,3,4}	{0,1,2,3,4,5,6}	{0,1,2,3,4,5,6}
disc	{}	{0:0}	{0:0,1:1,2:2,3:3}	{0:0,1:1,2:2,3:3,4:4}	{0:0,1:1,2:2,3:3,4:4,5:5,6:6}	{0:0,1:1,2:2,3:3,4:4,5:5,6:6}
low	{}	{0:0}	{0:0,1:1,2:2,3:3}	{0:0,1:1,2:2,3:3,4:4}	{0:0,1:1,2:2,3:3,4:4,5:5,6:6}	{0:0,1:1,2:2,3:3,4:4,5:5,6:6}
parent	{}	{0:None}	{0:None,1:0,2:1,3:1}	{0:None,1:0,2:1,3:1,4:3}	{0:None,1:0,2:1,3:1,4:3,5:0,6:5}	{0:None,1:0,2:1,3:1,4:3,5:0,6:5}
children	0	1	2	2	2	2
ap	{}	{}	{}	{1}	{0,1}	{0,1}

Key Moments - 3 Insights

Why do we update the low time of a node after visiting its child?

Because the low time represents the earliest visited node reachable, updating it after child DFS helps detect back edges and articulation points, as shown in steps 4, 7, and 8.

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

Because removing the root disconnects the graph only if it has multiple DFS tree children, as seen in step 13 where root node 0 has 2 children and is marked AP.

Why do we keep track of the parent of each node?

To avoid considering the edge back to parent as a back edge and correctly update low times, as shown in the parent array updates in variable_tracker.

Visual Quiz - 3 Questions

Look at the execution_table at step 8, which node is marked as an articulation point?

A Node 1

B Node 0

C Node 3

D Node 5

💡 Hint

Check the 'Articulation Point Marked' and 'Node Visited' columns at step 8.

At which step does the root node 0 get marked as an articulation point?

A Step 10

B Step 13

C Step 5

D Step 2

💡 Hint

Look for when 'Articulation Point Marked' is 'Yes' for node 0 in the execution_table.

If node 1 had only one child, how would the articulation points change?

A Node 1 would not be an articulation point

B Node 0 would not be an articulation point

C Node 3 would become an articulation point

D No change in articulation points

💡 Hint

Refer to the key moment about root and child count affecting articulation points.

Concept Snapshot

Articulation Points in Graph:
- Use DFS to assign discovery and low times.
- Low time tracks earliest reachable ancestor.
- A node u is articulation if:
  * u is root with >1 child
  * u is not root and low[v]>=disc[u] for child v
- Helps find critical nodes disconnecting graph.

Full Transcript

This visualization shows how articulation points in a graph are found using DFS. We start DFS from a node, mark it visited, and assign discovery and low times. For each neighbor, if not visited, we recurse DFS and update low times after backtracking. We track children count and parent nodes. A node is marked articulation if it is root with more than one child or if a child's low time is not less than the node's discovery time. The execution table traces each step, showing visited nodes, discovery and low times, parents, children count, and articulation points found. Variable tracker shows how these values change. Key moments clarify why low times update, root node conditions, and parent tracking. The quiz tests understanding of when nodes become articulation points and effects of child count changes. This method identifies nodes whose removal increases graph components, critical for network reliability and connectivity analysis.

Practice

1. What is an articulation point in a graph?

easy

A. A vertex connected to all other vertices

B. A vertex with the highest degree in the graph

C. A vertex that, when removed, increases the number of connected components

D. A vertex that forms a cycle with its neighbors

Solution

1. Step 1: Understand the definition of articulation point

   An articulation point is a vertex in a graph whose removal disconnects the graph or increases the number of connected components.

2. Step 2: Compare options with definition

   A vertex that, when removed, increases the number of connected components matches this definition exactly. Other options describe different concepts.

3. Final Answer:

   A vertex that, when removed, increases the number of connected components -> Option C

4. Quick Check:

   Articulation point = vertex disconnecting graph [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 initialize the discovery time array for articulation point detection in Python?

easy

A. discovery = list(range(n))

B. discovery = [-1] * n

C. discovery = [0] * n

D. discovery = None

Solution

1. Step 1: Understand initialization purpose

   The discovery time array stores the time when each vertex is first visited. Initializing with -1 means unvisited.

2. Step 2: Check options

   discovery = [-1] * n initializes all values to -1, indicating unvisited vertices. discovery = [0] * n sets all to 0, which can be confused with a valid time. discovery = list(range(n)) assigns increasing numbers, which is incorrect. discovery = None sets None, which is invalid for indexing.

3. Final Answer:

   discovery = [-1] * n -> Option B

4. Quick Check:

   Unvisited vertices marked as -1 [OK]

Hint: Use -1 to mark unvisited nodes in discovery array [OK]

Common Mistakes:

• Initializing discovery with zeros causing confusion
• Using range which sets wrong discovery times
• Setting discovery to None causing errors

3. What will be the output articulation points for the following graph represented as adjacency list?

graph = {0: [1, 2], 1: [0, 2], 2: [0, 1, 3], 3: [2, 4, 5], 4: [3, 5], 5: [3, 4]}

medium

A. [2, 3]

B. [0, 3]

C. [1, 4]

D. [3]

Solution

1. Step 1: Analyze graph structure

   Vertices 0,1,2 form a triangle (cycle). Vertex 3 connects this triangle to vertices 4 and 5, which form another cycle.

2. Step 2: Identify articulation points

   Removing vertex 2 disconnects vertex 3 and its connected cycle from the triangle. Removing vertex 3 disconnects vertices 4 and 5 from the rest. So articulation points are 2 and 3.

3. Final Answer:

   [2, 3] -> Option A

4. Quick Check:

   Vertices breaking connectivity = 2, 3 [OK]

Hint: Check vertices connecting two or more components [OK]

Common Mistakes:

• Ignoring articulation point at vertex 2
• Missing vertex 3 as articulation point
• Confusing cycle vertices as articulation points

4. Identify the bug in this articulation point detection code snippet:

def dfs(u, parent):
    visited[u] = True
    discovery[u] = time
    low[u] = time
    time += 1
    children = 0
    for v in graph[u]:
        if not visited[v]:
            children += 1
            dfs(v, u)
            low[u] = min(low[u], low[v])
            if parent != -1 and low[v] >= discovery[u]:
                articulation[u] = True
        elif v != parent:
            low[u] = min(low[u], discovery[v])
    if parent == -1 and children > 1:
        articulation[u] = True

medium

A. Variable 'time' is not declared global or passed, causing incorrect increments

B. The condition 'low[v] >= discovery[u]' should be '>' instead of '>='

C. The 'children' count is not incremented correctly

D. The check 'elif v != parent' should be 'if v == parent'

Solution

1. Step 1: Check variable usage in recursion

   The variable 'time' is incremented inside dfs but not declared global or passed as argument, so increments won't persist across calls.

2. Step 2: Verify other conditions

   Conditions and increments for 'children' and articulation logic are correct. The 'elif' condition is also correct to update low values.

3. Final Answer:

   Variable 'time' is not declared global or passed, causing incorrect increments -> Option A

4. Quick Check:

   Global time needed for correct discovery times [OK]

Hint: Declare 'time' global or pass it to update correctly [OK]

Common Mistakes:

• Not declaring 'time' global causing discovery errors
• Changing condition '>=' to '>' incorrectly
• Miscounting children in DFS
• Incorrectly checking parent in else condition

5. Given a connected undirected graph with 7 vertices and edges:

edges = [(0,1),(1,2),(2,0),(1,3),(3,4),(4,5),(5,3),(5,6)]

Which vertices are articulation points?

hard

A. [0, 3, 6]

B. [2, 4, 5]

C. [1, 4, 6]

D. [1, 3, 5]

Solution

1. Step 1: Analyze graph structure

   Vertices 0,1,2 form a triangle (cycle). Vertex 1 connects to vertex 3, which connects to a cycle 3-4-5 and vertex 5 connects to 6.

2. Step 2: Identify articulation points

   Removing vertex 1 disconnects 3 and beyond from 0 and 2. Removing vertex 3 disconnects 4 and 5 from 1. Removing vertex 5 disconnects 6 from the rest. So articulation points are 1, 3, and 5.

3. Final Answer:

   [1, 3, 5] -> Option D

4. Quick Check:

   Vertices disconnecting parts = 1, 3, 5 [OK]

Hint: Find vertices connecting cycles or leaf nodes [OK]

Common Mistakes:

• Missing vertex 1 as articulation point
• Including leaf vertex 6 incorrectly
• Ignoring vertex 5's role in connectivity