Articulation Points in Graph in DSA Java

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. These intersections are 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; find articulation points

Goal: Identify nodes that, when removed, increase the number of disconnected parts 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 the graph 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 or articulation points

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 deeper to find articulation points

Step 4: From 3, visit 4, 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: Explore child nodes to check connectivity

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

low[3] = 3, low[4] = 4
Stack: [1,2,3]

Why: Update low values to detect articulation points

Step 6: From 3, visit 5, set discovery and low values

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

Why: Explore another child of 3

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

low[3] = 3, low[5] = 5
Stack: [1,2,3]

Why: Update low values after visiting all children

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

low[2] = 2, low[3] = 3
Stack: [1,2]

Why: Update low values to check articulation condition

Step 9: Backtrack from 2 to 1, update low[1] = min(low[1], low[2]) = 1

low[1] = 1, low[2] = 2
Stack: [1]

Why: Update low values for root node

Step 10: Check articulation points: node 3 is articulation point because low[child] >= disc[node]

Articulation points: 3

Why: Node 3 separates the graph if removed

Result:

Articulation points: 3

Annotated Code

DSA Java

import java.util.*;

public class ArticulationPoints {
    private int time = 0;

    public List<Integer> findArticulationPoints(int n, List<List<Integer>> graph) {
        boolean[] visited = new boolean[n];
        int[] disc = new int[n];
        int[] low = new int[n];
        int[] parent = new int[n];
        boolean[] ap = new boolean[n];

        Arrays.fill(parent, -1);

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i, visited, disc, low, parent, ap, graph);
            }
        }

        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (ap[i]) result.add(i + 1); // +1 for 1-based node numbering
        }
        return result;
    }

    private void dfs(int u, boolean[] visited, int[] disc, int[] low, int[] parent, boolean[] ap, List<List<Integer>> graph) {
        visited[u] = true;
        disc[u] = low[u] = ++time;
        int children = 0;

        for (int v : graph.get(u)) {
            if (!visited[v]) {
                children++;
                parent[v] = u;
                dfs(v, visited, disc, low, parent, ap, graph);

                low[u] = Math.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] = Math.min(low[u], disc[v]);
            }
        }
    }

    public static void main(String[] args) {
        ArticulationPoints apFinder = new ArticulationPoints();
        int n = 5;
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());

        // edges: 1-2, 1-3, 2-3, 3-4, 3-5
        graph.get(0).add(1); graph.get(1).add(0);
        graph.get(0).add(2); graph.get(2).add(0);
        graph.get(1).add(2); graph.get(2).add(1);
        graph.get(2).add(3); graph.get(3).add(2);
        graph.get(2).add(4); graph.get(4).add(2);

        List<Integer> articulationPoints = apFinder.findArticulationPoints(n, graph);
        System.out.print("Articulation points: ");
        for (int node : articulationPoints) {
            System.out.print(node + " ");
        }
        System.out.println();
    }
}

disc[u] = low[u] = ++time;

Set discovery time and low value for node u

for (int v : graph.get(u)) {

Traverse all neighbors of u

if (!visited[v]) {

If neighbor v not visited, explore it

children++;

Count children of u in DFS tree

parent[v] = u;

Set parent of v to u

dfs(v, visited, disc, low, parent, ap, graph);

Recursive DFS call to explore v

low[u] = Math.min(low[u], low[v]);

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

if (parent[u] == -1 && children > 1) { ap[u] = true; }

Root node with multiple children is articulation point

if (parent[u] != -1 && low[v] >= disc[u]) { ap[u] = true; }

Non-root node is articulation point if child's low >= disc[u]

} else if (v != parent[u]) { low[u] = Math.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 to store discovery, low, parent, visited, and recursion stack

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

Edge Cases

Graph with no edges (all isolated nodes)

No articulation points because removing any node does not disconnect others

DSA Java

if (!visited[i]) { dfs(i, visited, disc, low, parent, ap, graph); }

Graph with a single node

No articulation points because there's no other node to disconnect

DSA Java

if (!visited[i]) { dfs(i, visited, disc, low, parent, ap, graph); }

Graph with multiple disconnected components

Algorithm runs DFS on each component separately and finds articulation points in each

DSA Java

for (int i = 0; i < n; i++) { if (!visited[i]) { dfs(...); } }

When to Use This Pattern

When a problem asks for nodes whose removal increases disconnected parts of a graph, use articulation points detection with DFS and low-link values.

Common Mistakes

Mistake: Not handling the root node's special case where it must have more than one child to be an articulation point
Fix: Add condition: if parent[u] == -1 and children > 1 then mark u as articulation point

Mistake: Updating low[u] incorrectly by not considering back edges to ancestors
Fix: In DFS, update low[u] = min(low[u], disc[v]) for visited neighbors v not equal to parent[u]

Summary

Finds nodes that disconnect the graph if removed

Use when you need to find critical points in network connectivity

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 that forms a cycle in the graph

B. A vertex with the highest degree in the graph

C. A vertex connected to all other vertices

D. A vertex which, when removed, increases the number of connected components

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 which, when removed, increases the number of connected components matches this definition exactly.

3. Final Answer:

   A vertex which, when removed, increases the number of connected components -> Option D

4. Quick Check:

   Articulation point = vertex breaking connectivity [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 declare a graph adjacency list in Java for articulation point detection?

easy

A. int graph[][] = new int[];

B. HashMap graph = new HashMap<>();

C. ArrayList graph = new ArrayList<>();

D. List<Integer> graph = new List<>();

Solution

1. Step 1: Understand adjacency list structure

   An adjacency list for a graph is usually a list of lists, where each inner list holds neighbors of a vertex.

2. Step 2: Check Java syntax for adjacency list

   ArrayList graph = new ArrayList<>(); correctly declares an ArrayList of ArrayLists of Integers, suitable for adjacency list.

3. Final Answer:

   ArrayList graph = new ArrayList<>(); -> Option C

4. Quick Check:

   Adjacency list = list of lists [OK]

Hint: Adjacency list uses list of lists in Java [OK]

Common Mistakes:

• Using 2D array without size initialization
• Using HashMap with wrong value type
• Trying to instantiate interface List directly

3. Consider the following Java code snippet for articulation point detection. What will be the output when the graph has edges: 0-1, 1-2, 1-3?

int V = 4;
ArrayList graph = new ArrayList<>();
for (int i = 0; i < V; i++) graph.add(new ArrayList<>());
graph.get(0).add(1);
graph.get(1).add(0);
graph.get(1).add(2);
graph.get(2).add(1);
graph.get(1).add(3);
graph.get(3).add(1);
// Articulation points found: 1

medium

A. []

B. [1]

C. [2, 3]

D. [0, 1]

Solution

1. Step 1: Analyze the graph structure

   The graph has vertices 0,1,2,3 with edges 0-1, 1-2, 1-3. Vertex 1 connects to all others.

2. Step 2: Identify articulation points

   Removing vertex 1 disconnects the graph into three parts, so 1 is an articulation point. Others are not.

3. Final Answer:

   [1] -> Option B

4. Quick Check:

   Only vertex 1 breaks connectivity [OK]

Hint: Check which vertex removal splits graph [OK]

Common Mistakes:

• Assuming leaf nodes are articulation points
• Including vertices with degree 1 as articulation points
• Ignoring connectivity after removal

4. The following Java code snippet is intended to find articulation points but has a bug. What is the error?

void dfs(int u, int parent) {
  visited[u] = true;
  disc[u] = low[u] = time++;
  int children = 0;
  for (int v : graph.get(u)) {
    if (!visited[v]) {
      children++;
      dfs(v, u);
      low[u] = Math.min(low[u], low[v]);
      if (parent != -1 && low[v] >= disc[u])
        articulation[u] = true;
    } else if (v != parent) {
      low[u] = Math.min(low[u], disc[v]);
    }
  }
  if (parent == -1 && children > 1)
    articulation[u] = true;
}

medium

A. The time variable is not initialized before DFS

B. The condition for root articulation point is incorrect

C. The low array is not updated correctly for back edges

D. The visited array is not marked true for vertex u

Solution

1. Step 1: Check initialization of time variable

   The variable 'time' is used to assign discovery times but must be initialized before DFS starts.

2. Step 2: Verify other parts of DFS

   Conditions for root and back edges are correct; visited[u] is marked true properly.

3. Final Answer:

   The time variable is not initialized before DFS -> Option A

4. Quick Check:

   Uninitialized time causes wrong discovery times [OK]

Hint: Initialize time counter before DFS call [OK]

Common Mistakes:

• Forgetting to initialize time before DFS
• Misusing parent check for root node
• Not updating low values for back edges

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

hard

A. [1, 3]

B. [0, 2]

C. [3]

D. [1]

Solution

1. Step 1: Analyze the graph structure

   Vertices 0,1,2 form a triangle (cycle). Edges 1-3 and 3-4 form a chain attached to vertex 1.

2. Step 2: Identify articulation points

   Removing vertex 1 disconnects 3 and 4 from the cycle, so 1 is an articulation point. Removing 3 disconnects 4, so 3 is also an articulation point. Vertices 0 and 2 are in a cycle, so not articulation points.

3. Final Answer:

   [1, 3] -> Option A

4. Quick Check:

   Vertices breaking connectivity: 1 and 3 [OK]

Hint: Check vertices whose removal splits graph into parts [OK]

Common Mistakes:

• Assuming cycle vertices are articulation points
• Missing vertex 3 as articulation point
• Only considering vertex 1 as articulation point