Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Articulation Point
3.
Problem
4.
Solution
4.1.
Approach 1: 
4.2.
Approach 2: 
4.3.
C++ Implementation
5.
Frequently Asked Questions
5.1.
What is meant by articulation point?
5.2.
How do you calculate articulation points?
5.3.
What are articulation points in a graph?
5.4.
How many articulation points are in a graph?
5.5.
What is articulation point in bridge?
6.
Conclusion
Last Updated: Mar 27, 2024
Hard

Articulation Points in a Graph

Author GAZAL ARORA
7 upvotes
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Hello Readers, In this article, we will learn how to calculate the number of articulation points in a graph. We’ll also go through the definition of articulation points. In graphs, It is important to understand the brute force approach too, which we have discussed here. 

Articulation Points in a Graph

Articulation Point

If removing a vertex and its related edges causes the graph to become disconnected, the vertex is considered to be an articulation point in the graph. Therefore, the number of related components in a graph grows as articulation points are removed. A connected component, or simply component, is a subgraph where every pair of nodes is connected to every other node by a path.

Sometimes articulation points are referred to as cut vertices.

Finding all of a graph's articulation points is the primary goal here which can be done by Tarjan’s Algorithm.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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:

Articulation Points and Bridges
Articulation Points in a graph

 

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:

Graph G in articulation point

 

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.
root of the DFS tree

 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.

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;
}

 

Input: V = 5, E = 6.

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

Output: 4.

output

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

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:

Apart from that, use Coding Ninjas Studio to practice a wide range of DSA questions asked in various interviews. It will assist you in mastering efficient coding techniques, and you will also get interview experiences from people working in big companies.

Previous article
Minimum possible modifications in the matrix to reach the destination
Next article
Find First Undeleted Integer From K to N in Given Unconnected Graph After Performing Q Queries.
Live masterclass