Skip to main content

Articulation points in a graph

In graph theory, an articulation point (or cut vertex) is a vertex in a connected graph whose removal would disconnect the graph or increase the number of connected components in the graph.

Articulation point example in graph

More formally, let G be a connected undirected graph. An articulation point of G is a vertex whose removal from G would result in a disconnected graph or a graph with more connected components than the original graph.

Intuitively, an articulation point can be thought of as a critical point in the graph, whose removal would break the connectivity of the graph. The concept of articulation points is important in network analysis, as it helps identify key nodes that play a crucial role in maintaining the connectivity of a network.

Code Solution

// Include header file
#include <iostream>
#include <vector>

using namespace std;
/*
    C++ program for
    Articulation points in a graph
*/
class Graph
{
	public: int vertices;
	vector < vector < int > > adjacencylist;
	int time;
	Graph(int vertices)
	{
		this->vertices = vertices;
		this->time = 0;
		for (int i = 0; i < this->vertices; ++i)
		{
			this->adjacencylist.push_back( vector < int > ());
		}
	}
	// Connect two node with new edge
	void addEdge(int u, int v)
	{
		if (u >= this->vertices || v >= this->vertices || v < 0 || u < 0)
		{
			//  invalid node
			return;
		}
		// First edge from  (u to v)
		this->adjacencylist.at(u).push_back(v);
		if (u == v)
		{
			// Self loop
			return;
		}
		// Second edge from  (v to u)
		this->adjacencylist.at(v).push_back(u);
	}
	int min(int a, int b)
	{
		if (a < b)
		{
			return a;
		}
		return b;
	}
	void findDFS(int u, bool visited[], int disc[], 
      int low[], int parent[], bool point[])
	{
		visited[u] = true;
		this->time = this->time + 1;
		disc[u] = this->time;
		low[u] = this->time;
		int children = 0;
		int i = 0;
		int v = 0;
		while (i < this->adjacencylist.at(u).size())
		{
			v = this->adjacencylist.at(u).at(i);
			if (visited[v] == false)
			{
				parent[v] = u;
				children += 1;
				this->findDFS(v, visited, disc, low, parent, point);
				if ((parent[u] == -1 && children > 1) 
                    || (parent[u] != -1 && low[v] >= disc[u]))
				{
					// When u is Articulation point
					point[u] = true;
				}
				low[u] = this->min(low[u], low[v]);
			}
			else if (v != parent[u])
			{
				low[u] = this->min(low[u], disc[v]);
			}
			i++;
		}
	}
	void findArticulationPoints()
	{
		// Define some auxiliary variable which is store managing 
		// execution process
		int disc[this->vertices];
		int low[this->vertices];
		int parent[this->vertices];
		// Dicating status of node visited
		bool visited[this->vertices];
		// Indicates the information of articulation point in graph
		bool point[this->vertices];
		// Reset time in new case 
		this->time = 0;
		// Set default value
		for (int i = 0; i < this->vertices; ++i)
		{
			visited[i] = false;
			parent[i] = -1;
			point[i] = false;
		}
		// Perform dfs operation
		for (int i = 0; i < this->vertices; ++i)
		{
			if (visited[i] == false)
			{
				this->findDFS(i, visited, disc, low, parent, point);
			}
		}
		// Resultat indicator
		bool result = false;
		cout << "\n Articulation points : ";
		for (int i = 0; i < this->vertices; ++i)
		{
			if (point[i] == true)
			{
				// When i is articulation point
				result = true;
				cout << " " << i;
			}
		}
		if (result == false)
		{
			cout << " None \n";
		}
	}
	// Display graph nodes and edges
	void printGraph()
	{
		cout << "\n Graph Adjacency List ";
		for (int i = 0; i < this->vertices; ++i)
		{
			cout << " \n [" << i << "] :";
			// iterate edges of i node
			for (int j = 0; j < this->adjacencylist.at(i).size(); j++)
			{
				cout << "  " << this->adjacencylist.at(i).at(j);
			}
		}
	}
};
int main()
{
	Graph *g = new Graph(10);
	// Connect node with edges
	g->addEdge(0, 1);
	g->addEdge(0, 3);
	g->addEdge(0, 7);
	g->addEdge(1, 2);
	g->addEdge(1, 5);
	g->addEdge(2, 3);
	g->addEdge(2, 4);
	g->addEdge(3, 8);
	g->addEdge(4, 5);
	g->addEdge(4, 6);
	g->addEdge(7, 9);
	// Display graph
	g->printGraph();
	// find articulation point
	g->findArticulationPoints();
	return 0;
}

input

 Graph Adjacency List
 [0] :  1  3  7
 [1] :  0  2  5
 [2] :  1  3  4
 [3] :  0  2  8
 [4] :  2  5  6
 [5] :  1  4
 [6] :  4
 [7] :  0  9
 [8] :  3
 [9] :  7
 Articulation points :  0 3 4 7
import java.util.ArrayList;
/*
    Java program for
    Articulation points in a graph
*/
public class Graph
{
	public int vertices;
	public ArrayList < ArrayList < Integer >> adjacencylist;
	public int time;
	public Graph(int vertices)
	{
		this.vertices = vertices;
		this.adjacencylist = new ArrayList < ArrayList < Integer >> (vertices);
		this.time = 0;
		for (int i = 0; i < this.vertices; ++i)
		{
			this.adjacencylist.add(new ArrayList < Integer > ());
		}
	}
	// Connect two node with new edge
	public void addEdge(int u, int v)
	{
		if (u >= this.vertices || v >= this.vertices || v < 0 || u < 0)
		{
			//  invalid node
			return;
		}
		// First edge from  (u to v)
		adjacencylist.get(u).add(v);
		if (u == v)
		{
			// Self loop
			return;
		}
		// Second edge from  (v to u)
		adjacencylist.get(v).add(u);
	}
	public int min(int a, int b)
	{
		if (a < b)
		{
			return a;
		}
		return b;
	}
	public void findDFS(int u, boolean visited[], 
      int disc[], int low[], int parent[], boolean point[])
	{
		visited[u] = true;
		this.time = this.time + 1;
		disc[u] = this.time;
		low[u] = this.time;
		int children = 0;
		int i = 0;
		int v = 0;
		while (i < adjacencylist.get(u).size())
		{
			v = adjacencylist.get(u).get(i);
			if (visited[v] == false)
			{
				parent[v] = u;
				children += 1;
				findDFS(v, visited, disc, low, parent, point);
				if ((parent[u] == -1 && children > 1) 
                    || (parent[u] != -1 && low[v] >= disc[u]))
				{
					// When u is Articulation point
					point[u] = true;
				}
				low[u] = min(low[u], low[v]);
			}
			else if (v != parent[u])
			{
				low[u] = min(low[u], disc[v]);
			}
			i++;
		}
	}
	public void findArticulationPoints()
	{
		// Define some auxiliary variable which is store managing 
      	// execution process
		int disc[] = new int[this.vertices];
		int low[] = new int[this.vertices];
		int parent[] = new int[this.vertices];
		// Dicating status of node visited
		boolean visited[] = new boolean[this.vertices];
		// Indicates the information of articulation point in graph
		boolean point[] = new boolean[this.vertices];
		// Reset time in new case 
		this.time = 0;
		// Set default value
		for (int i = 0; i < this.vertices; ++i)
		{
			visited[i] = false;
			parent[i] = -1;
			point[i] = false;
		}
		// Perform dfs operation
		for (int i = 0; i < this.vertices; ++i)
		{
			if (visited[i] == false)
			{
				findDFS(i, visited, disc, low, parent, point);
			}
		}
		// Resultat indicator
		boolean result = false;
		System.out.print("\n Articulation points : ");
		for (int i = 0; i < this.vertices; ++i)
		{
			if (point[i] == true)
			{
				// When i is articulation point
				result = true;
				System.out.print(" " + i);
			}
		}
		if (result == false)
		{
			System.out.print(" None \n");
		}
	}
	// Display graph nodes and edges
	public void printGraph()
	{
		System.out.print("\n Graph Adjacency List ");
		for (int i = 0; i < this.vertices; ++i)
		{
			System.out.print(" \n [" + i + "] :");
			// iterate edges of i node
			for (int j = 0; j < this.adjacencylist.get(i).size(); j++)
			{
				System.out.print("  " + this.adjacencylist.get(i).get(j));
			}
		}
	}
	public static void main(String[] args)
	{
		Graph g = new Graph(10);
		// Connect node with edges
		g.addEdge(0, 1);
		g.addEdge(0, 3);
		g.addEdge(0, 7);
		g.addEdge(1, 2);
		g.addEdge(1, 5);
		g.addEdge(2, 3);
		g.addEdge(2, 4);
		g.addEdge(3, 8);
		g.addEdge(4, 5);
		g.addEdge(4, 6);
		g.addEdge(7, 9);
		// Display graph
		g.printGraph();
		// find articulation point
		g.findArticulationPoints();
	}
}

input

 Graph Adjacency List
 [0] :  1  3  7
 [1] :  0  2  5
 [2] :  1  3  4
 [3] :  0  2  8
 [4] :  2  5  6
 [5] :  1  4
 [6] :  4
 [7] :  0  9
 [8] :  3
 [9] :  7
 Articulation points :  0 3 4 7
// Include namespace system
using System;
using System.Collections.Generic;
/*
    Csharp program for
    Articulation points in a graph
*/
public class Graph
{
	public int vertices;
	public List < List < int >> adjacencylist;
	public int time;
	public Graph(int vertices)
	{
		this.vertices = vertices;
		this.adjacencylist = new List < List < int >> (vertices);
		this.time = 0;
		for (int i = 0; i < this.vertices; ++i)
		{
			this.adjacencylist.Add(new List < int > ());
		}
	}
	// Connect two node with new edge
	public void addEdge(int u, int v)
	{
		if (u >= this.vertices || v >= this.vertices || v < 0 || u < 0)
		{
			//  invalid node
			return;
		}
		// First edge from  (u to v)
		this.adjacencylist[u].Add(v);
		if (u == v)
		{
			// Self loop
			return;
		}
		// Second edge from  (v to u)
		this.adjacencylist[v].Add(u);
	}
	public int min(int a, int b)
	{
		if (a < b)
		{
			return a;
		}
		return b;
	}
	public void findDFS(int u, Boolean[] visited, 
      int[] disc, int[] low, int[] parent, Boolean[] point)
	{
		visited[u] = true;
		this.time = this.time + 1;
		disc[u] = this.time;
		low[u] = this.time;
		int children = 0;
		int i = 0;
		int v = 0;
		while (i < this.adjacencylist[u].Count)
		{
			v = this.adjacencylist[u][i];
			if (visited[v] == false)
			{
				parent[v] = u;
				children += 1;
				this.findDFS(v, visited, disc, low, parent, point);
				if ((parent[u] == -1 && children > 1) || 
                    (parent[u] != -1 && low[v] >= disc[u]))
				{
					// When u is Articulation point
					point[u] = true;
				}
				low[u] = this.min(low[u], low[v]);
			}
			else if (v != parent[u])
			{
				low[u] = this.min(low[u], disc[v]);
			}
			i++;
		}
	}
	public void findArticulationPoints()
	{
		// Define some auxiliary variable which is store managing 
		// execution process
		int[] disc = new int[this.vertices];
		int[] low = new int[this.vertices];
		int[] parent = new int[this.vertices];
		// Dicating status of node visited
		Boolean[] visited = new Boolean[this.vertices];
		// Indicates the information of articulation point in graph
		Boolean[] point = new Boolean[this.vertices];
		// Reset time in new case 
		this.time = 0;
		// Set default value
		for (int i = 0; i < this.vertices; ++i)
		{
			visited[i] = false;
			parent[i] = -1;
			point[i] = false;
		}
		// Perform dfs operation
		for (int i = 0; i < this.vertices; ++i)
		{
			if (visited[i] == false)
			{
				this.findDFS(i, visited, disc, low, parent, point);
			}
		}
		// Resultat indicator
		Boolean result = false;
		Console.Write("\n Articulation points : ");
		for (int i = 0; i < this.vertices; ++i)
		{
			if (point[i] == true)
			{
				// When i is articulation point
				result = true;
				Console.Write(" " + i);
			}
		}
		if (result == false)
		{
			Console.Write(" None \n");
		}
	}
	// Display graph nodes and edges
	public void printGraph()
	{
		Console.Write("\n Graph Adjacency List ");
		for (int i = 0; i < this.vertices; ++i)
		{
			Console.Write(" \n [" + i + "] :");
			// iterate edges of i node
			for (int j = 0; j < this.adjacencylist[i].Count; j++)
			{
				Console.Write("  " + this.adjacencylist[i][j]);
			}
		}
	}
	public static void Main(String[] args)
	{
		Graph g = new Graph(10);
		// Connect node with edges
		g.addEdge(0, 1);
		g.addEdge(0, 3);
		g.addEdge(0, 7);
		g.addEdge(1, 2);
		g.addEdge(1, 5);
		g.addEdge(2, 3);
		g.addEdge(2, 4);
		g.addEdge(3, 8);
		g.addEdge(4, 5);
		g.addEdge(4, 6);
		g.addEdge(7, 9);
		// Display graph
		g.printGraph();
		// find articulation point
		g.findArticulationPoints();
	}
}

input

 Graph Adjacency List
 [0] :  1  3  7
 [1] :  0  2  5
 [2] :  1  3  4
 [3] :  0  2  8
 [4] :  2  5  6
 [5] :  1  4
 [6] :  4
 [7] :  0  9
 [8] :  3
 [9] :  7
 Articulation points :  0 3 4 7
package main
import "fmt"
/*
    Go program for
    Articulation points in a graph
*/
type Graph struct {
	vertices int
	adjacencylist [][]int
	time int
}
func getGraph(vertices int) * Graph {
	var me *Graph = &Graph {}
	me.vertices = vertices
	me.adjacencylist =  make([][]int,vertices)
	me.time = 0
	for i := 0 ; i < me.vertices ; i++ {
		me.adjacencylist = append(me.adjacencylist, )
	}
	return me
}
// Connect two node with new edge
func(this Graph) addEdge(u, v int) {
	if u >= this.vertices || v >= this.vertices || v < 0 || u < 0 {
		//  invalid node
		return
	}
	// First edge from  (u to v)
	this.adjacencylist[u] = append(this.adjacencylist[u], v)
	if u == v {
		// Self loop
		return
	}
	// Second edge from  (v to u)
	this.adjacencylist[v] = append(this.adjacencylist[v], u)
}
func(this Graph) min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
func(this Graph) findDFS(u int, visited[] bool, 
	disc[] int, low[] int, parent[] int, point[] bool) {
	visited[u] = true
	this.time = this.time + 1
	disc[u] = this.time
	low[u] = this.time
	var children int = 0
	var i int = 0
	var v int = 0
	for (i < len(this.adjacencylist[u])) {
		v = this.adjacencylist[u][i]
		if visited[v] == false {
			parent[v] = u
			children += 1
			this.findDFS(v, visited, disc, low, parent, point)
			if (parent[u] == -1 && children > 1) || (parent[u] != -1 && 
				low[v] >= disc[u]) {
				// When u is Articulation point
				point[u] = true
			}
			low[u] = this.min(low[u], low[v])
		} else if v != parent[u] {
			low[u] = this.min(low[u], disc[v])
		}
		i++
	}
}
func(this Graph) findArticulationPoints() {
	// Define some auxiliary variable which is store managing 
	// execution process
	var disc =  make([]int,this.vertices)
	var low = 	make([]int,this.vertices)
	var parent = make([]int,this.vertices)
	// Dicating status of node visited
	var visited = make([]bool,this.vertices)
	// Indicates the information of articulation point in graph
	var point = make([]bool,this.vertices)
	// Reset time in new case 
	this.time = 0

	for i:= 0; i < this.vertices; i ++ {

		parent[i] = -1;
	}
	// Perform dfs operation
	for i := 0 ; i < this.vertices ; i++ {
		if visited[i] == false {
			this.findDFS(i, visited, disc, low, parent, point)
		}
	}
	// Resultat indicator
	var result bool = false
	fmt.Print("\n Articulation points : ")
	for i := 0 ; i < this.vertices ; i++ {
		if point[i] == true {
			// When i is articulation point
			result = true
			fmt.Print(" ", i)
		}
	}
	if result == false {
		fmt.Print(" None \n")
	}
}
// Display graph nodes and edges
func(this Graph) printGraph() {
	fmt.Print("\n Graph Adjacency List ")
	for i := 0 ; i < this.vertices ; i++ {
		fmt.Print(" \n [", i, "] :")
		// iterate edges of i node
		for j := 0 ; j < len(this.adjacencylist[i]) ; j++ {
			fmt.Print("  ", this.adjacencylist[i][j])
		}
	}
}
func main() {
	var g * Graph = getGraph(10)
	// Connect node with edges
	g.addEdge(0, 1)
	g.addEdge(0, 3)
	g.addEdge(0, 7)
	g.addEdge(1, 2)
	g.addEdge(1, 5)
	g.addEdge(2, 3)
	g.addEdge(2, 4)
	g.addEdge(3, 8)
	g.addEdge(4, 5)
	g.addEdge(4, 6)
	g.addEdge(7, 9)
	// Display graph
	g.printGraph()
	// find articulation point
	g.findArticulationPoints()
}

input

 Graph Adjacency List  
 [0] :  1  3  7 
 [1] :  0  2  5 
 [2] :  1  3  4 
 [3] :  0  2  8 
 [4] :  2  5  6 
 [5] :  1  4 
 [6] :  4 
 [7] :  0  9 
 [8] :  3 
 [9] :  7
 Articulation points :  0 3 4 7
<?php
/*
    Php program for
    Articulation points in a graph
*/
class Graph
{
	public $vertices;
	public $adjacencylist;
	public $time;
	public	function __construct($vertices)
	{
		$this->vertices = $vertices;
		$this->adjacencylist = array();
		$this->time = 0;
		for ($i = 0; $i < $this->vertices; ++$i)
		{
			$this->adjacencylist[] = array();
		}
	}
	// Connect two node with new edge
	public	function addEdge($u, $v)
	{
		if ($u >= $this->vertices || $v >= $this->vertices 
            || $v < 0 || $u < 0)
		{
			//  invalid node
			return;
		}
		// First edge from  (u to v)
		$this->adjacencylist[$u][] = $v;
		if ($u == $v)
		{
			// Self loop
			return;
		}
		// Second edge from  (v to u)
		$this->adjacencylist[$v][] = $u;
	}
	public	function min($a, $b)
	{
		if ($a < $b)
		{
			return $a;
		}
		return $b;
	}
	public	function findDFS($u, &$visited, 
                              &$disc, &$low, &$parent, &$point)
	{
		$visited[$u] = true;
		$this->time = $this->time + 1;
		$disc[$u] = $this->time;
		$low[$u] = $this->time;
		$children = 0;
		$i = 0;
		$v = 0;
		while ($i < count($this->adjacencylist[$u]))
		{
			$v = $this->adjacencylist[$u][$i];
			if ($visited[$v] == false)
			{
				$parent[$v] = $u;
				$children += 1;
				$this->findDFS($v, $visited, $disc, $low, $parent, $point);
				if (($parent[$u] == -1 && $children > 1) || 
                    ($parent[$u] != -1 && $low[$v] >= $disc[$u]))
				{
					// When u is Articulation point
					$point[$u] = true;
				}
				$low[$u] = $this->min($low[$u], $low[$v]);
			}
			else if ($v != $parent[$u])
			{
				$low[$u] = $this->min($low[$u], $disc[$v]);
			}
			$i++;
		}
	}
	public	function findArticulationPoints()
	{
		// Define some auxiliary variable which is store managing 
		// execution process
		$disc = array_fill(0, $this->vertices, 0);
		$low = array_fill(0, $this->vertices, 0);
		$parent = array_fill(0, $this->vertices, -1);
		// Dicating status of node visited
		$visited = array_fill(0, $this->vertices, false);
		// Indicates the information of articulation point in graph
		$point = array_fill(0, $this->vertices, false);
		// Reset time in new case 
		$this->time = 0;
		// Perform dfs operation
		for ($i = 0; $i < $this->vertices; ++$i)
		{
			if ($visited[$i] == false)
			{
				$this->findDFS($i, $visited, $disc, $low, $parent, $point);
			}
		}
		// Resultat indicator
		$result = false;
		echo("\n Articulation points : ");
		for ($i = 0; $i < $this->vertices; ++$i)
		{
			if ($point[$i] == true)
			{
				// When i is articulation point
				$result = true;
				echo(" ".$i);
			}
		}
		if ($result == false)
		{
			echo(" None \n");
		}
	}
	// Display graph nodes and edges
	public	function printGraph()
	{
		echo("\n Graph Adjacency List ");
		for ($i = 0; $i < $this->vertices; ++$i)
		{
			echo(" \n [".$i.
				"] :");
			// iterate edges of i node
			for ($j = 0; $j < count($this->adjacencylist[$i]); $j++)
			{
				echo("  ".$this->adjacencylist[$i][$j]);
			}
		}
	}
}

function main()
{
	$g = new Graph(10);
	// Connect node with edges
	$g->addEdge(0, 1);
	$g->addEdge(0, 3);
	$g->addEdge(0, 7);
	$g->addEdge(1, 2);
	$g->addEdge(1, 5);
	$g->addEdge(2, 3);
	$g->addEdge(2, 4);
	$g->addEdge(3, 8);
	$g->addEdge(4, 5);
	$g->addEdge(4, 6);
	$g->addEdge(7, 9);
	// Display graph
	$g->printGraph();
	// find articulation point
	$g->findArticulationPoints();
}
main();

input

 Graph Adjacency List
 [0] :  1  3  7
 [1] :  0  2  5
 [2] :  1  3  4
 [3] :  0  2  8
 [4] :  2  5  6
 [5] :  1  4
 [6] :  4
 [7] :  0  9
 [8] :  3
 [9] :  7
 Articulation points :  0 3 4 7
/*
    Node JS program for
    Articulation points in a graph
*/
class Graph
{
	constructor(vertices)
	{
		this.vertices = vertices;
		this.adjacencylist = [];
		this.time = 0;
		for (var i = 0; i < this.vertices; ++i)
		{
			this.adjacencylist.push([]);
		}
	}
	// Connect two node with new edge
	addEdge(u, v)
	{
		if (u >= this.vertices || v >= this.vertices || v < 0 || u < 0)
		{
			//  invalid node
			return;
		}
		// First edge from  (u to v)
		this.adjacencylist[u].push(v);
		if (u == v)
		{
			// Self loop
			return;
		}
		// Second edge from  (v to u)
		this.adjacencylist[v].push(u);
	}
	min(a, b)
	{
		if (a < b)
		{
			return a;
		}
		return b;
	}
	findDFS(u, visited, disc, low, parent, point)
	{
		visited[u] = true;
		this.time = this.time + 1;
		disc[u] = this.time;
		low[u] = this.time;
		var children = 0;
		var i = 0;
		var v = 0;
		while (i < this.adjacencylist[u].length)
		{
			v = this.adjacencylist[u][i];
			if (visited[v] == false)
			{
				parent[v] = u;
				children += 1;
				this.findDFS(v, visited, disc, low, parent, point);
				if ((parent[u] == -1 && children > 1) 
                    || (parent[u] != -1 && low[v] >= disc[u]))
				{
					// When u is Articulation point
					point[u] = true;
				}
				low[u] = this.min(low[u], low[v]);
			}
			else if (v != parent[u])
			{
				low[u] = this.min(low[u], disc[v]);
			}
			i++;
		}
	}
	findArticulationPoints()
	{
		// Define some auxiliary variable which is store managing 
		// execution process
		var disc = Array(this.vertices).fill(0);
		var low = Array(this.vertices).fill(0);
		var parent = Array(this.vertices).fill(-1);
		// Dicating status of node visited
		var visited = Array(this.vertices).fill(false);
		// Indicates the information of articulation point in graph
		var point = Array(this.vertices).fill(false);
		// Reset time in new case 
		this.time = 0;
		// Perform dfs operation
		for (var i = 0; i < this.vertices; ++i)
		{
			if (visited[i] == false)
			{
				this.findDFS(i, visited, disc, low, parent, point);
			}
		}
		// Resultat indicator
		var result = false;
		process.stdout.write("\n Articulation points : ");
		for (var i = 0; i < this.vertices; ++i)
		{
			if (point[i] == true)
			{
				// When i is articulation point
				result = true;
				process.stdout.write(" " + i);
			}
		}
		if (result == false)
		{
			process.stdout.write(" None \n");
		}
	}
	// Display graph nodes and edges
	printGraph()
	{
		process.stdout.write("\n Graph Adjacency List ");
		for (var i = 0; i < this.vertices; ++i)
		{
			process.stdout.write(" \n [" + i + "] :");
			// iterate edges of i node
			for (var j = 0; j < this.adjacencylist[i].length; j++)
			{
				process.stdout.write("  " + this.adjacencylist[i][j]);
			}
		}
	}
}

function main()
{
	var g = new Graph(10);
	// Connect node with edges
	g.addEdge(0, 1);
	g.addEdge(0, 3);
	g.addEdge(0, 7);
	g.addEdge(1, 2);
	g.addEdge(1, 5);
	g.addEdge(2, 3);
	g.addEdge(2, 4);
	g.addEdge(3, 8);
	g.addEdge(4, 5);
	g.addEdge(4, 6);
	g.addEdge(7, 9);
	// Display graph
	g.printGraph();
	// find articulation point
	g.findArticulationPoints();
}
main();

input

 Graph Adjacency List
 [0] :  1  3  7
 [1] :  0  2  5
 [2] :  1  3  4
 [3] :  0  2  8
 [4] :  2  5  6
 [5] :  1  4
 [6] :  4
 [7] :  0  9
 [8] :  3
 [9] :  7
 Articulation points :  0 3 4 7
#    Python 3 program for
#    Articulation points in a graph
class Graph :
	def __init__(self, vertices) :
		self.vertices = vertices
		self.adjacencylist = []
		self.time = 0
		i = 0
		while (i < self.vertices) :
			self.adjacencylist.append([])
			i += 1
		
	
	#  Connect two node with new edge
	def addEdge(self, u, v) :
		if (u >= self.vertices or v >= self.vertices or v < 0 or u < 0) :
			#   invalid node
			return
		
		#  First edge from  (u to v)
		self.adjacencylist[u].append(v)
		if (u == v) :
			#  Self loop
			return
		
		#  Second edge from  (v to u)
		self.adjacencylist[v].append(u)
	
	def min(self, a, b) :
		if (a < b) :
			return a
		
		return b
	
	def findDFS(self, u, visited, disc, low, parent, point) :
		visited[u] = True
		self.time = self.time + 1
		disc[u] = self.time
		low[u] = self.time
		children = 0
		i = 0
		v = 0
		while (i < len(self.adjacencylist[u])) :
			v = self.adjacencylist[u][i]
			if (visited[v] == False) :
				parent[v] = u
				children += 1
				self.findDFS(v, visited, disc, low, parent, point)
				if ((parent[u] == -1 and children > 1) or
                    (parent[u] != -1 and low[v] >= disc[u])) :
					#  When u is Articulation point
					point[u] = True
				
				low[u] = self.min(low[u], low[v])
			elif (v != parent[u]) :
				low[u] = self.min(low[u], disc[v])
			
			i += 1
		
	
	def findArticulationPoints(self) :
		#  Define some auxiliary variable which is store managing 
		#  execution process
		disc = [0] * (self.vertices)
		low = [0] * (self.vertices)
		parent = [0] * (self.vertices)
		#  Dicating status of node visited
		visited = [False] * (self.vertices)
		#  Indicates the information of articulation point in graph
		point = [False] * (self.vertices)
		#  Reset time in new case 
		self.time = 0
		i = 0
		#  Set default value
		while (i < self.vertices) :
			visited[i] = False
			parent[i] = -1
			point[i] = False
			i += 1
		
		i = 0
		#  Perform dfs operation
		while (i < self.vertices) :
			if (visited[i] == False) :
				self.findDFS(i, visited, disc, low, parent, point)
			
			i += 1
		
		#  Resultat indicator
		result = False
		print("\n Articulation points : ", end = "")
		i = 0
		while (i < self.vertices) :
			if (point[i] == True) :
				#  When i is articulation point
				result = True
				print(" ", i, end = "")
			
			i += 1
		
		if (result == False) :
			print(" None ")
		
	
	#  Display graph nodes and edges
	def printGraph(self) :
		print("\n Graph Adjacency List ", end = "")
		i = 0
		while (i < self.vertices) :
			print(" \n [", i ,"] :", end = "")
			j = 0
			#  iterate edges of i node
			while (j < len(self.adjacencylist[i])) :
				print("  ", self.adjacencylist[i][j], end = "")
				j += 1
			
			i += 1
		
	

def main() :
	g = Graph(10)
	#  Connect node with edges
	g.addEdge(0, 1)
	g.addEdge(0, 3)
	g.addEdge(0, 7)
	g.addEdge(1, 2)
	g.addEdge(1, 5)
	g.addEdge(2, 3)
	g.addEdge(2, 4)
	g.addEdge(3, 8)
	g.addEdge(4, 5)
	g.addEdge(4, 6)
	g.addEdge(7, 9)
	#  Display graph
	g.printGraph()
	#  find articulation point
	g.findArticulationPoints()

if __name__ == "__main__": main()

input

 Graph Adjacency List
 [ 0 ] :   1   3   7
 [ 1 ] :   0   2   5
 [ 2 ] :   1   3   4
 [ 3 ] :   0   2   8
 [ 4 ] :   2   5   6
 [ 5 ] :   1   4
 [ 6 ] :   4
 [ 7 ] :   0   9
 [ 8 ] :   3
 [ 9 ] :   7
 Articulation points :   0  3  4  7
#    Ruby program for
#    Articulation points in a graph
class Graph 
	# Define the accessor and reader of class Graph
	attr_reader :vertices, :adjacencylist, :time
	attr_accessor :vertices, :adjacencylist, :time
	def initialize(vertices) 
		self.vertices = vertices
		self.adjacencylist = []
		self.time = 0
		i = 0
		while (i < self.vertices) 
			self.adjacencylist.push([])
			i += 1
		end

	end

	#  Connect two node with new edge
	def addEdge(u, v) 
		if (u >= self.vertices || v >= self.vertices || v < 0 || u < 0) 
			#   invalid node
			return
		end

		#  First edge from  (u to v)
		self.adjacencylist[u].push(v)
		if (u == v) 
			#  Self loop
			return
		end

		#  Second edge from  (v to u)
		self.adjacencylist[v].push(u)
	end

	def min(a, b) 
		if (a < b) 
			return a
		end

		return b
	end

	def findDFS(u, visited, disc, low, parent, point) 
		visited[u] = true
		self.time = self.time + 1
		disc[u] = self.time
		low[u] = self.time
		children = 0
		i = 0
		v = 0
		while (i < self.adjacencylist[u].length) 
			v = self.adjacencylist[u][i]
			if (visited[v] == false) 
				parent[v] = u
				children += 1
				self.findDFS(v, visited, disc, low, parent, point)
				if ((parent[u] == -1 && children > 1) || (parent[u] != -1 &&
                                                          low[v] >= disc[u])) 
					#  When u is Articulation point
					point[u] = true
				end

				low[u] = self.min(low[u], low[v])
			elsif (v != parent[u]) 
				low[u] = self.min(low[u], disc[v])
			end

			i += 1
		end

	end

	def findArticulationPoints() 
		#  Define some auxiliary variable which is store managing 
		#  execution process
		disc = Array.new(self.vertices) {0}
		low = Array.new(self.vertices) {0}
		parent = Array.new(self.vertices) {0}
		#  Dicating status of node visited
		visited = Array.new(self.vertices) {false}
		#  Indicates the information of articulation point in graph
		point = Array.new(self.vertices) {false}
		#  Reset time in new case 
		self.time = 0
		i = 0
		#  Set default value
		while (i < self.vertices) 
			visited[i] = false
			parent[i] = -1
			point[i] = false
			i += 1
		end

		i = 0
		#  Perform dfs operation
		while (i < self.vertices) 
			if (visited[i] == false) 
				self.findDFS(i, visited, disc, low, parent, point)
			end

			i += 1
		end

		#  Resultat indicator
		result = false
		print("\n Articulation points : ")
		i = 0
		while (i < self.vertices) 
			if (point[i] == true) 
				#  When i is articulation point
				result = true
				print(" ", i)
			end

			i += 1
		end

		if (result == false) 
			print(" None \n")
		end

	end

	#  Display graph nodes and edges
	def printGraph() 
		print("\n Graph Adjacency List ")
		i = 0
		while (i < self.vertices) 
			print(" \n [", i ,"] :")
			j = 0
			#  iterate edges of i node
			while (j < self.adjacencylist[i].length) 
				print("  ", self.adjacencylist[i][j])
				j += 1
			end

			i += 1
		end

	end

end

def main() 
	g = Graph.new(10)
	#  Connect node with edges
	g.addEdge(0, 1)
	g.addEdge(0, 3)
	g.addEdge(0, 7)
	g.addEdge(1, 2)
	g.addEdge(1, 5)
	g.addEdge(2, 3)
	g.addEdge(2, 4)
	g.addEdge(3, 8)
	g.addEdge(4, 5)
	g.addEdge(4, 6)
	g.addEdge(7, 9)
	#  Display graph
	g.printGraph()
	#  find articulation point
	g.findArticulationPoints()
end

main()

input

 Graph Adjacency List  
 [0] :  1  3  7 
 [1] :  0  2  5 
 [2] :  1  3  4 
 [3] :  0  2  8 
 [4] :  2  5  6 
 [5] :  1  4 
 [6] :  4 
 [7] :  0  9 
 [8] :  3 
 [9] :  7
 Articulation points :  0 3 4 7
import scala.collection.mutable._;
/*
    Scala program for
    Articulation points in a graph
*/
class Graph(var vertices: Int,
	var adjacencylist: ArrayBuffer[ArrayBuffer[Int]],
		var time: Int)
{
	def this(vertices: Int)
	{
		this(vertices,new ArrayBuffer[ArrayBuffer[Int]](vertices), 0);
		var i: Int = 0;
		while (i < this.vertices)
		{
			this.adjacencylist += new ArrayBuffer[Int]();
			i += 1;
		}
	}
	// Connect two node with new edge
	def addEdge(u: Int, v: Int): Unit = {
		if (u >= this.vertices || v >= this.vertices || v < 0 || u < 0)
		{
			//  invalid node
			return;
		}
		// First edge from  (u to v)
		adjacencylist(u) += v;
		if (u == v)
		{
			// Self loop
			return;
		}
		// Second edge from  (v to u)
		adjacencylist(v) += u;
	}
	def min(a: Int, b: Int): Int = {
		if (a < b)
		{
			return a;
		}
		return b;
	}
	def findDFS(u: Int, visited: Array[Boolean], disc: Array[Int], low: Array[Int], parent: Array[Int], point: Array[Boolean]): Unit = {
		visited(u) = true;
		this.time = this.time + 1;
		disc(u) = this.time;
		low(u) = this.time;
		var children: Int = 0;
		var i: Int = 0;
		var v: Int = 0;
		while (i < adjacencylist(u).size)
		{
			v = adjacencylist(u)(i);
			if (visited(v) == false)
			{
				parent(v) = u;
				children += 1;
				findDFS(v, visited, disc, low, parent, point);
				if ((parent(u) == -1 && children > 1) || (parent(u) != -1 && low(v) >= disc(u)))
				{
					// When u is Articulation point
					point(u) = true;
				}
				low(u) = min(low(u), low(v));
			}
			else if (v != parent(u))
			{
				low(u) = min(low(u), disc(v));
			}
			i += 1;
		}
	}
	def findArticulationPoints(): Unit = {
		// Define some auxiliary variable which is store managing 
		// execution process
		var disc: Array[Int] = Array.fill[Int](this.vertices)(0);
		var low: Array[Int] = Array.fill[Int](this.vertices)(0);
		var parent: Array[Int] = Array.fill[Int](this.vertices)(-1);
		// Dicating status of node visited
		var visited: Array[Boolean] = Array.fill[Boolean](this.vertices)(false);
		// Indicates the information of articulation point in graph
		var point: Array[Boolean] = Array.fill[Boolean](this.vertices)(false);
		// Reset time in new case 
		this.time = 0;
		var i: Int = 0;
		// Perform dfs operation
		while (i < this.vertices)
		{
			if (visited(i) == false)
			{
				findDFS(i, visited, disc, low, parent, point);
			}
			i += 1;
		}
		// Resultat indicator
		var result: Boolean = false;
		print("\n Articulation points : ");
		i = 0;
		while (i < this.vertices)
		{
			if (point(i) == true)
			{
				// When i is articulation point
				result = true;
				print(" " + i);
			}
			i += 1;
		}
		if (result == false)
		{
			print(" None \n");
		}
	}
	// Display graph nodes and edges
	def printGraph(): Unit = {
		print("\n Graph Adjacency List ");
		var i: Int = 0;
		while (i < this.vertices)
		{
			print(" \n [" + i + "] :");
			var j: Int = 0;
			// iterate edges of i node
			while (j < this.adjacencylist(i).size)
			{
				print("  " + this.adjacencylist(i)(j));
				j += 1;
			}
			i += 1;
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var g: Graph = new Graph(10);
		// Connect node with edges
		g.addEdge(0, 1);
		g.addEdge(0, 3);
		g.addEdge(0, 7);
		g.addEdge(1, 2);
		g.addEdge(1, 5);
		g.addEdge(2, 3);
		g.addEdge(2, 4);
		g.addEdge(3, 8);
		g.addEdge(4, 5);
		g.addEdge(4, 6);
		g.addEdge(7, 9);
		// Display graph
		g.printGraph();
		// find articulation point
		g.findArticulationPoints();
	}
}

input

 Graph Adjacency List
 [0] :  1  3  7
 [1] :  0  2  5
 [2] :  1  3  4
 [3] :  0  2  8
 [4] :  2  5  6
 [5] :  1  4
 [6] :  4
 [7] :  0  9
 [8] :  3
 [9] :  7
 Articulation points :  0 3 4 7
import Foundation;
/*
    Swift 4 program for
    Articulation points in a graph
*/
class Graph
{
	var vertices: Int;
	var adjacencylist: [[Int]];
	var time: Int;
	init(_ vertices: Int)
	{
		self.vertices = vertices;
		self.adjacencylist = [[Int]]();
		self.time = 0;
		var i: Int = 0;
		while (i < self.vertices)
		{
			self.adjacencylist.append([Int]());
			i += 1;
		}
	}
	// Connect two node with new edge
	func addEdge(_ u: Int, _ v: Int)
	{
		if (u >= self.vertices || v >= self.vertices || v < 0 || u < 0)
		{
			//  invalid node
			return;
		}
		// First edge from  (u to v)
		self.adjacencylist[u].append(v);
		if (u == v)
		{
			// Self loop
			return;
		}
		// Second edge from  (v to u)
		self.adjacencylist[v].append(u);
	}
	func min(_ a: Int, _ b: Int) -> Int
	{
		if (a < b)
		{
			return a;
		}
		return b;
	}
	func findDFS(_ u: Int, _ visited: inout[Bool], 
      _ disc: inout[Int], _ low: inout[Int], 
        _ parent: inout[Int], _ point: inout[Bool])
	{
		visited[u] = true;
		self.time = self.time + 1;
		disc[u] = self.time;
		low[u] = self.time;
		var children: Int = 0;
		var i: Int = 0;
		var v: Int = 0;
		while (i < self.adjacencylist[u].count)
		{
			v = self.adjacencylist[u][i];
			if (visited[v] == false)
			{
				parent[v] = u;
				children += 1;
				self.findDFS(v, &visited, &disc, &low, &parent, &point);
				if ((parent[u] == -1 && children > 1) || 
                    (parent[u]  != -1 && low[v] >= disc[u]))
				{
					// When u is Articulation point
					point[u] = true;
				}
				low[u] = self.min(low[u], low[v]);
			}
			else if (v  != parent[u])
			{
				low[u] = self.min(low[u], disc[v]);
			}
			i += 1;
		}
	}
	func findArticulationPoints()
	{
		// Define some auxiliary variable which is store managing 
		// execution process
		var disc: [Int] = Array(repeating: 0, count: self.vertices);
		var low: [Int] = Array(repeating: 0, count: self.vertices);
		var parent: [Int] = Array(repeating: -1, count: self.vertices);
		// Dicating status of node visited
		var visited: [Bool] = Array(repeating: false, count: self.vertices);
		// Indicates the information of articulation point in graph
		var point: [Bool] = Array(repeating: false, count: self.vertices);
		// Reset time in new case 
		self.time = 0;
	
		var i: Int = 0;
		// Perform dfs operation
		while (i < self.vertices)
		{
			if (visited[i] == false)
			{
				self.findDFS(i, &visited, &disc, &low, &parent, &point);
			}
			i += 1;
		}
		// Resultat indicator
		var result: Bool = false;
		print("\n Articulation points : ", terminator: "");
		i = 0;
		while (i < self.vertices)
		{
			if (point[i] == true)
			{
				// When i is articulation point
				result = true;
				print(" ", i, terminator: "");
			}
			i += 1;
		}
		if (result == false)
		{
			print(" None ");
		}
	}
	// Display graph nodes and edges
	func printGraph()
	{
		print("\n Graph Adjacency List ", terminator: "");
		var i: Int = 0;
		while (i < self.vertices)
		{
			print(" \n [", i ,"] :", terminator: "");
			var j: Int = 0;
			// iterate edges of i node
			while (j < self.adjacencylist[i].count)
			{
				print("  ", self.adjacencylist[i][j], terminator: "");
				j += 1;
			}
			i += 1;
		}
	}
}
func main()
{
	let g: Graph = Graph(10);
	// Connect node with edges
	g.addEdge(0, 1);
	g.addEdge(0, 3);
	g.addEdge(0, 7);
	g.addEdge(1, 2);
	g.addEdge(1, 5);
	g.addEdge(2, 3);
	g.addEdge(2, 4);
	g.addEdge(3, 8);
	g.addEdge(4, 5);
	g.addEdge(4, 6);
	g.addEdge(7, 9);
	// Display graph
	g.printGraph();
	// find articulation point
	g.findArticulationPoints();
}
main();

input

 Graph Adjacency List
 [ 0 ] :   1   3   7
 [ 1 ] :   0   2   5
 [ 2 ] :   1   3   4
 [ 3 ] :   0   2   8
 [ 4 ] :   2   5   6
 [ 5 ] :   1   4
 [ 6 ] :   4
 [ 7 ] :   0   9
 [ 8 ] :   3
 [ 9 ] :   7
 Articulation points :   0  3  4  7
/*
    Kotlin program for
    Articulation points in a graph
*/
class Graph
{
	var vertices: Int;
	var adjacencylist: MutableList < MutableList < Int >> ;
	var time: Int;
	constructor(vertices: Int)
	{
		this.vertices = vertices;
		this.adjacencylist = mutableListOf<MutableList<Int>>();
		this.time = 0;
		var i: Int = 0;
		while (i < this.vertices)
		{
			this.adjacencylist.add(mutableListOf < Int > ());
			i += 1;
		}
	}
	// Connect two node with new edge
	fun addEdge(u: Int, v: Int): Unit
	{
		if (u >= this.vertices || v >= this.vertices || v < 0 || u < 0)
		{
			//  invalid node
			return;
		}
		// First edge from  (u to v)
		this.adjacencylist[u].add(v);
		if (u == v)
		{
			// Self loop
			return;
		}
		// Second edge from  (v to u)
		this.adjacencylist[v].add(u);
	}
	fun min(a: Int, b: Int): Int
	{
		if (a < b)
		{
			return a;
		}
		return b;
	}
	fun findDFS(u: Int, visited: Array < Boolean > , 
                disc: Array < Int > , low: Array < Int > , 
                parent: Array < Int > , point: Array < Boolean > ): Unit
	{
		visited[u] = true;
		this.time = this.time + 1;
		disc[u] = this.time;
		low[u] = this.time;
		var children: Int = 0;
		var i: Int = 0;
		var v: Int ;
		while (i < this.adjacencylist[u].size)
		{
			v = this.adjacencylist[u][i];
			if (visited[v] == false)
			{
				parent[v] = u;
				children += 1;
				this.findDFS(v, visited, disc, low, parent, point);
				if ((parent[u] == -1 && children > 1) || 
                    (parent[u] != -1 && low[v] >= disc[u]))
				{
					// When u is Articulation point
					point[u] = true;
				}
				low[u] = this.min(low[u], low[v]);
			}
			else if (v != parent[u])
			{
				low[u] = this.min(low[u], disc[v]);
			}
			i += 1;
		}
	}
	fun findArticulationPoints(): Unit
	{
		// Define some auxiliary variable which is store managing 
		// execution process
		val disc: Array < Int > = Array(this.vertices)
		{
			0
		};
		val low: Array < Int > = Array(this.vertices)
		{
			0
		};
		val parent: Array < Int > = Array(this.vertices)
		{
			-1
		};
		// Dicating status of node visited
		val visited: Array < Boolean > = Array(this.vertices)
		{
			false
		};
		// Indicates the information of articulation point in graph
		val point: Array < Boolean > = Array(this.vertices)
		{
			false
		};
		// Reset time in new case 
		this.time = 0;
	
		var i: Int = 0;
		// Perform dfs operation
		while (i < this.vertices)
		{
			if (visited[i] == false)
			{
				this.findDFS(i, visited, disc, low, parent, point);
			}
			i += 1;
		}
		// Resultat indicator
		var result: Boolean = false;
		print("\n Articulation points : ");
		i = 0;
		while (i < this.vertices)
		{
			if (point[i] == true)
			{
				// When i is articulation point
				result = true;
				print(" " + i);
			}
			i += 1;
		}
		if (result == false)
		{
			print(" None \n");
		}
	}
	// Display graph nodes and edges
	fun printGraph(): Unit
	{
		print("\n Graph Adjacency List ");
		var i: Int = 0;
		while (i < this.vertices)
		{
			print(" \n [" + i + "] :");
			var j: Int = 0;
			// iterate edges of i node
			while (j < this.adjacencylist[i].size)
			{
				print("  " + this.adjacencylist[i][j]);
				j += 1;
			}
			i += 1;
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val g: Graph = Graph(10);
	// Connect node with edges
	g.addEdge(0, 1);
	g.addEdge(0, 3);
	g.addEdge(0, 7);
	g.addEdge(1, 2);
	g.addEdge(1, 5);
	g.addEdge(2, 3);
	g.addEdge(2, 4);
	g.addEdge(3, 8);
	g.addEdge(4, 5);
	g.addEdge(4, 6);
	g.addEdge(7, 9);
	// Display graph
	g.printGraph();
	// find articulation point
	g.findArticulationPoints();
}

input

 Graph Adjacency List
 [0] :  1  3  7
 [1] :  0  2  5
 [2] :  1  3  4
 [3] :  0  2  8
 [4] :  2  5  6
 [5] :  1  4
 [6] :  4
 [7] :  0  9
 [8] :  3
 [9] :  7
 Articulation points :  0 3 4 7
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment