Skip to main content

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:

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

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

  1. 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.
  2. Reset the visited array.
  3. Perform DFS again from the same vertex.
  4. If any vertex is unvisited, return false.
  5. 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.

Last updated on by Kalkicode




Comment

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

New Comment