Articulation Points in Graph in DSA Python

Mental Model

An articulation point is a node in a graph that, if removed, breaks the graph into more pieces. It shows where the graph is fragile.

Analogy: Imagine a city connected by roads. Some intersections are so important that if they close, parts of the city become unreachable. Those intersections are like articulation points.

Graph:
  1
 / \
2 - 3 - 4
     |
     5

Articulation points: 3 (removing 3 splits the graph)

Dry Run Walkthrough

Input: Graph with edges: 1-2, 1-3, 2-3, 3-4, 3-5

Goal: Find all articulation points in the graph

Step 1: Start DFS from node 1, set discovery time and low value

Visited: 1 (disc=1, low=1)
Stack: [1]

Why: We begin exploring from node 1 to find articulation points

Step 2: Visit node 2 from 1, set discovery and low values

Visited: 1 (disc=1, low=1), 2 (disc=2, low=2)
Stack: [1,2]

Why: Explore neighbors to find back edges and update low values

Step 3: Visit node 3 from 2, set discovery and low values

Visited: 1 (disc=1, low=1), 2 (disc=2, low=2), 3 (disc=3, low=3)
Stack: [1,2,3]

Why: Continue DFS to deeper nodes to detect articulation points

Step 4: Visit node 4 from 3, set discovery and low values

Visited: 1 (disc=1, low=1), 2 (disc=2, low=2), 3 (disc=3, low=3), 4 (disc=4, low=4)
Stack: [1,2,3,4]

Why: Leaf node reached, backtrack to update low values

Step 5: Backtrack from 4 to 3, update low[3] = min(low[3], low[4]) = 3

low[3] = 3
Articulation check: 3 is articulation point because low[4] >= disc[3]

Why: Node 3 separates node 4 from the rest, so 3 is articulation point

Step 6: Visit node 5 from 3, set discovery and low values

Visited: 1,2,3,4,5 (disc=5, low=5)
Stack: [1,2,3,5]

Why: Explore another branch from 3

Step 7: Backtrack from 5 to 3, update low[3] = min(low[3], low[5]) = 3

low[3] = 3
Articulation check: 3 is articulation point because low[5] >= disc[3]

Why: Node 3 separates node 5 from the rest, confirming articulation

Step 8: Backtrack from 3 to 1, update low[1] = min(low[1], low[3]) = 1

low[1] = 1
Articulation check: 1 is not articulation point because it is root with only one child

Why: Root node with one child is not articulation point

Result:

Articulation points: 3
Graph remains connected except if node 3 is removed

Annotated Code

DSA Python

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = defaultdict(list)
        self.time = 0

    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

    def _AP_util(self, u, visited, ap, parent, low, disc):
        children = 0
        visited[u] = True
        self.time += 1
        disc[u] = self.time
        low[u] = self.time

        for v in self.graph[u]:
            if not visited[v]:
                parent[v] = u
                children += 1
                self._AP_util(v, visited, ap, parent, low, disc)

                low[u] = min(low[u], low[v])  # update low value

                if parent[u] is None and children > 1:
                    ap[u] = True  # root with two or more children

                if parent[u] is not None and low[v] >= disc[u]:
                    ap[u] = True  # articulation point

            elif v != parent[u]:
                low[u] = min(low[u], disc[v])  # back edge

    def find_articulation_points(self):
        visited = [False] * self.V
        disc = [float('inf')] * self.V
        low = [float('inf')] * self.V
        parent = [None] * self.V
        ap = [False] * self.V

        for i in range(self.V):
            if not visited[i]:
                self._AP_util(i, visited, ap, parent, low, disc)

        return [index for index, value in enumerate(ap) if value]

# Driver code
if __name__ == '__main__':
    g = Graph(6)  # nodes 0 to 5
    g.add_edge(1, 2)
    g.add_edge(1, 3)
    g.add_edge(2, 3)
    g.add_edge(3, 4)
    g.add_edge(3, 5)

    aps = g.find_articulation_points()
    print('Articulation points:', aps)

visited[u] = True self.time += 1 disc[u] = self.time low[u] = self.time

Mark node u visited and set discovery and low times

for v in self.graph[u]:

Traverse all neighbors of u

if not visited[v]: parent[v] = u children += 1 self._AP_util(v, visited, ap, parent, low, disc)

Visit unvisited neighbor v recursively, track parent and children count

low[u] = min(low[u], low[v])

Update low[u] based on child's low value

if parent[u] is None and children > 1: ap[u] = True

Root node with multiple children is articulation point

if parent[u] is not None and low[v] >= disc[u]: ap[u] = True

Non-root node u is articulation point if child's low >= u's discovery

elif v != parent[u]: low[u] = min(low[u], disc[v])

Update low[u] for back edge to ancestor

Output

Articulation points: [3]

Complexity Analysis

Time: O(V + E) because we visit each vertex and edge once during DFS

Space: O(V) for arrays storing visited, discovery, low, parent, and articulation points

vs Alternative: Naive approach checks connectivity after removing each node, costing O(V*(V+E)), much slower than DFS-based O(V+E)

Edge Cases

Graph with no edges

No articulation points because no connections to break

DSA Python

if not visited[i]:

Graph with single node

No articulation points because removing the only node leaves empty graph

DSA Python

if not visited[i]:

Graph with multiple disconnected components

Algorithm finds articulation points in each component separately

DSA Python

for i in range(self.V):
    if not visited[i]:

When to Use This Pattern

When asked to find nodes whose removal disconnects a graph, use articulation points detection with DFS and low-link values.

Common Mistakes

Mistake: Not updating low[u] for back edges to ancestors
Fix: Add condition to update low[u] = min(low[u], disc[v]) when v is visited and not parent

Mistake: Marking root as articulation point without checking children count
Fix: Only mark root as articulation point if it has two or more children

Summary

Find nodes that disconnect the graph if removed.

Use when you want to identify fragile points in networks or graphs.

Use DFS with discovery and low times to detect articulation points efficiently.

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