Check if graph is strongly connected or not
Determining whether a directed graph is strongly connected or not is a crucial problem in graph theory. A strongly connected graph is one in which there is a directed path between any two vertices. In contrast, if a graph is not strongly connected, it means there are vertices that cannot be reached from some other vertices. This article delves into the concept of checking the strong connectivity of a graph and presents a detailed explanation of how to implement this in code.
Problem Statement and Description
Given a directed graph represented using an adjacency list, the task is to determine whether the graph is strongly connected or not. A graph is strongly connected if, for every pair of vertices (u, v), there is a directed path from u to v and from v to u. In other words, it is possible to reach any vertex from any other vertex in the graph.
Example
Consider two examples of directed graphs:
- A strongly connected graph:
0 -> 4
1 -> 0, 2
2 -> 1, 4
3 -> 1, 2
4 -> 3
In this case, the graph is strongly connected because every vertex can be reached from any other vertex.
- A not strongly connected graph:
0 -> 1, 5
1 -> 2
2 -> 3
3 -> 4
4 -> 1
5 -> 2, 4
This graph is not strongly connected because there is no directed path from vertices 3 and 4 to any other vertices.
Idea to Solve the Problem
To check if a graph is strongly connected, we need to perform depth-first searches (DFS) from each vertex in the graph. If DFS can reach all other vertices starting from a given vertex and also from those vertices to the starting vertex, then the graph is strongly connected. In other words, we check if each vertex can reach all other vertices and be reached by them as well.
Pseudocode
Here's the pseudocode for checking if a graph is strongly connected:
procedure CheckStrongConnectivity(graph):
for each vertex in graph:
result = DFS_FromVertex(vertex)
if result == false:
print("Not Strongly Connected Graph")
return
print("Strongly Connected Graph")
procedure DFS_FromVertex(start):
# Initialize visited array
initialize visit array with 0
# Perform DFS to mark reachable vertices
dfs(start, visit)
# If any vertex is unvisited, return false
for each vertex in graph:
if visit[vertex] == 0:
return false
# Reset visited array and perform DFS again
reset visit array to 0
dfs(start, visit)
# If any vertex is unvisited, return false
for each vertex in graph:
if visit[vertex] == 0:
return false
return true
procedure DFS(start, visit):
mark start as visited
for each adjacent_vertex of start:
if adjacent_vertex is not visited:
DFS(adjacent_vertex, visit)
Algorithm Explanation
- For each vertex in the graph:
a. Perform a DFS to mark all vertices that can be reached from the current vertex.
b. If any vertex remains unvisited after the DFS, return
false
. - Reset the visited array.
- Perform DFS again from the same vertex.
- If any vertex is unvisited, return
false
. - If all vertices are visited, return
true
.
Code Solution
//C Program
//Check if graph is strongly connected or not
#include<stdio.h>
#include<stdlib.h>
struct AjlistNode {
int vId; //Vertices id
struct AjlistNode *next;
};
struct Graph {
int data; //node key value
struct AjlistNode *next;
};
int size; //number of nodes
//set node key value
void set_data(struct Graph *node) {
if (node != NULL && size > 0) {
int index = 0;
for (index; index < size; index++) {
//set vertic node data
node[index].data = index; //set node key
//Initial no AjlistNode
//set NULL Value
node[index].next = NULL;
}
} else {
printf("Vertic Node is Empty");
}
}
//Add Edge from Two given Nodes
void add_edge(struct Graph *node, int V, int E) {
//add edge form V to E
//V and E is Node location
if (V < size && E < size) {
//first create Adjacency node
struct AjlistNode *newEdge = (struct AjlistNode *) malloc(sizeof(struct AjlistNode));
if (newEdge != NULL) {
newEdge->next = NULL;
newEdge->vId = E;
struct AjlistNode *temp = node[V].next;
if (temp == NULL) {
node[V].next = newEdge;
} else {
//Add node at last
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newEdge;
}
} else {
printf("\n Memory overflow");
}
} else {
//not valid Vertices
printf("Invalid Node Vertices %d %d", V, E);
}
}
//Display Adjacency list of vertex
void print_graph(struct Graph *node) {
if (node != NULL) {
struct AjlistNode *temp = NULL;
for (int index = 0; index < size; index++) {
printf("\n Adjacency list of vertex %d :", index);
temp = node[index].next;
while (temp != NULL) {
//temp->vId is graph node vertices
//in this case temp->vId is same as
//node[temp->vId].data
printf(" %d", node[temp->vId].data);
temp = temp->next;
}
}
} else {
printf("Empty Graph");
}
}
void dfs(int start, int *visit, struct Graph *node) {
if (start > size || start < 0 || node == NULL) {
//invalid input
return;
}
if (visit[start] == 1) {
return;
}
visit[start] = 1;
struct AjlistNode *temp = node[start].next;
while (temp != NULL) {
dfs(temp->vId, visit, node);
temp = temp->next;
}
}
//Get the path information of given node
void path(int start, int *visit, struct Graph *node) {
if (start > size || start < 0 || node == NULL) {
//invalid input
return;
}
if (visit[start] != 1) {
visit[start] = 1;
struct AjlistNode *temp = node[start].next;
while (temp != NULL) {
path(temp->vId, visit, node);
temp = temp->next;
}
}
}
void reset_path(int visit[])
{
//reset value
for(int j = 0 ; j < size; j++)
{
visit[j] = 0;
}
}
int visited_status(int visit[])
{
//reset value
for(int j = 0 ; j < size; j++)
{
if(visit[j] == 0)
{
return 0;
}
}
return 1;
}
void connection(struct Graph *node) {
int result = 1;
int visit[size];
for (int i = 1; i < size && result == 1; ++i) {
result = 0;
reset_path(visit);
path(i, visit, node);
if(visited_status(visit)==1)
{
result = 1;
}
}
if (result == 1) {
printf("\n Strongly Connected Graph\n");
} else {
printf("\n Not Strongly Connected Graph\n");
}
}
int main() {
size = 5;
struct Graph *g1 = NULL;
struct Graph *g2 = NULL;
g1 = (struct Graph *) malloc(sizeof(struct Graph) *size);
if (g1 == NULL)
{
printf("\n Memory overflow");
}
else
{
printf("First Graph ");
//First set node keys
set_data(g1);
//Connected two node with Edges
add_edge(g1, 0, 4);
add_edge(g1, 1, 0);
add_edge(g1, 1, 2);
add_edge(g1, 2, 1);
add_edge(g1, 2, 4);
add_edge(g1, 3, 1);
add_edge(g1, 3, 2);
add_edge(g1, 4, 3);
print_graph(g1);
connection(g1);
}
//Case 2
size = 6;
g2 = (struct Graph *) malloc(sizeof(struct Graph) *size);
if (g2 == NULL)
{
printf("\n Memory overflow");
}
else
{
set_data(g2);
//Connected two node with Edges
add_edge(g2, 0, 1);
add_edge(g2, 0, 5);
add_edge(g2, 1, 2);
add_edge(g2, 2, 3);
add_edge(g2, 3, 4);
add_edge(g2, 4, 1);
add_edge(g2, 5, 2);
add_edge(g2, 5, 4);
printf("\nSecond Graph ");
print_graph(g2);
connection(g2);
}
return 0;
}
Output
First Graph
Adjacency list of vertex 0 : 4
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 : 1 4
Adjacency list of vertex 3 : 1 2
Adjacency list of vertex 4 : 3
Strongly Connected Graph
Second Graph
Adjacency list of vertex 0 : 1 5
Adjacency list of vertex 1 : 2
Adjacency list of vertex 2 : 3
Adjacency list of vertex 3 : 4
Adjacency list of vertex 4 : 1
Adjacency list of vertex 5 : 2 4
Not Strongly Connected Graph
// C++ program
// Check if graph is strongly connected or not
#include<iostream>
using namespace std;
class AjlistNode {
public:
//Vertices node key
int id;
AjlistNode *next;
AjlistNode(int id) {
//Set value of node key
this->id = id;
this->next = NULL;
}
};
class Vertices {
public:
int data;
AjlistNode *next;
Vertices()
{
this->data = 0;
this->next = NULL;
}
Vertices(int data) {
this->data = data;
this->next = NULL;
}
};
class MyGraph {
public:
//number of Vertices
int size;
Vertices *node;
bool result;
MyGraph(int size) {
this->size = size;
this->result = false;
this->node = new Vertices[size];
//set initial values of graph node
this->set_data();
}
//Set initial node value
void set_data() {
if (this->node == NULL) {
cout << "\nEmpty Graph";
} else {
int index = 0;
while (index < this->size) {
this->node[index] = index;
index++;
}
}
}
//Connect two node
void add_edge(int start, int last) {
AjlistNode *newEdge = new AjlistNode(last);
if (this->node[start].next == NULL) {
//Include first adjacency list node of location start
this->node[start].next = newEdge;
} else {
AjlistNode *temp = this->node[start].next;
//Add new node at the last of edge
while (temp->next != NULL) {
temp = temp->next;
}
//Add node
temp->next = newEdge;
}
}
//Display graph elements
void print_graph() {
if (this->size > 0 &&
this->node != NULL) {
int index = 0;
while (index < this->size) {
cout << "\nAdjacency list of vertex " << index << " : ";
AjlistNode *temp = this->node[index].next;
while (temp != NULL) {
cout << this->node[temp->id].data << " ";
temp = temp->next;
}
index++;
}
}
}
void dfs(int start, bool visit[]) {
if (start > this->size ||
start < 0 ||
this->node == NULL) {
//invalid input
return;
}
if (visit[start] == true) {
return;
}
AjlistNode *temp = this->node[start].next;
visit[start] = true;
while (temp != NULL) {
this->dfs(temp->id, visit);
temp = temp->next;
}
}
//Check path between two nodes
void path(int start, bool visit[]) {
if (start > this->size ||
start < 0 ||
this->node == NULL) {
//invalid input
return;
}
if (visit[start] == true) {
return;
}
if (this->result == false) {
visit[start] = true;
AjlistNode *temp = this->node[start].next;
while (temp != NULL) {
this->path(temp->id, visit);
temp = temp->next;
}
}
}
void reset_path(bool visit[]) {
//reset value
for (int j = 0; j < this->size; j++) {
visit[j] = false;
}
}
bool visited_status(bool visit[]) {
//reset value
for (int j = 0; j < this->size; j++) {
if (visit[j] == false) {
return false;
}
}
return true;
}
void connection() {
bool visit[size];
this->result = true;
for (int i = 0; i < this->size &&
this->result == true; ++i) {
this->reset_path(visit);
this->result = false;
this->path(i, visit);
//Check that whether i node are connected to other node
if (this->visited_status(visit) == true) {
this->result = true;
}
}
if (this->result == true) {
cout << "\n Strongly Connected Graph\n";
} else {
cout << "\n Not Strongly Connected Graph\n";
}
}
};
int main() {
MyGraph g1 = MyGraph(5);
//Connected two node with Edges
g1.add_edge(0, 4);
g1.add_edge(1, 0);
g1.add_edge(1, 2);
g1.add_edge(2, 1);
g1.add_edge(2, 4);
g1.add_edge(3, 1);
g1.add_edge(3, 2);
g1.add_edge(4, 3);
cout << "First Graph";
g1.print_graph();
g1.connection();
MyGraph g2 = MyGraph(6);
//Connected two node with Edges
g2.add_edge(0, 1);
g2.add_edge(0, 5);
g2.add_edge(1, 2);
g2.add_edge(2, 2);
g2.add_edge(2, 3);
g2.add_edge(3, 4);
g2.add_edge(4, 1);
g2.add_edge(5, 2);
g2.add_edge(5, 4);
cout << "\nSecond Graph";
g2.print_graph();
g2.connection();
return 0;
}
Output
First Graph
Adjacency list of vertex 0 : 4
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 : 1 4
Adjacency list of vertex 3 : 1 2
Adjacency list of vertex 4 : 3
Strongly Connected Graph
Second Graph
Adjacency list of vertex 0 : 1 5
Adjacency list of vertex 1 : 2
Adjacency list of vertex 2 : 2 3
Adjacency list of vertex 3 : 4
Adjacency list of vertex 4 : 1
Adjacency list of vertex 5 : 2 4
Not Strongly Connected Graph
// Java program
// Check if graph is strongly connected or not
class AjlistNode {
//Vertices node key
public int id;
public AjlistNode next;
public AjlistNode(int id) {
//Set value of node key
this.id = id;
this.next = null;
}
}
class Vertices {
public int data;
public AjlistNode next;
public Vertices(int data) {
this.data = data;
this.next = null;
}
}
public class MyGraph {
//number of Vertices
private int size;
private Vertices[] node;
private boolean result ;
public MyGraph(int size) {
this.size = size;
this.result = false;
this.node = new Vertices[size];
//set initial values of graph node
this.set_data();
}
//Set initial node value
public void set_data() {
if (node == null) {
System.out.println("\nEmpty Graph");
} else {
int index = 0;
while (index < size) {
node[index] = new Vertices(index);
index++;
}
}
}
//Connect two node
public void add_edge(int start, int last) {
AjlistNode newEdge = new AjlistNode(last);
if (node[start].next == null)
{
//Include first adjacency list node of location start
node[start].next = newEdge;
}
else
{
AjlistNode temp = node[start].next;
//Add new node at the last of edge
while (temp.next != null)
{
temp = temp.next;
}
//Add node
temp.next = newEdge;
}
}
//Display graph elements
public void print_graph() {
if (size > 0 && node != null) {
int index = 0;
while (index < size) {
System.out.print("\nAdjacency list of vertex " + index + " : ");
AjlistNode temp = node[index].next;
while (temp != null) {
System.out.print(node[temp.id].data + " ");
temp = temp.next;
}
index++;
}
}
}
public void dfs(int start, boolean []visit) {
if (start > size || start < 0 || node == null) {
//invalid input
return;
}
if (visit[start] == true) {
return;
}
AjlistNode temp = node[start].next;
visit[start] = true;
while (temp != null) {
dfs(temp.id, visit);
temp = temp.next;
}
}
//Check path between two nodes
public void path(int start, boolean []visit) {
if (start > size || start < 0 || node == null) {
//invalid input
return;
}
if (visit[start] == true) {
return;
}
if (this.result == false) {
visit[start] = true;
AjlistNode temp = node[start].next;
while (temp != null) {
path(temp.id, visit);
temp = temp.next;
}
}
}
public void reset_path(boolean []visit)
{
//reset value
for(int j = 0 ; j < this.size; j++)
{
visit[j]=false;
}
}
public boolean visited_status(boolean []visit)
{
//reset value
for(int j = 0 ; j < this.size; j++)
{
if(visit[j]==false)
{
return false;
}
}
return true;
}
public void connection() {
//Auxiliary space which is used to store information about
// node is visit or not
boolean []visit = new boolean[size];
this.result = true;
for (int i = 0; i < size && this.result == true; ++i) {
reset_path(visit);
this.result = false;
this.path(i, visit);
//Check that whether i node are connected to other node
if(visited_status(visit)==true)
{
this.result = true;
}
}
if (this.result == true) {
System.out.print("\n Strongly Connected Graph\n");
} else {
System.out.print("\n Not Strongly Connected Graph\n");
}
}
public static void main(String[] args) {
MyGraph g1 = new MyGraph(5);
//Connected two node with Edges
g1.add_edge(0, 4);
g1.add_edge(1, 0);
g1.add_edge(1, 2);
g1.add_edge(2, 1);
g1.add_edge(2, 4);
g1.add_edge(3, 1);
g1.add_edge(3, 2);
g1.add_edge(4, 3);
System.out.print("First Graph");
g1.print_graph();
g1.connection();
MyGraph g2 = new MyGraph(6);
//Connected two node with Edges
g2.add_edge( 0, 1);
g2.add_edge( 0, 5);
g2.add_edge( 1, 2);
g2.add_edge( 2, 2);
g2.add_edge( 2, 3);
g2.add_edge( 3, 4);
g2.add_edge( 4, 1);
g2.add_edge( 5, 2);
g2.add_edge( 5, 4);
System.out.print("\nSecond Graph");
g2.print_graph();
g2.connection();
}
}
Output
First Graph
Adjacency list of vertex 0 : 4
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 : 1 4
Adjacency list of vertex 3 : 1 2
Adjacency list of vertex 4 : 3
Strongly Connected Graph
Second Graph
Adjacency list of vertex 0 : 1 5
Adjacency list of vertex 1 : 2
Adjacency list of vertex 2 : 2 3
Adjacency list of vertex 3 : 4
Adjacency list of vertex 4 : 1
Adjacency list of vertex 5 : 2 4
Not Strongly Connected Graph
// C# program
// Check if graph is strongly connected or not
using System;
public class AjlistNode {
//Vertices node key
public int id;
public AjlistNode next;
public AjlistNode(int id) {
//Set value of node key
this.id = id;
this.next = null;
}
}
public class Vertices {
public int data;
public AjlistNode next;
public Vertices(int data) {
this.data = data;
this.next = null;
}
}
public class MyGraph {
//number of Vertices
private int size;
private Vertices[] node;
private Boolean result;
public MyGraph(int size) {
this.size = size;
this.result = false;
this.node = new Vertices[size];
this.set_data();
}
//Set initial node value
public void set_data() {
if (node == null) {
Console.WriteLine("\nEmpty Graph");
} else {
int index = 0;
while (index < size) {
node[index] = new Vertices(index);
index++;
}
}
}
//Connect two node
public void add_edge(int start, int last) {
AjlistNode newEdge = new AjlistNode(last);
if (node[start].next == null) {
//Include first adjacency list node of location start
node[start].next = newEdge;
} else {
AjlistNode temp = node[start].next;
//Add new node at the last of edge
while (temp.next != null) {
temp = temp.next;
}
//Add node
temp.next = newEdge;
}
}
//Display graph elements
public void print_graph() {
if (size > 0 &&
node != null) {
int index = 0;
while (index < size) {
Console.Write("\nAdjacency list of vertex " + index + " : ");
AjlistNode temp = node[index].next;
while (temp != null) {
Console.Write(node[temp.id].data + " ");
temp = temp.next;
}
index++;
}
}
}
public void dfs(int start, Boolean[] visit) {
if (start > size ||
start < 0 ||
node == null) {
return;
}
if (visit[start] == true) {
return;
}
AjlistNode temp = node[start].next;
visit[start] = true;
while (temp != null) {
dfs(temp.id, visit);
temp = temp.next;
}
}
//Check path between two nodes
public void path(int start, Boolean[] visit) {
if (start > size ||
start < 0 ||
node == null) {
return;
}
if (visit[start] == true) {
return;
}
if (this.result == false) {
visit[start] = true;
AjlistNode temp = node[start].next;
while (temp != null) {
path(temp.id, visit);
temp = temp.next;
}
}
}
public void reset_path(Boolean[] visit) {
//reset value
for (int j = 0; j < this.size; j++) {
visit[j] = false;
}
}
public Boolean visited_status(Boolean[] visit) {
//reset value
for (int j = 0; j < this.size; j++) {
if (visit[j] == false) {
return false;
}
}
return true;
}
public void connection() {
Boolean[]
//Auxiliary space which is used to store information about
// node is visit or not
visit = new Boolean[size];
this.result = true;
for (int i = 0; i < size &&
this.result == true; ++i) {
reset_path(visit);
this.result = false;
this.path(i, visit);
//Check that whether i node are connected to other node
if (visited_status(visit) == true) {
this.result = true;
}
}
if (this.result == true) {
Console.Write("\n Strongly Connected Graph\n");
} else {
Console.Write("\n Not Strongly Connected Graph\n");
}
}
public static void Main(String[] args) {
MyGraph g1 = new MyGraph(5);
g1.add_edge(0, 4);
g1.add_edge(1, 0);
g1.add_edge(1, 2);
g1.add_edge(2, 1);
g1.add_edge(2, 4);
g1.add_edge(3, 1);
g1.add_edge(3, 2);
g1.add_edge(4, 3);
Console.Write("First Graph");
g1.print_graph();
g1.connection();
MyGraph g2 = new MyGraph(6);
g2.add_edge(0, 1);
g2.add_edge(0, 5);
g2.add_edge(1, 2);
g2.add_edge(2, 2);
g2.add_edge(2, 3);
g2.add_edge(3, 4);
g2.add_edge(4, 1);
g2.add_edge(5, 2);
g2.add_edge(5, 4);
Console.Write("\nSecond Graph");
g2.print_graph();
g2.connection();
}
}
Output
First Graph
Adjacency list of vertex 0 : 4
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 : 1 4
Adjacency list of vertex 3 : 1 2
Adjacency list of vertex 4 : 3
Strongly Connected Graph
Second Graph
Adjacency list of vertex 0 : 1 5
Adjacency list of vertex 1 : 2
Adjacency list of vertex 2 : 2 3
Adjacency list of vertex 3 : 4
Adjacency list of vertex 4 : 1
Adjacency list of vertex 5 : 2 4
Not Strongly Connected Graph
<?php
// Php program
// Check if graph is strongly connected or not
class AjlistNode {
//Vertices node key
public $id;
public $next;
function __construct($id) {
//Set value of node key
$this->id = $id;
$this->next = null;
}
}
class Vertices {
public $data;
public $next;
function __construct($data) {
$this->data = $data;
$this->next = null;
}
}
class MyQueue {
public $element;
public $next;
function __construct($element) {
$this->element = $element;
$this->next = null;
}
}
class MyGraph {
//number of Vertices
private $size;
private $node;
private $result;
function __construct($size) {
$this->size = $size;
$this->result = false;
$this->node = array_fill(0, $size, 0);
//set initial values of graph node
$this->set_data();
}
//Set initial node value
public function set_data() {
if ($this->node == null) {
echo("\nEmpty Graph");
} else {
$index = 0;
while ($index < $this->size) {
$this->node[$index] = new Vertices($index);
$index++;
}
}
}
//Connect two node
public function add_edge($start, $last) {
$newEdge = new AjlistNode($last);
if ($this->node[$start]->next == null) {
//Include first adjacency list node of location start
$this->node[$start]->next = $newEdge;
} else {
$temp = $this->node[$start]->next;
//Add new node at the last of edge
while ($temp->next != null) {
$temp = $temp->next;
}
//Add node
$temp->next = $newEdge;
}
}
//Display graph elements
public function print_graph() {
if ($this->size > 0 &&
$this->node != null) {
$index = 0;
while ($index < $this->size) {
echo("\nAdjacency list of vertex ". $index ." : ");
$temp = $this->node[$index]->next;
while ($temp != null) {
echo($this->node[$temp->id]->data ." ");
$temp = $temp->next;
}
$index++;
}
}
}
public function dfs($start, & $visit) {
if ($start > $this->size ||
$start < 0 ||
$this->node == null) {
return;
}
if ($visit[$start] == true) {
return;
}
$temp = $this->node[$start]->next;
$visit[$start] = true;
while ($temp != null) {
$this->dfs($temp->id, $visit);
$temp = $temp->next;
}
}
//Check path between two nodes
public function path($start, & $visit) {
if ($start > $this->size ||
$start < 0 ||
$this->node == null) {
return;
}
if ($visit[$start] == true) {
return;
}
if ($this->result == false) {
$visit[$start] = true;
$temp = $this->node[$start]->next;
while ($temp != null) {
$this->path($temp->id, $visit);
$temp = $temp->next;
}
}
}
public function reset_path( & $visit) {
//reset value
for ($j = 0; $j < $this->size; $j++) {
$visit[$j] = false;
}
}
public function visited_status( & $visit) {
//reset value
for ($j = 0; $j < $this->size; $j++) {
if ($visit[$j] == false) {
return false;
}
}
return true;
}
public function connection() {
//Auxiliary space which is used to store information about
// node is visit or not
$visit = array_fill(0, $this->size, false);
$this->result = true;
for ($i = 0; $i < $this->size &&
$this->result == true; ++$i) {
$this->reset_path($visit);
$this->result = false;
$this->path($i, $visit);
//Check that whether i node are connected to other node
if ($this->visited_status($visit) == true) {
$this->result = true;
}
}
if ($this->result == true) {
echo("\n Strongly Connected Graph\n");
} else {
echo("\n Not Strongly Connected Graph\n");
}
}
}
function main() {
$g1 = new MyGraph(5);
//Connected two node with Edges
$g1->add_edge(0, 4);
$g1->add_edge(1, 0);
$g1->add_edge(1, 2);
$g1->add_edge(2, 1);
$g1->add_edge(2, 4);
$g1->add_edge(3, 1);
$g1->add_edge(3, 2);
$g1->add_edge(4, 3);
echo("First Graph");
$g1->print_graph();
$g1->connection();
$g2 = new MyGraph(6);
//Connected two node with Edges
$g2->add_edge(0, 1);
$g2->add_edge(0, 5);
$g2->add_edge(1, 2);
$g2->add_edge(2, 2);
$g2->add_edge(2, 3);
$g2->add_edge(3, 4);
$g2->add_edge(4, 1);
$g2->add_edge(5, 2);
$g2->add_edge(5, 4);
echo("\nSecond Graph");
$g2->print_graph();
$g2->connection();
}
main();
Output
First Graph
Adjacency list of vertex 0 : 4
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 : 1 4
Adjacency list of vertex 3 : 1 2
Adjacency list of vertex 4 : 3
Strongly Connected Graph
Second Graph
Adjacency list of vertex 0 : 1 5
Adjacency list of vertex 1 : 2
Adjacency list of vertex 2 : 2 3
Adjacency list of vertex 3 : 4
Adjacency list of vertex 4 : 1
Adjacency list of vertex 5 : 2 4
Not Strongly Connected Graph
// Node Js program
// Check if graph is strongly connected or not
class AjlistNode {
//Vertices node key
constructor(id) {
//Set value of node key
this.id = id;
this.next = null;
}
}
class Vertices {
constructor(data) {
this.data = data;
this.next = null;
}
}
class MyGraph {
//number of Vertices
constructor(size) {
this.size = size;
this.result = false;
this.node = Array(size).fill(null);
//set initial values of graph node
this.set_data();
}
//Set initial node value
set_data() {
if (this.node == null) {
process.stdout.write("\nEmpty Graph");
} else {
var index = 0;
while (index < this.size) {
this.node[index] = new Vertices(index);
index++;
}
}
}
//Connect two node
add_edge(start, last) {
var newEdge = new AjlistNode(last);
if (this.node[start].next == null) {
//Include first adjacency list node of location start
this.node[start].next = newEdge;
} else {
var temp = this.node[start].next;
//Add new node at the last of edge
while (temp.next != null) {
temp = temp.next;
}
//Add node
temp.next = newEdge;
}
}
//Display graph elements
print_graph() {
if (this.size > 0 &&
this.node != null) {
var index = 0;
while (index < this.size) {
process.stdout.write("\nAdjacency list of vertex " + index + " : ");
var temp = this.node[index].next;
while (temp != null) {
process.stdout.write(this.node[temp.id].data + " ");
temp = temp.next;
}
index++;
}
}
}
dfs(start, visit) {
if (start > this.size ||
start < 0 ||
this.node == null) {
return;
}
if (visit[start] == true) {
return;
}
var temp = this.node[start].next;
visit[start] = true;
while (temp != null) {
this.dfs(temp.id, visit);
temp = temp.next;
}
}
//Check path between two nodes
path(start, visit) {
if (start > this.size ||
start < 0 ||
this.node == null) {
return;
}
if (visit[start] == true) {
return;
}
if (this.result == false) {
visit[start] = true;
var temp = this.node[start].next;
while (temp != null) {
this.path(temp.id, visit);
temp = temp.next;
}
}
}
reset_path(visit) {
//reset value
for (var j = 0; j < this.size; j++) {
visit[j] = false;
}
}
visited_status(visit) {
//reset value
for (var j = 0; j < this.size; j++) {
if (visit[j] == false) {
return false;
}
}
return true;
}
connection() {
//Auxiliary space which is used to store information about
// node is visit or not
var visit = Array(this.size).fill(false);
this.result = true;
for (var i = 0; i < this.size &&
this.result == true; ++i) {
this.reset_path(visit);
this.result = false;
this.path(i, visit);
//Check that whether i node are connected to other node
if (this.visited_status(visit) == true) {
this.result = true;
}
}
if (this.result == true) {
process.stdout.write("\n Strongly Connected Graph\n");
} else {
process.stdout.write("\n Not Strongly Connected Graph\n");
}
}
}
function main(args) {
var g1 = new MyGraph(5);
//Connected two node with Edges
g1.add_edge(0, 4);
g1.add_edge(1, 0);
g1.add_edge(1, 2);
g1.add_edge(2, 1);
g1.add_edge(2, 4);
g1.add_edge(3, 1);
g1.add_edge(3, 2);
g1.add_edge(4, 3);
process.stdout.write("First Graph");
g1.print_graph();
g1.connection();
var g2 = new MyGraph(6);
//Connected two node with Edges
g2.add_edge(0, 1);
g2.add_edge(0, 5);
g2.add_edge(1, 2);
g2.add_edge(2, 2);
g2.add_edge(2, 3);
g2.add_edge(3, 4);
g2.add_edge(4, 1);
g2.add_edge(5, 2);
g2.add_edge(5, 4);
process.stdout.write("\nSecond Graph");
g2.print_graph();
g2.connection();
}
main();
Output
First Graph
Adjacency list of vertex 0 : 4
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 : 1 4
Adjacency list of vertex 3 : 1 2
Adjacency list of vertex 4 : 3
Strongly Connected Graph
Second Graph
Adjacency list of vertex 0 : 1 5
Adjacency list of vertex 1 : 2
Adjacency list of vertex 2 : 2 3
Adjacency list of vertex 3 : 4
Adjacency list of vertex 4 : 1
Adjacency list of vertex 5 : 2 4
Not Strongly Connected Graph
# Python 3 program
# Check if graph is strongly connected or not
class AjlistNode :
def __init__(self, id) :
# Set value of node key
self.id = id
self.next = None
class Vertices :
def __init__(self, data) :
self.data = data
self.next = None
class MyGraph :
def __init__(self, size) :
self.size = size
self.result = False
self.node = [0] * size
# set initial values of graph node
self.set_data()
# Set initial node value
def set_data(self) :
if (self.node == None) :
print("\nEmpty Graph", end = "")
else :
index = 0
while (index < self.size) :
self.node[index] = Vertices(index)
index += 1
# Connect two node
def add_edge(self, start, last) :
newEdge = AjlistNode(last)
if (self.node[start].next == None) :
# Include first adjacency list node of location start
self.node[start].next = newEdge
else :
temp = self.node[start].next
# Add new node at the last of edge
while (temp.next != None) :
temp = temp.next
# Add node
temp.next = newEdge
# Display graph elements
def print_graph(self) :
if (self.size > 0 and self.node != None) :
index = 0
while (index < self.size) :
print("\nAdjacency list of vertex ", index ," : ", end = "")
temp = self.node[index].next
while (temp != None) :
print(self.node[temp.id].data ," ", end = "")
temp = temp.next
index += 1
def dfs(self, start, visit) :
if (start > self.size or start < 0 or self.node == None) :
return
if (visit[start] == True) :
return
temp = self.node[start].next
visit[start] = True
while (temp != None) :
self.dfs(temp.id, visit)
temp = temp.next
# Check path between two nodes
def path(self, start, visit) :
if (start > self.size or start < 0 or self.node == None) :
return
if (visit[start] == True) :
return
if (self.result == False) :
visit[start] = True
temp = self.node[start].next
while (temp != None) :
self.path(temp.id, visit)
temp = temp.next
def reset_path(self, visit) :
# reset value
j = 0
while (j < self.size) :
visit[j] = False
j += 1
def visited_status(self, visit) :
# check visited value
j = 0
while (j < self.size) :
if (visit[j] == False) :
return False
j += 1
return True
def connection(self) :
# node is visit or not
# Auxiliary space which is used to store information about
# node is visit or not
visit = [False] * self.size
self.result = True
i = 0
while (i < self.size and self.result == True) :
self.reset_path(visit)
self.result = False
self.path(i, visit)
# Check that whether i node are connected to other node
if (self.visited_status(visit) == True) :
self.result = True
i += 1
if (self.result == True) :
print("\n Strongly Connected Graph\n", end = "")
else :
print("\n Not Strongly Connected Graph\n", end = "")
def main() :
g1 = MyGraph(5)
# Connected two node with Edges
g1.add_edge(0, 4)
g1.add_edge(1, 0)
g1.add_edge(1, 2)
g1.add_edge(2, 1)
g1.add_edge(2, 4)
g1.add_edge(3, 1)
g1.add_edge(3, 2)
g1.add_edge(4, 3)
print("First Graph", end = "")
g1.print_graph()
g1.connection()
g2 = MyGraph(6)
# Connected two node with Edges
g2.add_edge(0, 1)
g2.add_edge(0, 5)
g2.add_edge(1, 2)
g2.add_edge(2, 2)
g2.add_edge(2, 3)
g2.add_edge(3, 4)
g2.add_edge(4, 1)
g2.add_edge(5, 2)
g2.add_edge(5, 4)
print("\nSecond Graph", end = "")
g2.print_graph()
g2.connection()
if __name__ == "__main__":
main()
Output
First Graph
Adjacency list of vertex 0 : 4
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 : 1 4
Adjacency list of vertex 3 : 1 2
Adjacency list of vertex 4 : 3
Strongly Connected Graph
Second Graph
Adjacency list of vertex 0 : 1 5
Adjacency list of vertex 1 : 2
Adjacency list of vertex 2 : 2 3
Adjacency list of vertex 3 : 4
Adjacency list of vertex 4 : 1
Adjacency list of vertex 5 : 2 4
Not Strongly Connected Graph
# Ruby program
# Check if graph is strongly connected or not
class AjlistNode
# Define the accessor and reader of class AjlistNode
attr_reader :id, :next
attr_accessor :id, :next
# Vertices node key
def initialize(id)
# Set value of node key
self.id = id
self.next = nil
end
end
class Vertices
# Define the accessor and reader of class Vertices
attr_reader :data, :next
attr_accessor :data, :next
def initialize(data)
self.data = data
self.next = nil
end
end
class MyGraph
# Define the accessor and reader of class MyGraph
attr_reader :size, :node, :result
attr_accessor :size, :node, :result
def initialize(size)
self.size = size
self.result = false
self.node = Array.new(size) {nil}
# set initial values of graph node
self.set_data()
end
# Set initial node value
def set_data()
if (@node == nil)
print("\nEmpty Graph")
else
index = 0
while (index < @size)
@node[index] = Vertices.new(index)
index += 1
end
end
end
# Connect two node
def add_edge(start, last)
newEdge = AjlistNode.new(last)
if (@node[start].next == nil)
# Include first adjacency list node of location start
@node[start].next = newEdge
else
temp = @node[start].next
# Add new node at the last of edge
while (temp.next != nil)
temp = temp.next
end
# Add node
temp.next = newEdge
end
end
# Display graph elements
def print_graph()
if (@size > 0 &&
@node != nil)
index = 0
while (index < @size)
print("\nAdjacency list of vertex ", index ," : ")
temp = @node[index].next
while (temp != nil)
print(@node[temp.id].data ," ")
temp = temp.next
end
index += 1
end
end
end
def dfs(start, visit)
if (start > @size ||
start < 0 ||
@node == nil)
return
end
if (visit[start] == true)
return
end
temp = @node[start].next
visit[start] = true
while (temp != nil)
self.dfs(temp.id, visit)
temp = temp.next
end
end
# Check path between two nodes
def path(start, visit)
if (start > @size ||
start < 0 ||
@node == nil)
return
end
if (visit[start] == true)
return
end
if (self.result == false)
visit[start] = true
temp = @node[start].next
while (temp != nil)
self.path(temp.id, visit)
temp = temp.next
end
end
end
def reset_path(visit)
# reset value
j = 0
while (j < self.size)
visit[j] = false
j += 1
end
end
def visited_status(visit)
# check visited value
j = 0
while (j < self.size)
if (visit[j] == false)
return false
end
j += 1
end
return true
end
def connection()
# Auxiliary space which is used to store information about
# node is visit or not
visit = Array.new(@size) {false}
self.result = true
i = 0
while (i < @size &&
self.result == true)
self.reset_path(visit)
self.result = false
self.path(i, visit)
# Check that whether i node are connected to other node
if (self.visited_status(visit) == true)
self.result = true
end
i += 1
end
if (self.result == true)
print("\n Strongly Connected Graph\n")
else
print("\n Not Strongly Connected Graph\n")
end
end
end
def main()
g1 = MyGraph.new(5)
# Connected two node with Edges
g1.add_edge(0, 4)
g1.add_edge(1, 0)
g1.add_edge(1, 2)
g1.add_edge(2, 1)
g1.add_edge(2, 4)
g1.add_edge(3, 1)
g1.add_edge(3, 2)
g1.add_edge(4, 3)
print("First Graph")
g1.print_graph()
g1.connection()
g2 = MyGraph.new(6)
# Connected two node with Edges
g2.add_edge(0, 1)
g2.add_edge(0, 5)
g2.add_edge(1, 2)
g2.add_edge(2, 2)
g2.add_edge(2, 3)
g2.add_edge(3, 4)
g2.add_edge(4, 1)
g2.add_edge(5, 2)
g2.add_edge(5, 4)
print("\nSecond Graph")
g2.print_graph()
g2.connection()
end
main()
Output
First Graph
Adjacency list of vertex 0 : 4
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 : 1 4
Adjacency list of vertex 3 : 1 2
Adjacency list of vertex 4 : 3
Strongly Connected Graph
Second Graph
Adjacency list of vertex 0 : 1 5
Adjacency list of vertex 1 : 2
Adjacency list of vertex 2 : 2 3
Adjacency list of vertex 3 : 4
Adjacency list of vertex 4 : 1
Adjacency list of vertex 5 : 2 4
Not Strongly Connected Graph
// Scala program
// Check if graph is strongly connected or not
class AjlistNode(var id: Int,
var next: AjlistNode) {
def this(id: Int) {
//Set value
this(id,null);
}
}
class Vertices(var data: Int,
var next: AjlistNode) {
def this(data: Int) {
this(data,null);
}
}
class MyGraph(var size: Int,
var node : Array[Vertices],
var result : Boolean) {
def this(value: Int) {
//set value
this(value,Array.fill[Vertices](value)(null),false);
//set initial values of graph node
this.set_data();
}
//Set initial node value
def set_data(): Unit = {
if (this.node == null) {
print("\nEmpty Graph");
} else {
var index: Int = 0;
while (index < this.size) {
this.node(index) = new Vertices(index);
index += 1;
}
}
}
//Connect two node
def add_edge(start: Int, last: Int): Unit = {
var newEdge: AjlistNode = new AjlistNode(last);
if (this.node(start).next == null) {
//Include first adjacency list node of location start
this.node(start).next = newEdge;
} else {
var temp: AjlistNode = this.node(start).next;
//Add new node at the last of edge
while (temp.next != null) {
temp = temp.next;
}
//Add node
temp.next = newEdge;
}
}
//Display graph elements
def print_graph(): Unit = {
if (this.size > 0 &&
this.node != null) {
var index: Int = 0;
while (index < this.size) {
print("\nAdjacency list of vertex " + index + " : ");
var temp: AjlistNode = this.node(index).next;
while (temp != null) {
print(" "+this.node(temp.id).data + " ");
temp = temp.next;
}
index += 1;
}
}
}
def dfs(start: Int, visit: Array[Boolean]): Unit = {
if (start > this.size ||
start < 0 ||
this.node == null) {
return;
}
if (visit(start) == true) {
return;
}
var temp: AjlistNode = this.node(start).next;
visit(start) = true;
while (temp != null) {
dfs(temp.id, visit);
temp = temp.next;
}
}
//Check path between two nodes
def path(start: Int, visit: Array[Boolean]): Unit = {
if (start > this.size ||
start < 0 ||
this.node == null) {
return;
}
if (visit(start) == true) {
return;
}
if (this.result == false) {
visit(start) = true;
var temp: AjlistNode = this.node(start).next;
while (temp != null) {
path(temp.id, visit);
temp = temp.next;
}
}
}
def reset_path(visit: Array[Boolean]): Unit = {
//reset value
var j: Int = 0;
while (j < this.size) {
visit(j) = false;
j += 1;
}
}
def visited_status(visit: Array[Boolean]): Boolean = {
//check visited value
var j: Int = 0;
while (j < this.size) {
if (visit(j) == false) {
return false;
}
j += 1;
}
return true;
}
def connection(): Unit = {
//Auxiliary space which is used to store information about
// node is visit or not
var visit: Array[Boolean] = Array.fill[Boolean](this.size)(false);
this.result = true;
var i: Int = 0;
while (i < this.size &&
this.result == true) {
reset_path(visit);
this.result = false;
this.path(i, visit);
//Check that whether i node are connected to other node
if (visited_status(visit) == true) {
this.result = true;
}
i += 1;
}
if (this.result == true) {
print("\n Strongly Connected Graph\n");
} else {
print("\n Not Strongly Connected Graph\n");
}
}
}
object Main {
def main(args: Array[String]): Unit = {
var g1: MyGraph = new MyGraph(5);
//Connected two node with Edges
g1.add_edge(0, 4);
g1.add_edge(1, 0);
g1.add_edge(1, 2);
g1.add_edge(2, 1);
g1.add_edge(2, 4);
g1.add_edge(3, 1);
g1.add_edge(3, 2);
g1.add_edge(4, 3);
print("First Graph");
g1.print_graph();
g1.connection();
var g2: MyGraph = new MyGraph(6);
//Connected two node with Edges
g2.add_edge(0, 1);
g2.add_edge(0, 5);
g2.add_edge(1, 2);
g2.add_edge(2, 2);
g2.add_edge(2, 3);
g2.add_edge(3, 4);
g2.add_edge(4, 1);
g2.add_edge(5, 2);
g2.add_edge(5, 4);
print("\nSecond Graph");
g2.print_graph();
g2.connection();
}
}
Output
First Graph
Adjacency list of vertex 0 : 4
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 : 1 4
Adjacency list of vertex 3 : 1 2
Adjacency list of vertex 4 : 3
Strongly Connected Graph
Second Graph
Adjacency list of vertex 0 : 1 5
Adjacency list of vertex 1 : 2
Adjacency list of vertex 2 : 2 3
Adjacency list of vertex 3 : 4
Adjacency list of vertex 4 : 1
Adjacency list of vertex 5 : 2 4
Not Strongly Connected Graph
// Swift program
// Check if graph is strongly connected or not
class AjlistNode {
//Vertices node key
var id: Int;
var next: AjlistNode? ;
init(_ id: Int) {
//Set value of node key
self.id = id;
self.next = nil;
}
}
class Vertices {
var data: Int;
var next: AjlistNode? ;
init(_ data: Int) {
self.data = data;
self.next = nil;
}
}
class MyGraph {
//number of Vertices
var size: Int;
var node: [Vertices]? = [Vertices]() ;
var result: Bool;
init(_ size: Int) {
self.size = size;
self.result = false;
var i = 0;
while (i<size) {
self.node!.append(Vertices(i));
i+=1;
}
}
//Connect two node
func add_edge(_ start: Int, _ last: Int) {
let newEdge: AjlistNode? = AjlistNode(last);
if (self.node![start].next == nil) {
//Include first adjacency list node of location start
self.node![start].next = newEdge;
} else {
var temp: AjlistNode? = self.node![start].next;
//Add new node at the last of edge
while (temp!.next != nil) {
temp = temp!.next;
}
//Add node
temp!.next = newEdge;
}
}
//Display graph elements
func print_graph() {
if (self.size > 0 &&
self.node != nil) {
var index: Int = 0;
while (index < self.size) {
print("\nAdjacency list of vertex ", index ," : ", terminator: "");
var temp: AjlistNode? = self.node![index].next;
while (temp != nil) {
print(self.node![temp!.id].data ," ", terminator: "");
temp = temp!.next;
}
index += 1;
}
}
}
func dfs(_ start: Int, _ visit: inout[Bool]) {
if (start > self.size ||
start < 0 ||
self.node == nil) {
return;
}
if (visit[start] == true) {
return;
}
var temp: AjlistNode? = self.node![start].next;
visit[start] = true;
while (temp != nil) {
self.dfs(temp!.id, &visit);
temp = temp!.next;
}
}
//Check path between two nodes
func path(_ start: Int, _ visit: inout[Bool]) {
if (start > self.size ||
start < 0 ||
self.node == nil) {
return;
}
if (visit[start] == true) {
return;
}
if (self.result == false) {
visit[start] = true;
var temp: AjlistNode? = self.node![start].next;
while (temp != nil) {
self.path(temp!.id, &visit);
temp = temp!.next;
}
}
}
func reset_path(_ visit: inout[Bool]) {
//reset value
var j: Int = 0;
while (j < self.size) {
visit[j] = false;
j += 1;
}
}
func visited_status(_ visit: [Bool]) -> Bool {
//check visited value
var j: Int = 0;
while (j < self.size) {
if (visit[j] == false) {
return false;
}
j += 1;
}
return true;
}
func connection() {
//Auxiliary space which is used to store information about
// node is visit or not
var visit: [Bool] = Array(repeating: false, count: self.size);
self.result = true;
var i: Int = 0;
while (i < self.size &&
self.result == true) {
self.reset_path(&visit);
self.result = false;
self.path(i, &visit);
//Check that whether i node are connected to other node
if (self.visited_status(visit) == true) {
self.result = true;
}
i += 1;
}
if (self.result == true) {
print("\n Strongly Connected Graph\n", terminator: "");
} else {
print("\n Not Strongly Connected Graph\n", terminator: "");
}
}
}
func main() {
let g1: MyGraph? = MyGraph(5);
//Connected two node with Edges
g1!.add_edge(0, 4);
g1!.add_edge(1, 0);
g1!.add_edge(1, 2);
g1!.add_edge(2, 1);
g1!.add_edge(2, 4);
g1!.add_edge(3, 1);
g1!.add_edge(3, 2);
g1!.add_edge(4, 3);
print("First Graph", terminator: "");
g1!.print_graph();
g1!.connection();
let g2: MyGraph? = MyGraph(6);
//Connected two node with Edges
g2!.add_edge(0, 1);
g2!.add_edge(0, 5);
g2!.add_edge(1, 2);
g2!.add_edge(2, 2);
g2!.add_edge(2, 3);
g2!.add_edge(3, 4);
g2!.add_edge(4, 1);
g2!.add_edge(5, 2);
g2!.add_edge(5, 4);
print("\nSecond Graph", terminator: "");
g2!.print_graph();
g2!.connection();
}
main();
Output
First Graph
Adjacency list of vertex 0 : 4
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 : 1 4
Adjacency list of vertex 3 : 1 2
Adjacency list of vertex 4 : 3
Strongly Connected Graph
Second Graph
Adjacency list of vertex 0 : 1 5
Adjacency list of vertex 1 : 2
Adjacency list of vertex 2 : 2 3
Adjacency list of vertex 3 : 4
Adjacency list of vertex 4 : 1
Adjacency list of vertex 5 : 2 4
Not Strongly Connected Graph
Time Complexity
The algorithm performs a DFS for each vertex twice. In the worst case, this results in a time complexity of O(V * (V + E)), where V is the number of vertices and E is the number of edges in the graph.
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