Posted on by Kalkicode
Code Graph

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

Articulation point example in graph

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

  1. The findDFS function performs DFS traversal and identifies articulation points using low discovery time and parent information.
  2. The findArticulationPoints function initializes arrays and iterates through each vertex, invoking DFS on unvisited vertices.
  3. 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.

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





Categories
Relative Post