1.
Introduction
2.
Articulation Point
3.
Problem
4.
Solution
4.1.
Approach 1:
4.2.
Approach 2:
4.3.
C++ Implementation
5.
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

GAZAL ARORA
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 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.

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:

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

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.

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.

Live masterclass