Articulation points in a graph
The problem you're addressing is about finding articulation points in a given undirected graph. An articulation point is a vertex in the graph whose removal would increase the number of connected components. In other words, if you remove an articulation point from the graph, the graph becomes disconnected or has more connected components than before. Your goal is to create a program that identifies and outputs the articulation points in the graph.
Problem Statement and Example
Given an undirected graph with vertices and edges, you want to identify and output the articulation points in the graph. For example, consider the following graph:
Vertices: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Edges: (0,1), (0,3), (0,7), (1,2), (1,5), (2,3), (2,4), (3,8), (4,5), (4,6), (7,9)
You need to find and output the articulation points in this graph.
Idea to Solve

To solve this problem, you can use Depth-First Search (DFS) traversal and low discovery time to identify articulation points. The low value of a vertex 'v' represents the earliest visited vertex reachable from the subtree rooted at 'v'. If 'low[v] >= disc[u]', where 'u' is the parent of 'v', then 'u' is an articulation point.
Pseudocode
function findDFS(u, visited, disc, low, parent, point)
mark u as visited
increment time
assign disc[u] and low[u] to current time
initialize children as 0
for each neighbor v of u
if v is not visited
set parent[v] as u
increment children
perform findDFS(v, visited, disc, low, parent, point)
if (u is root and children > 1) or (u is not root and low[v] >= disc[u])
set point[u] as true
assign low[u] as minimum of low[u] and low[v]
else if v is not parent[u]
assign low[u] as minimum of low[u] and disc[v]
function findArticulationPoints()
initialize visited, disc, low, parent, point arrays
mark all vertices as not visited
initialize result as false
for each vertex u
if u is not visited
perform findDFS(u, visited, disc, low, parent, point)
print articulation points
Algorithm Explanation
- The
findDFS
function performs DFS traversal and identifies articulation points using low discovery time and parent information. - The
findArticulationPoints
function initializes arrays and iterates through each vertex, invoking DFS on unvisited vertices. - If a vertex satisfies the articulation point condition, it's marked as an articulation point.
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
Time Complexity
The time complexity of the algorithm depends on the number of vertices and edges in the graph. The DFS traversal has a time complexity of O(V + E), where 'V' is the number of vertices and 'E' is the number of edges. The loop that iterates through each vertex contributes O(V) to the time complexity.
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