Articulation Points in Graph in DSA Python - Build from Scratch

Articulation Points in Graph

📖 Scenario: Imagine a city's road network represented as a graph. Each intersection is a node, and roads are edges connecting them. Some intersections are critical: if they close, parts of the city become unreachable. These are called articulation points.

🎯 Goal: You will build a program to find all articulation points in a given undirected graph. This helps city planners identify critical intersections to keep open for smooth traffic.

📋 What You'll Learn

Create a graph using an adjacency list representation with exact nodes and edges

Set up necessary helper variables for tracking discovery times and low values

Implement a Depth-First Search (DFS) based function to find articulation points

Print the list of articulation points in sorted order

💡 Why This Matters

🌍 Real World

City planners use articulation points to identify critical intersections that, if blocked, can cause traffic jams or isolate neighborhoods.

💼 Career

Understanding articulation points is important for network reliability analysis, infrastructure planning, and cybersecurity roles involving network vulnerability assessments.

1

Create the graph as an adjacency list

Create a dictionary called graph representing an undirected graph with these exact edges: 0-1, 1-2, 2-0, 1-3, 3-4. Use adjacency lists where each key is a node and the value is a list of connected nodes.

DSA Python

# Your code here

Hint

Use a dictionary where keys are node numbers and values are lists of connected nodes.

2

Set up helper variables for DFS

Create three variables: time set to 0, disc as a dictionary with keys from graph nodes and values -1, and low as a dictionary with keys from graph nodes and values -1.

DSA Python

graph = {
    0: [1, 2],
    1: [0, 2, 3],
    2: [0, 1],
    3: [1, 4],
    4: [3]
}
# Your code here

Hint

Initialize disc and low dictionaries with all nodes set to -1.

3

Implement DFS to find articulation points

Define a function dfs(u, parent) that uses the global time, updates disc[u] and low[u], and finds articulation points. Use a set articulation_points to store them. Iterate neighbors with for v in graph[u]:. Follow the standard articulation point logic with discovery and low times.

DSA Python

graph = {
    0: [1, 2],
    1: [0, 2, 3],
    2: [0, 1],
    3: [1, 4],
    4: [3]
}
time = 0
disc = {node: -1 for node in graph}
low = {node: -1 for node in graph}

# Your code here

Hint

Use recursion and update disc and low times carefully. Remember to handle root node separately.

4

Print the articulation points

Print the sorted list of articulation points using print(sorted(articulation_points)).

DSA Python

graph = {
    0: [1, 2],
    1: [0, 2, 3],
    2: [0, 1],
    3: [1, 4],
    4: [3]
}
time = 0
disc = {node: -1 for node in graph}
low = {node: -1 for node in graph}
articulation_points = set()

def dfs(u, parent):
    global time
    children = 0
    disc[u] = time
    low[u] = time
    time += 1

    for v in graph[u]:
        if disc[v] == -1:
            children += 1
            dfs(v, u)
            low[u] = min(low[u], low[v])

            if parent is None and children > 1:
                articulation_points.add(u)
            if parent is not None and low[v] >= disc[u]:
                articulation_points.add(u)
        elif v != parent:
            low[u] = min(low[u], disc[v])

for node in graph:
    if disc[node] == -1:
        dfs(node, None)

# Your code here

Hint

The articulation points in this graph are nodes 1 and 3. Use print(sorted(articulation_points)) to display them.

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