Articulation Points in Graph in DSA Go - Execution Trace

Concept Flow - Articulation Points in Graph

Start DFS at node 0

↓

Set discovery & low time

↓

For each neighbor

↓

If neighbor not visited

↓

Recurse DFS on neighbor

↓

Update low time of current

↓

Check articulation condition

↓

Mark articulation if condition met

↓

Repeat for all nodes

↓

Output all articulation points

We run DFS from each unvisited node, track discovery and low times, update low values, and mark nodes as articulation points if removing them increases graph components.

Execution Sample

DSA Go

func APUtil(u int, visited []bool, disc []int, low []int, parent []int, ap []bool) {
    visited[u] = true
    disc[u] = time
    low[u] = time
    time++
    children := 0
    for _, v := range graph[u] {
        if !visited[v] {
            children++
            parent[v] = u
            APUtil(v, visited, disc, low, parent, ap)
            low[u] = 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] = min(low[u], disc[v])
        }
    }
}

This code runs DFS to find articulation points by tracking discovery and low times, updating them, and marking nodes that separate graph components.

Execution Table

Step	Operation	Node Visited	Discovery Time (disc)	Low Time (low)	Parent	Children Count	Articulation Point Marked	Graph State (Visited Nodes)	Visual State (Articulation Points)
1	Start DFS at node 0	0	disc[0]=0	low[0]=0	parent[0]=-1	children=0	No	[0]	[]
2	Visit neighbor 1 of 0	1	disc[1]=1	low[1]=1	parent[1]=0	children=0	No	[0,1]	[]
3	Visit neighbor 2 of 1	2	disc[2]=2	low[2]=2	parent[2]=1	children=0	No	[0,1,2]	[]
4	Visit neighbor 3 of 2	3	disc[3]=3	low[3]=3	parent[3]=2	children=0	No	[0,1,2,3]	[]
5	Backtrack from 3 to 2	2	disc[2]=2	low[2]=min(2,3)=2	parent[2]=1	children=1	No	[0,1,2,3]	[]
6	Check articulation at 2	2	disc[2]=2	low[2]=2	parent[2]=1	children=1	No (low[3]>=disc[2] false)	[0,1,2,3]	[]
7	Backtrack from 2 to 1	1	disc[1]=1	low[1]=min(1,2)=1	parent[1]=0	children=1	No	[0,1,2,3]	[]
8	Visit neighbor 4 of 1	4	disc[4]=4	low[4]=4	parent[4]=1	children=0	No	[0,1,2,3,4]	[]
9	Backtrack from 4 to 1	1	disc[1]=1	low[1]=min(1,4)=1	parent[1]=0	children=2	Yes (root with >1 child)	[0,1,2,3,4]	[1]
10	Backtrack from 1 to 0	0	disc[0]=0	low[0]=min(0,1)=0	parent[0]=-1	children=1	No	[0,1,2,3,4]	[1]
11	Visit neighbor 5 of 0	5	disc[5]=5	low[5]=5	parent[5]=0	children=0	No	[0,1,2,3,4,5]	[1]
12	Visit neighbor 6 of 5	6	disc[6]=6	low[6]=6	parent[6]=5	children=0	No	[0,1,2,3,4,5,6]	[1]
13	Backtrack from 6 to 5	5	disc[5]=5	low[5]=min(5,6)=5	parent[5]=0	children=1	No	[0,1,2,3,4,5,6]	[1]
14	Backtrack from 5 to 0	0	disc[0]=0	low[0]=min(0,5)=0	parent[0]=-1	children=2	Yes (root with >1 child)	[0,1,2,3,4,5,6]	[1,0]
15	End DFS	-	-	-	-	-	-	[0,1,2,3,4,5,6]	[0,1]
16	Output articulation points	-	-	-	-	-	-	-	Nodes 0 and 1 are articulation points

💡 All nodes visited, DFS complete, articulation points identified

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 9	After Step 14	Final
visited	[false,false,false,false,false,false,false]	[true,true,false,false,false,false,false]	[true,true,true,true,false,false,false]	[true,true,true,true,true,false,false]	[true,true,true,true,true,true,true]	[true,true,true,true,true,true,true]
disc	[-1,-1,-1,-1,-1,-1,-1]	[0,1,-1,-1,-1,-1,-1]	[0,1,2,3,-1,-1,-1]	[0,1,2,3,4,-1,-1]	[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,2,3,-1,-1,-1]	[0,1,2,3,4,-1,-1]	[0,1,2,3,4,5,6]	[0,1,2,3,4,5,6]
parent	[-1,-1,-1,-1,-1,-1,-1]	[-1,0,-1,-1,-1,-1,-1]	[-1,0,1,2,-1,-1,-1]	[-1,0,1,2,1,-1,-1]	[-1,0,1,2,1,0,5]	[-1,0,1,2,1,0,5]
ap	[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,false]	[true,true,false,false,false,false,false]

Key Moments - 3 Insights

Why do we mark a root node as articulation point only if it has more than one child?

Because in the execution_table at step 9 and 14, the root node 0 is marked articulation only when children count > 1. This means removing root splits graph into multiple parts.

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

At step 6, we update low[u] = min(low[u], disc[v]) to capture back edges. This helps detect cycles and ensures correct articulation detection.

Why is a node marked articulation if low[v] >= disc[u] for non-root nodes?

At step 9, node 1 is marked articulation because low[4] >= disc[1]. This means subtree rooted at 4 cannot reach ancestors of 1, so removing 1 disconnects graph.

Visual Quiz - 3 Questions

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

A Node 0

B Node 2

C Node 1

D Node 4

💡 Hint

Check the 'Articulation Point Marked' and 'Visual State' columns at step 9

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

A Step 14

B Step 9

C Step 6

D Step 2

💡 Hint

Look for root node 0's articulation marking in 'Articulation Point Marked' column

If node 5 had no children, how would that affect the articulation points?

A Node 5 would become an articulation point

B Node 0 would not be an articulation point

C Node 1 would not be an articulation point

D No change in articulation points

💡 Hint

Refer to variable_tracker for 'children' count of root node 0 and its effect on articulation marking

Concept Snapshot

Articulation Points in Graph:
- Use DFS to assign discovery and low times
- low[u] = earliest visited vertex reachable from u
- Root node is articulation if it has >1 child
- Non-root node u is articulation if 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 connected components. We find them using DFS by tracking discovery times and low values. The low value of a node is the earliest discovery time reachable from it or its descendants. For the root node, if it has more than one child in DFS tree, it is an articulation point. For other nodes, if any child's low value is greater or equal to the node's discovery time, that node is an articulation point. The execution table shows step-by-step DFS traversal, updating discovery and low times, and marking articulation points accordingly.

Practice

1. What is an articulation point in a graph?

easy

A. A vertex with the highest degree in the graph

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

C. A vertex that has no edges connected to it

D. A vertex that forms a cycle with other vertices

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 B

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 a vertex with no edges
• Mixing articulation point with cycle vertices

2. Which Go code snippet correctly declares a graph as an adjacency list for articulation point detection?

easy

A. graph := make(map[int][]int)

B. graph := make(map[int]int)

C. graph := make([]int, n)

D. graph := make([][]int, n)

Solution

1. Step 1: Identify correct data structure for adjacency list

   An adjacency list maps each vertex to a list of connected vertices, so map[int][]int is correct.

2. Step 2: Check other options

   graph := make([][]int, n) is a slice of slices, which can work but usually fixed size; graph := make(map[int]int) is map[int]int (single int), not list; graph := make([]int, n) is slice of ints, not adjacency list.

3. Final Answer:

   graph := make(map[int][]int) -> Option A

4. Quick Check:

   Adjacency list = map vertex to list of neighbors [OK]

Hint: Adjacency list uses map[int][]int in Go [OK]

Common Mistakes:

• Using map[int]int instead of map[int][]int
• Using slice of ints instead of slice of slices or map
• Confusing slice initialization with map initialization

3. What is the output of the following Go code snippet that finds articulation points in a graph with edges: 0-1, 1-2, 1-3?

package main
import "fmt"
func main() {
    n := 4
    graph := make(map[int][]int)
    graph[0] = []int{1}
    graph[1] = []int{0, 2, 3}
    graph[2] = []int{1}
    graph[3] = []int{1}
    articulationPoints := []int{}
    // Assume articulation point detection returns [1]
    articulationPoints = append(articulationPoints, 1)
    fmt.Println(articulationPoints)
}

medium

A. []

B. [0, 1]

C. [1]

D. [2, 3]

Solution

1. Step 1: Analyze the graph structure

   Vertices 0,1,2,3 with edges 0-1, 1-2, 1-3 form a star with center 1.

2. Step 2: Identify articulation points

   Removing vertex 1 disconnects the graph, so 1 is an articulation point; others are not.

3. Final Answer:

   [1] -> Option C

4. Quick Check:

   Center vertex in star graph is articulation point [OK]

Hint: Center vertex connecting others is articulation point [OK]

Common Mistakes:

• Including leaf nodes as articulation points
• Forgetting that removing center disconnects graph
• Assuming multiple articulation points without checking connectivity

4. Find the bug in this Go code snippet for articulation point detection:

func dfs(u, parent int, graph map[int][]int, visited []bool, disc []int, low []int, time *int, ap []bool) {
    visited[u] = true
    disc[u] = *time
    low[u] = *time
    *time = *time + 1
    children := 0
    for _, v := range graph[u] {
        if !visited[v] {
            children++
            dfs(v, u, graph, visited, disc, low, time, ap)
            low[u] = min(low[u], low[v])
            if parent != -1 && low[v] >= disc[u] {
                ap[u] = true
            }
        } else if v != parent {
            low[u] = min(low[u], disc[v])
        }
    }
    if parent == -1 && children > 1 {
        ap[u] = true
    }
}

What is the error?

medium

A. Wrong comparison operator in if condition

B. Missing initialization of visited array

C. Incorrect base case for DFS

D. Incorrect increment syntax for time pointer (*time++)

Solution

1. Step 1: Check pointer increment syntax

   The line '*time++' is invalid in Go; pointer dereference and increment must be done as '*time = *time + 1'.

2. Step 2: Verify other parts

   Visited array initialization, if conditions, and DFS base case are correct.

3. Final Answer:

   Incorrect increment syntax for time pointer (*time++) -> Option D

4. Quick Check:

   Pointer increment in Go uses '*time = *time + 1' [OK]

Hint: Use '*time = *time + 1' to increment pointer value in Go [OK]

Common Mistakes:

• Using '*time++' which is invalid in Go
• Not initializing visited slice before DFS
• Confusing parent check condition
• Missing DFS base case for recursion

5. Given a connected graph with vertices 0 to 5 and edges: 0-1, 1-2, 2-0, 1-3, 3-4, 4-5, 5-3, which vertices are articulation points?

hard

A. [1,3]

B. [1,4]

C. [3]

D. [0,2,4]

Solution

1. Step 1: Analyze the graph structure

   Vertices 0,1,2 form a triangle (cycle), so none are articulation points there. Vertices 3,4,5 form another cycle. Vertex 1 connects these two parts.

2. Step 2: Identify articulation points

   Removing vertex 1 disconnects {0,2} from {3,4,5}. Removing vertex 3 disconnects {0,1,2} from {4,5}. Removing vertex 4 does not disconnect since 5 connects back to 3.

3. Final Answer:

   [1,3] -> Option A

4. Quick Check:

   Vertices connecting cycles or bridges are articulation points [OK]

Hint: Articulation points connect cycles or separate components [OK]

Common Mistakes:

• Including vertices inside cycles as articulation points
• Missing vertex 3 as articulation point
• Assuming all cycle vertices are articulation points