Articulation Points in a Graph

Problem

Given an undirected graph G, find all the articulation points in the graph.

For a connected undirected graph, an articulation point or a cut vertex is a vertex in the graph removing which disconnects the graph.   For a disconnected undirected graph, an articulation point or a cut vertex is a vertex removing which increases the number of connected components.   Examples of Articulation Points:

Input:

• The first line contains two integers, V and E.
• The following E lines have two integers, u and v, representing an edge between vertex u and v.
   

Output: 

Print all the articulation points in one line.
 

The questions you should ask the interviewer:

1. What are the constraints on V and E?
    

Alert Ninjas:  Don’t stop now! Enroll in the Competitive Programming course today and start coding. Learn the art of writing time and space-efficient code and compete in code competitions worldwide. 
 

For example,

Let's look at an undirected graph G and try to find articulation points by following the definition:

Input: V = 5, E = 6. 1 0 0 4 1 4 2 3 2 4 3 4   Output: 4. Explanation:   In the above graph G with a vertex set V = (0, 1, 2, 3, 4) and edges (E1, E2, E3, E4, E5, E6), let's start with the vertex A and see if removing it and its associated edges will disconnect the graph. Removing vertex 0 and associated edges E1 and E2 doesn't disconnect the graph. Therefore, 0 isn't an articulation point.   Let's remove the 4th vertex and associated edges E2, E3, E4, and E5. This divides graph G into the following two connected components: The first component is C1 with vertex set (0, 1) and edge set E1. The second component is C2 with vertex set (2, 3) and edge set E6.   Removing E satisfies the definition. Therefore, the vertex E is an articulation point in G.   You can try removing 1, 2, 3 also, but you will observe that only E satisfies the definition.

Recommended: Please try to solve it yourself before moving on to the solution.

Solution

Approach 1: 

Idea: A simple method is to remove all vertices one by one and see if it causes the graph to become disconnected.
 

Algorithm:

1. Loop around all the vertices.
2. Do the following for each vertex v
    

a) Remove v from the graph.

b) Check if the graph is still connected (we can use BFS or DFS to check that)

c) Add v to the graph again.
 

Time Complexity: O(V*(V+E)). For every v, BFS/DFS will take O(V+E) time to check for the graph's connectivity. Therefore, O(V*(V+E)) is the time complexity.

Can we do better?

Approach 2: 

Idea: The idea is to use DFS and find the articulation points simultaneously with some extra coding. As DFS takes O(V+E) time, therefore the time complexity of this approach will be O(V+E).

We will visit the vertices in the tree form known as the DFS tree. In the DFS tree, a vertex u in the graph is the parent of another vertex v if v is adjacent to u and discovered by u.

In the DFS tree, a vertex u is articulation point if any of the following conditions is true:

1. u is the root of the DFS tree, and it has at least two children.

 2.  u is not the root of the DFS tree, and it has a child v such that no vertex in the subtree rooted with v has a back edge to any of u's ancestors in the DFS tree.

Note: A leaf in a DFS Tree is never an articulation point.
 

Algorithm: 

1. In DFS traversal, maintain a parent array where parent[i] stores the parent of vertex i and a visited array. 

2. For condition 1:

• For every vertex u, count its children. If the currently visited vertex u is the root, i.e., parent[u] = NULL and has more than two children, it is an articulation point. 
   

3. For condition 2:

• Maintain an array disc[] to store vertices discovery time. For each node u, we must determine the earliest visited vertex (the vertex with the shortest discovery time) reached from the subtree rooted with u. As a result, we keep an additional array low[] defined as follows.
   
• low[u] = min(disc[u], disc[k]), where k is an ancestor of node u, and there is a back edge from some descendant of u to k.
   
• After determining the lowest discovery number for all vertices, the algorithm takes a pair of vertices to determine articulation points. Consider the vertices V1 and V2. V1 is the parent vertex, while V2 is the child vertex. If the lowest discovery number of V1 is more than or equal to the lowest discovery number of V2, then V1 is an articulation point.
   

C++ Implementation

#include <bits/stdc++.h> using namespace std; // A function to add edges in the graph. void addEdge(vector<vector<int>> &adj, int u, int v) { adj[u].push_back(v); adj[v].push_back(u); } void APUtil(vector<vector<int>> &adj, vector<bool> &visited, vector<int> &disc, vector<int> &low, int &time, int u, int parent, vector<bool> &AP) { // To count the children in the DFS Tree. int child = 0; visited[u] = true; // Initialise the discovery time and the low value for u. disc[u] = ++time; low[u] = time; for (auto v : adj[u]) { // If v is not visited yet, make it a child of u in the DFS tree and repeat for it. if (!visited[v]) { child++; APUtil(adj, visited, disc, low, time, v, u, AP); // Check if the subtree rooted at v has a back edge to the ancestors of u. low[u] = min(low[u], low[v]); // If u is not the root and the low value of one of its children is more than the discovery time value of u. if (low[v] >= disc[u] && parent != -1) AP[u] = true; } // Update low value of u for the parent function calls. else if (v != parent) low[u] = min(low[u], disc[v]); } // Case 1, if u is the root of the DFS tree and has more than one child. if (parent == -1 && child > 1) AP[u] = true; } void AP(vector<vector<int>> &adj, int V) { vector<int> disc(V);    vector<int> low(V);    vector<bool> visited(V, false);    vector<bool> AP(V, false);  int time = 0; int par = -1; // Using the for loop so that the code works for disconnected the graph. for (int u = 0; u < V; ++u){ if (!visited[u]) APUtil(adj, visited, disc, low, time, u, par, AP); } // Printing the Articulation points. for (int i = 0; i < V; i++){ if (AP[i] == true) cout << i << " "; } } int main() { cout << "Articulation points: "; int V = 5; int E = 6; vector<vector<int>> adj(V); addEdge(adj, 1, 0); addEdge(adj, 0, 4); addEdge(adj, 1, 4); addEdge(adj, 2, 3); addEdge(adj, 2, 4); addEdge(adj, 3, 4); AP(adj, V); return 0; } You can also try this code with Online C++ Compiler Run Code

Input: V = 5, E = 6.

• 1 0
• 0 4
• 1 4
• 2 3
• 2 4
• 3 4
   

Output: 4.

Time Complexity: O(V+E). The time complexity of a simple DFS for adjacency list representation of the graph.

Naive approach to find Articulation Points (or Cut Vertices) in a Graph

The naive approach to finding articulation points involves removing each vertex one by one and checking if the graph remains connected. If removing a vertex disconnects the graph, that vertex is an articulation point. This method requires recalculating the graph’s connectivity for each vertex, making it less efficient for larger graphs.

• Java
• Python
• JavaScript
• C#

Java

import java.util.*;

public class ArticulationPoints {
    public static void findArticulationPoints(int[][] graph) {
        int V = graph.length;
        for (int i = 0; i < V; i++) {
            boolean[] visited = new boolean[V];
            dfs(graph, (i + 1) % V, visited, i);
            if (!allVisited(visited, i)) {
                System.out.println("Articulation Point: " + i);
            }
        }
    }

    private static void dfs(int[][] graph, int start, boolean[] visited, int skip) {
        visited[start] = true;
        for (int i = 0; i < graph.length; i++) {
            if (graph[start][i] == 1 && !visited[i] && i != skip) {
                dfs(graph, i, visited, skip);
            }
        }
    }

    private static boolean allVisited(boolean[] visited, int skip) {
        for (int i = 0; i < visited.length; i++) {
            if (i != skip && !visited[i]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[][] graph = {{0, 1, 0, 0, 0},
                         {1, 0, 1, 1, 1},
                         {0, 1, 0, 0, 1},
                         {0, 1, 0, 0, 1},
                         {0, 1, 1, 1, 0}};
        findArticulationPoints(graph);
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

def dfs(graph, start, visited, skip):
    visited[start] = True
    for i, connected in enumerate(graph[start]):
        if connected == 1 and not visited[i] and i != skip:
            dfs(graph, i, visited, skip)

def all_visited(visited, skip):
    for i, v in enumerate(visited):
        if i != skip and not v:
            return False
    return True

def find_articulation_points(graph):
    V = len(graph)
    for i in range(V):
        visited = [False] * V
        dfs(graph, (i + 1) % V, visited, i)
        if not all_visited(visited, i):
            print(f"Articulation Point: {i}")

graph = [[0, 1, 0, 0, 0],
         [1, 0, 1, 1, 1],
         [0, 1, 0, 0, 1],
         [0, 1, 0, 0, 1],
         [0, 1, 1, 1, 0]]

find_articulation_points(graph)

You can also try this code with Online Python Compiler

Run Code

JavaScript

function dfs(graph, visited, node, skip) {
    visited[node] = true;
    for (let i = 0; i < graph[node].length; i++) {
        if (graph[node][i] === 1 && i !== skip && !visited[i]) {
            dfs(graph, visited, i, skip);
        }
    }
}

function isAllVisited(visited, skip) {
    for (let i = 0; i < visited.length; i++) {
        if (i !== skip && !visited[i]) {
            return false;
        }
    }
    return true;
}

function findArticulationPoints(graph) {
    const V = graph.length;
    for (let v = 0; v < V; v++) {
        const visited = new Array(V).fill(false);
        const start = v === 0 ? 1 : 0;
        dfs(graph, visited, start, v);
        if (!isAllVisited(visited, v)) {
            console.log(`Articulation Point: ${v}`);
        }
    }
}

const graph = [
    [0, 1, 0, 0, 0],
    [1, 0, 1, 1, 0],
    [0, 1, 0, 1, 0],
    [0, 1, 1, 0, 1],
    [0, 0, 0, 1, 0]
];

findArticulationPoints(graph);

You can also try this code with Online Javascript Compiler

Run Code

C#

using System;

class ArticulationPoints {
    static void DFS(int[,] graph, bool[] visited, int node, int skip) {
        visited[node] = true;
        for (int i = 0; i < graph.GetLength(1); i++) {
            if (graph[node, i] == 1 && i != skip && !visited[i]) {
                DFS(graph, visited, i, skip);
            }
        }
    }

    static bool IsAllVisited(bool[] visited, int skip) {
        for (int i = 0; i < visited.Length; i++) {
            if (i != skip && !visited[i]) {
                return false;
            }
        }
        return true;
    }

    public static void FindArticulationPoints(int[,] graph) {
        int V = graph.GetLength(0);
        for (int v = 0; v < V; v++) {
            bool[] visited = new bool[V];
            int start = (v == 0) ? 1 : 0;
            DFS(graph, visited, start, v);
            if (!IsAllVisited(visited, v)) {
                Console.WriteLine("Articulation Point: " + v);
            }
        }
    }

    static void Main(string[] args) {
        int[,] graph = {
            { 0, 1, 0, 0, 0 },
            { 1, 0, 1, 1, 0 },
            { 0, 1, 0, 1, 0 },
            { 0, 1, 1, 0, 1 },
            { 0, 0, 0, 1, 0 }
        };

        FindArticulationPoints(graph);
    }
}

Output

Articulation Point: 1
Articulation Point: 3

You can also try this code with Online C++ Compiler

Run Code

Frequently Asked Questions

What is meant by articulation point?

A vertex in a graph is referred to as an articulation point if removing it together with any connected edges causes the graph to have more connected components. If the graph initially had n connected components, after removal it will have more than n.

How do you calculate articulation points?

Articulation points or cut vertices in a graph can be calculated by Tarjan’s Algorithm. The main idea is to use a depth-first search in a tree form. In a graph, there can be more than one articulation point or none. 

What are articulation points in a graph?

An articulation point in a graph is a vertex with a special property. Removing it together with any connected edges causes the graph to have more connected components than it initially had. Articulation points in the graph are also known as cut vertices.

How many articulation points are in a graph?

The number of Articulation points varies from graph to graph. A graph can have multiple articulation points. The only requirement is that the removal of particular vertex results in more connected components. Articulation points in the graph are also known as cut vertices.

What is articulation point in bridge?

When there is no longer a path connecting two vertices in a graph, an edge between them is said to be a bridge. Its definition resembles that of Articulation Points quite a bit. It shows vulnerabilities in the specific network just like they do.

Conclusion

We learned about Articulation Points in this article and designed an algorithm to find all articulation points in a given graph.

We proposed two approaches for the algorithm:

1. Approach 1 involves removing all vertices one by one and checking if it caused the graph to become disconnected. It was taking O(V*(V+E)) time.
    
2. In Approach 2, we used DFS, taking O(V+E) time which is better than Approach 1.

Master graphs from here.

Recommended Problems:

• Graph Bridge
• Longest Path In Graph
• Graph Valid Tree
  
  Related Articles:
• Detect cycle in an undirected graph
• Data Structure