×

Search anything:

# Find articulation point in Graph

#### Algorithms Graph Algorithms

Get this book -> Problems on Array: For Interviews and Competitive Programming

In this article we'll be discussing on how to find articulation point in Graph. Firstly we'll discuss on the Introduction to Articulation Points. Secondly, we'll understand the Articulation Points concept with a graph example. At the end will write a Pseudo code & implementation for the same.

Following are the sections of this article:-

### 1. Introduction

Consider a Graph(`G`) which is formed by Vertices(`V`) and Edges(`E`) is said to have an Articulation point of Cut vertex(V) if by removing it and all the edges(E) associated with it results in increase of the total number of connected components in the Graph(G).
In other words, A vertex in an Undirected graph is an Articulation point if and only if by removing it, it disconnects the graph.

### 2. Example for Articulation Points

Example, Let us consider the below Fig a

###### Fig a - Undirected Graph

From the above Graph diagram, `vertex 0` and all the edges associated with it, i.e. the edges `0-1`, `0-2` and `0-3` are removed. If we want to reach the vertex 2, 3 or 4 from the vertices 1 and 5, their will be no path left and hence the graph will split into two separate components. Similarly if the `vertex 1` is removed, then it'll disconnect the `vertex 5` for all the other vertices.
These steps are shown in the below diagram Fig b(1 & 2),

(1)
(2)

###### Fig b(1 & 2) - After removal of Articulation Points(0 & 1) from Fig a

From the above Graph example its clear that, removal of an articulation point will increase the number of connected graph and hence for the Graph(G) at Fig a articulation points are `vertex 0 & 1`.

### 3. Pseudo Code and Implementation

As our main focus to produce this article is to write an algorithm to find Articulation points in a Graph, Lets get started.
Consider a Graph(`G`) that is formed by vertices `V` and edges `E`, Following are the ideal steps-

1. Remove a vertex `v` from the Graph(`G`).
2. Check, If the Graph(`G`) is still remains as a connected graph, we say no `articulation points`. This can be processed by DFS traversal algorithm.
Else, we print those vertex `v` as an `articulation point` or `Cut vertex` in the given Graph(`G`).
• Pseudo Code
Following is the Pseudo code snippets function, for finding all articulation points in a graph.
``````function totalArticulation_points(adj[][], V)
count = 0
for i = 0 to V
visited[i] = false
initial_val = 0
for i = 0 to V
if visited[i] == false
DFS(adj, V, visited, i)
initial_val = initial_val+1

for i=0 to V
for j = 0 to V
visited[j] = false

nval = 0
for j= 0 to V
if visited[j] == false AND j != i
nval = nval + 1
DFS(adj, n, visited, j)
if nval > initial_val
count = count + 1
for j= 0 to V
return count
``````

From the above code snippet, we'll get count of all the Articulation points from the Graph. We also see a Traversal approach(DFS) has been used.
Similar to our previous discussion on Bridges, even Articulation points can be found using `DFS`. Kindly go through the basics of the concept of DFS from this article An algorithm to find all bridges in a Graph.

• Implementation
We have implemented the code in Python(3.8)
``````
from collections import defaultdict

#Using adjacency list representation, This class represents an undirected graph

class Graph:

def __init__(self,vertices):
self.V= vertices #No. of vertices
self.graph = defaultdict(list) # default dictionary to store graph
self.Time = 0

# function to add an edge to graph
self.graph[u].append(v)
self.graph[v].append(u)

'''A recursive function that finds and prints Cut Vertex
or articulation points using DFS traversal

u --> The vertex to be visited next
visited[] --> A list, which keeps tract of visited vertices
disc[] --> A list, which Stores discovery times of visited vertices
parent[] --> A list, which Stores parent vertices in DFS tree
cv[] --> A list, which Stores the Cut Vertex or articulation points
'''
def cutVertexDetails(self,u, visited, parent, low, disc, cv):

#Count of children in current node
children = 0

# Marking the current node as visited and print it
visited[u]= True

# Initialize discovery time and low value
disc[u] = self.Time
low[u] = self.Time
self.Time += 1

#Recursive execution for all the vertices adjacent to this vertex
for v in self.graph[u]:
if visited[v] == False :
parent[v] = u
children += 1
self.cutVertexDetails(v, visited, parent, low, disc, cv)

low[u] = min(low[u], low[v])

# u is a Cut Vertex in following cases
# if,u is root of DFS tree & has two or more chilren.
if parent[u] == -1 and children > 1:
cv[u] = True
# If, u is not root & low value of one of its child
# is more than discovery value of vertex u.
if parent[u] != -1 and low[v] >= disc[u]:
cv[u] = True

elif v != parent[u]:
# Update low value of u for parent function calls.
low[u] = min(low[u], disc[v])

# DFS based function to find all Cut Vertex or articulation point.
# It uses recursive function, inside function findCutVertex()
def findCutVertex(self):

# Mark all the vertices as not visited and Initialize parent and visited
visited = [False] * (self.V)
disc = [float("Inf")] * (self.V)
low = [float("Inf")] * (self.V)
parent = [-1] * (self.V)
#To store Cut vertex or articulation points
cv = [False] * (self.V)

# to find Cut vertex or articulation points
# in DFS tree rooted with vertex 'i'
for i in range(self.V):
if visited[i] == False:
self.cutVertexDetails(i, visited, parent, low, disc, cv)
for p, value in enumerate (cv):
if value == True:
print(p)

# Program Execution starts from here
if __name__ == '__main__':

# Creating a graph given in the above diagram (Fig a)
g = Graph(6)
print("\nArticulation points in graph are:")
g.findCutVertex()

# Output @console after running the script
#
# Articulation points in graph are:
# 0
# 1

``````

### 4. Time and Space Complexity

The `Time complexity` of the above approach is O(V + E) where `V` is the total number of Vertices and `E` is the total number of Edges in the Graph(G). And coming to `Space complexity` of the above approach is O(V) where V is the total number of Vertices in the Graph(G).

### 5. Conclusion

Lastly we are at the end of the article. We explored a bit on the Articulation Points concept of graph. This article is the continuation of my previous article, An algorithm to find all bridges in a Graph. There are many applications in which we make use of this Articulation Points and Bridges. Few are-

• Finding a vulnerable node in a topology of network.
• Calculating the Shortest path or Feasible path between source and destination.

Hope it was an informative article, Thanks!

#### Shiva Basava P

Shiva is a Senior Analyst/ Software Engineer at Capgemini Technology Services India Limited and has been a Software Developer, Intern at OPENGENUS