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.

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