Articulation Points in Graph in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is an articulation point in a graph?

An articulation point is a vertex in a graph that, if removed along with its edges, increases the number of connected components. It acts like a critical bridge connecting parts of the graph.

beginner

Why are articulation points important in network analysis?

Articulation points identify critical nodes whose failure can disconnect the network. This helps in understanding vulnerabilities and improving network reliability.

intermediate

What is the role of 'discovery time' and 'low time' in finding articulation points?

Discovery time records when a node is first visited in DFS. Low time tracks the earliest visited vertex reachable from the subtree rooted at that node. Comparing these helps detect articulation points.

intermediate

In DFS, when is a root node considered an articulation point?

A root node is an articulation point if it has two or more children in the DFS tree. Removing it would disconnect those children from each other.

intermediate

What is the time complexity of finding articulation points using DFS?

The time complexity is O(V + E), where V is the number of vertices and E is the number of edges, because each vertex and edge is visited once during DFS.

What happens if you remove an articulation point from a connected graph?

A The graph loses all edges

B The graph remains connected

C The graph becomes a tree

D The graph becomes disconnected

Removing an articulation point increases the number of connected components, making the graph disconnected.

Which algorithm technique is commonly used to find articulation points?

A Depth-First Search

B Kruskal's Algorithm

C Dijkstra's Algorithm

D Breadth-First Search

Depth-First Search (DFS) is used to explore the graph and compute discovery and low times to find articulation points.

What does the 'low time' of a node represent in DFS?

A The earliest discovery time reachable from the node's subtree

B The time when the node was last visited

C The number of edges connected to the node

D The total time taken to visit all nodes

Low time is the earliest discovery time reachable from the node or its descendants, including back edges.

When is a non-root node considered an articulation point?

A If it has no children

B If it is connected to all other nodes

C If it has a child with low time >= its discovery time

D If it has the highest discovery time

A non-root node is an articulation point if it has a child whose low time is greater or equal to the node's discovery time.

What is the initial value of discovery and low times before DFS starts?

A 0

B -1 or None

C Infinity

D Number of vertices

Discovery and low times are initialized to -1 or None to indicate unvisited nodes before DFS.

Explain how DFS helps in identifying articulation points in a graph.

Think about how visiting nodes and tracking earliest reachable nodes helps find critical points.

Describe the difference between articulation points and bridges in a graph.

One is about removing a node, the other about removing an edge.

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