Skip to main content

Check if graph is strongly connected or not

Graphs are strongly connected, if when every node of path is capable to visit all other node of graph. for example source node V is visit all nodes of graph and others nodes is capable to reach the node V.

Check if graph is strongly connected or not

In given above graph is strongly connected. because each node are direct and indirect connecting to each other. For example

Node 0:
0 -> 4
0 -> 4 -> 3
0 -> 4 -> 3 -> 1
0 -> 4 -> 3 -> 5
or
0 -> 4 -> 3 -> 1 -> 5
//Similar way other nodes

If in this graph are remove edge from (1->0) then graph are not strongly connected because other nodes are not capable to visiting a node (0). for example.

Node 0:
0 -> 4
0 -> 4 -> 3
0 -> 4 -> 3 -> 1
0 -> 4 -> 3 -> 5
or
0 -> 4 -> 3 -> 1 -> 5

Node 1:
1 -> 2
1 -> 2 -> 4
1 -> 2 -> 4 -> 3
//not reached to node 0  
//so this is not strongly connected

Here given code implementation process.

//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 setData(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 addEdge(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 printGraph(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");
  }
}


//pick a path 
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;
  }
}
//Check path between two nodes
void check_path(int start,
  int end,
  int *visit,
  struct Graph*node,
  int *result)
{

  if(start >size 
    || end >size 
    || start<0 
    || end<0 
    || node==NULL)
  {
    //invalid input
    return ;
  }
  if(start==end)
  {
    //when node is connected
    visit[start]=1;
    *result=1;
    return;
  }
  if(visit[start]==1)
  {
    //node which is already check
    return;
  }
  if(*result==0)
  {

    visit[start]=1;
    struct AjlistNode *temp=node[start].next;
    while(temp!=NULL)
    {
      check_path(temp->vId,end,visit,node,result); 
      temp=temp->next;
    }
  }

}

//Handling the execution of two nodes, 
//And checking that two nodes are connected or not
void connection(struct Graph*node)
{
 
  int result=1,status=1;

  int *visit=(int*)calloc(size,sizeof(int));
  //first we are check, node 0 are connected or not to all other nodes
  DFS(0,visit,node);

  for (int i = 0; i < size; ++i)
  {
    if(visit[i]!=1)
    {
      //When not connect
      result=0;

      break;
    }
  }

  status=result;
  //remove memory
  free(visit);

  visit=NULL;

  if(status==1)
  {
    //Check other nodes are capable to visit first node or not
    for (int i = 1; i < size && status==1; ++i)
    {
      result=0;
      //Create memory of visiting nodes
      visit=(int*)calloc(size,sizeof(int));

      //0 is first node i is other node
      check_path(i,0,visit,node,&result);

      //remove memory
      free(visit);

      visit=NULL;
      //get new modification
      status=result;
    }
  }

  if(status==1)
  {
    printf("\n Strongly Connected Graph\n");
  }else
  {
    printf("\n Not Strongly Connected Graph\n");
  }
}

int main()
{

  size=5;
  struct Graph*node=NULL;

  node=(struct Graph*)malloc(sizeof(struct Graph)*size);

  if(node==NULL)
  {
    printf("\n Memory overflow");
  }else
  {
    //First set node keys
    setData(node); 

    //Connected two node with Edges
    addEdge(node,0, 4); 
    addEdge(node,1, 0); 
    addEdge(node,1, 2); 
    addEdge(node,2, 1); 
    addEdge(node,2, 4); 
    addEdge(node,3, 1);  
    addEdge(node,3, 2); 
    addEdge(node,4, 3); 
    printGraph(node);
    connection(node);
  }  
  return 0;
}

Output

 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
//C++ program
//Check if graph is strongly connected or not
#include<iostream>
using namespace std;

struct AjlistNode
{
    int vId;//Vertices id
    struct AjlistNode*next;
};

struct Vertices
{
    int data; //node key value
    struct AjlistNode*next;
};


class Graph
{
  Vertices *node;
    int size;//number of 
public:
  Graph(int);
  void setData();
  void addEdge(int,int);
  void printGraph();
    void DFS(int ,int *);
    void check_path(int ,int ,int *,int *);
  void connection();
  void connect(int  ,int );
};
Graph::Graph(int size)
{
  this->size = size;
    //set number of nodes
  node = new Vertices[size];
}
//set node key value
void Graph:: setData()
{
  if(node!=NULL)
  {
    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
  {
    cout<<"Vertic Node is Empty"<<endl;
  }
}
//Add Edge from Two given Nodes
void Graph ::connect(int start ,int end)
{
    //add edge form start to end
    //start and end is Node location
    //first create Adjacency node
  AjlistNode *newEdge=new AjlistNode;

  if(newEdge!=NULL)
  {

    newEdge->next = NULL;
    newEdge->vId = end;

    AjlistNode *temp=node[start].next;

    if(temp==NULL)
    {
      node[start].next=newEdge;
    }else
    {
            //Add node at last
      while(temp->next!=NULL)
      {
        temp=temp->next;
      }      
      temp->next=newEdge;          
    }
  }

}


void Graph ::  addEdge(int V ,int E)
{
    //add edge form V to E
    //V and E is Node location
  if(V<size && E <size)
  {
    connect(V,E);

    }else
    {
        //not valid Vertices
      cout<<"Invalid Node Vertices "<< V<<" "<<E;
    }
}

//Display Adjacency list of vertex
void Graph::printGraph()
{
  if(node!=NULL)
  {
    AjlistNode *temp=NULL;
    for(int index=0; index < size; index++)
    {
      cout<<"\n Adjacency list of vertex "<<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

        cout<<" "<<node[temp->vId].data;
        temp=temp->next;
      }
    }
  }else
  {
    cout<<"Empty Graph"<<endl;
  }
}

//pick a path 
void Graph :: DFS(int start,int *visit)
{

  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); 
    temp=temp->next;
  }
}
//Check path between two nodes
void Graph :: check_path(int start,
  int end,
  int *visit,
  int *result)
{

  if(start >size 
  || end >size 
  || start<0 
  || end<0 
  || node==NULL)
  {
    //invalid input
    return ;
  }
  if(start==end)
  {
    //when node is connected
    visit[start]=1;
    *result=1;
    return;
  }
  if(visit[start]==1)
  {
    //node which is already check
    return;
  }
  if(*result==0)
  {

    visit[start]=1;
    struct AjlistNode *temp=node[start].next;
    while(temp!=NULL)
    {
      check_path(temp->vId,end,visit,result); 
      temp=temp->next;
    }
  }

}

//Handling the execution of two nodes, 
//And checking that two nodes are connected or not
void Graph :: connection()
{
 
  int result=1,status=1;

  int *visit=new int[size];
  //first we are check, node 0 are connected or not to all other nodes
  DFS(0,visit);

  for (int i = 0; i < size; ++i)
  {
    if(visit[i]!=1)
    {
      //When not connect
      result=0;

      break;
    }
  }

  status=result;
 

  if(status==1)
  {
    //Check other nodes are capable to visit first node or not
    for (int i = 1; i < size && status==1; ++i)
    {
      result=0;
      for (int j = 0; j < size; ++j)
      {
        visit[j]=0;
      }

      //0 is first node i is other node
      check_path(i,0,visit,&result);

    
      //get new modification
      status=result;
    }
  }

  if(status==1)
  {
    cout<<("\n Strongly Connected Graph\n");
  }else
  {
    cout<<("\n Not Strongly Connected Graph\n");
  }
}
int main()
{
    //Create Object
  Graph g=Graph(5);
    //First set node keys
  g.setData();

    //Connected two node with Edges
    g.addEdge(0, 4); 
    g.addEdge(1, 0); 
    g.addEdge(1, 2); 
    g.addEdge(2, 1); 
    g.addEdge(2, 4); 
    g.addEdge(3, 1);  
    g.addEdge(3, 2); 
    g.addEdge(4, 3); 
    g.printGraph();
    g.connection();
  return 0;
}

Output

 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

//Java program
//Check if graph is strongly connected or not
public class MyGraph
{

    static class AjlistNode
    {
        int id;//Vertices node key
        AjlistNode next;
    }
    static class Vertices
    {
        int data;
        AjlistNode next;
    }

    //number of Vertices
    static int size;
    int result;
    Vertices node[];

    MyGraph(int size)
    {
        //set value
        this.size = size;
        node = new Vertices[size];
        result=0;
    }

    //set initial node value
    public void setData()
    {
        if(node == null)
        {
            System.out.println("\nEmpty Graph");

        }else
        {
            for(int index = 0; index < size; index++)
            {

                node[index]=new Vertices(); 
                node[index].data=index;//set your data
                node[index].next=null;
            }
        }
    }
    //connect two nodes
    public void connect(int start,int end)
    {
        AjlistNode newEdge=new AjlistNode();
        newEdge.id=end;//end node
        newEdge.next=null;
        if(node[start].next==null)
        {
            node[start].next=newEdge;
        }else
        {
            AjlistNode temp=node[start].next;

            while(temp.next!=null)
            {
                temp=temp.next;
            }
            temp.next=newEdge;
        }
    }
    //Add edge at the end
    public void addEdge(int start,int end)
    {
        if(start < size && end < size && node != null)
        {
            connect(start,end);

        }else
        {
            System.out.println("\nInvalid nodes "+start+" "+end);
        }
    }

    public void printGraph()
    {

        if(size>0 && node!=null)
        {
            for(int index=0;index<size;index++)
            {
                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;
                }
            }
        }
    }

    //pick a path 
    void  DFS(int start,int []visit)
    {

        if(start >size ||start<0 || this.node==null)
        {
            //invalid input
            return ;
        }
        if(visit[start]==1)
        {
            return;
        }

        visit[start]=1;

        AjlistNode  temp=node[start].next;
        while(temp!=null)
        {
            DFS(temp.id,visit); 
            temp=temp.next;
        }
    }
    //Check path between two nodes
    public void  check_path(int start,
      int end,
      int  []visit)
    {

        if(start >size 
            || end >size 
            || start<0 
            || end<0 
            || this.node==null)
        {
            //invalid input
            return ;
        }
        if(start == end)
        {
            //when node is connected
            visit[start]=1;
            this.result=1;
            return;
        }
        if(visit[start]==1)
        {
            //node which is already check
            return;
        }
        if( this.result==0)
        {

            visit[start]=1;
            AjlistNode  temp=node[start].next;
            while(temp!=null)
            {
                check_path(temp.id,end,visit); 
                temp=temp.next;
            }
        }

    }

    //Handling the execution of two nodes, 
    //And checking that two nodes are connected or not
    public void connection()
    {

        int status=1;
        this.result=1;
        int  []visit=new int[size];
        //first we are check, node 0 are connected or not to all other nodes
        DFS(0,visit);

        for (int i = 0; i < size; ++i)
        {
            if(visit[i]!=1)
            {
               //When not connect
                this.result=0;

                break;
            }
        }

        status=this.result;


        if(status==1)
        {
            //Check other nodes are capable to visit first node or not
            for (int i = 1; i < size && status==1; ++i)
            {
                this.result=0;

                for (int j = 0; j < size; ++j)
                {
                    visit[j]=0;
                }

                //0 is first node i is other node
                check_path(i,0,visit);


                //get new modification
                status=result;
            }
        }

        if(status==1)
        {
            System.out.println("\n Strongly Connected Graph");
        }else
        {
            System.out.println("\n Not Strongly Connected Graph");
        }
    }



    public static void main(String[] args) 
    {
        int totalNode=5;

        MyGraph g=new MyGraph(totalNode);

        g.setData();


        //Connected two node with Edges
        g.addEdge(0, 4); 
        g.addEdge(1, 0); 
        g.addEdge(1, 2); 
        g.addEdge(2, 1); 
        g.addEdge(2, 4); 
        g.addEdge(3, 1);  
        g.addEdge(3, 2); 
        g.addEdge(4, 3); 
        g.printGraph();
        g.connection();
    }
}

Output

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

#Python program
#Check if graph is strongly connected or not

class AjLinkeNode:
  def __init__(self,data):
    self.id=data
    self.next=None

class Vertices:
  def __init__(self,data):
    self.data=data
    self.next=None

class Graph:
  """Constructor for Graph"""
  def __init__(self, size):
    self.size=size
    self.node=[]
    self.result=0
    

  def setData(self):
    if(self.size>0 and self.node!=None):
      index=0
      while(index<self.size):
        self.node.append(Vertices(index))
        index+=1


  #connect two node with  edge
  def connect(self,start,end):
    new_edge=AjLinkeNode(end)
    if(self.node[start].next==None):
      self.node[start].next=new_edge
    else:
      temp=self.node[start].next
      while(temp.next!=None):
        temp=temp.next
      temp.next=new_edge  

  #add edge
  def addEdge(self,start,end):

    #start,end is two nodes
    if(self.size>start and self.size>start):
      
      self.connect(start,end)
  
    else:
      print("Invalid nodes")


  def printGraph(self):

    if(self.size>0 and self.node!=None):

      index=0

      while(index<self.size):

        print("\nAdjacency list of vertex  : {0}".format(index),end=" ")
        
        temp=self.node[index].next
        
        while temp!=None:

          print(" {0}".format(temp.id),end=" ")

          temp=temp.next

        index+=1

  #pick a path 
  def  DFS(self,start,visit) :

    if(start >self.size or start<0 or  self.node==None) :
      #invalid input
      return 
    
    if(visit[start]==1) :
      return
    

    visit[start]=1

    temp=self.node[start].next

    while(temp!=None):

      self.DFS(temp.id,visit) 

      temp=temp.next
    
  
  #Check path between two nodes
  def  check_path(self, start,end,visit):

    if(start > self.size or  end > self.size or  start < 0 or  end < 0 or  self.node==None):
      #invalid input
      return 
    
    if(start == end):
      #when node is connected
      visit[start]=1
      self.result=1
      return
    
    if(visit[start]==1):
      #node which is already check
      return
    
    if( self.result==0):

      visit[start]=1
      temp=self.node[start].next
      while(temp!=None):
        self.check_path(temp.id,end,visit) 
        temp=temp.next
      
      

  

  #Handling the execution of two nodes, 
  #And checking that two nodes are connected or not
  def connection(self):

    status=1
    self.result=1
    visit=[0]*self.size
    #first we are check, node 0 are connected or not to all other nodes
    self.DFS(0,visit)
    i = 0
    while(i<self.size) :

      if(visit[i]!=1):
        #When not connect
        self.result=0
        break

      i+=1
    

    status=self.result


    if(status==1):
      i=0
      
      #Check other nodes are capable to visit first node or not
      while(i<self.size and status==1) :
        
        self.result=0

        visit=[0]*self.size
        
        #0 is first node i is other node
        self.check_path(i,0,visit)

        i+=1

        #get new modification
        status=self.result
        
  
    if(status==1) :
      print("\n Strongly Connected Graph")
    else :
      print("\n Not Strongly Connected Graph")
      


    
def main():
  g=Graph(5)
  g.setData() 
  #Connected two node with Edges

  g.addEdge(0, 4) 
  g.addEdge(1, 0) 
  g.addEdge(1, 2) 
  g.addEdge(2, 1) 
  g.addEdge(2, 4) 
  g.addEdge(3, 1)  
  g.addEdge(3, 2) 
  g.addEdge(4, 3) 
  g.printGraph()
  g.connection()

if __name__=="__main__":
    main()

Output

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

//C# Graph 
//Check if graph is strongly connected or not
using System;

public class AjlistNode
{
  public int id;//Vertices node key
  public AjlistNode next;
}
public class Vertices
{
  public int data;
  public AjlistNode next;
}
public class MyGraph
{



  //number of Vertices
  public int size;
  public int result;
  public Vertices []node;

  public MyGraph(int size)
  {
    //set value
    this.size = size;
    node = new Vertices[size];
    result=0;
  }

  //set initial node value
  public void setData()
  {
    if(node == null)
    {
      Console.WriteLine("\nEmpty Graph");

    }else
    {
      for(int index = 0; index < size; index++)
      {

        node[index]=new Vertices(); 
        node[index].data=index;//set your data
        node[index].next=null;
      }
    }
  }
  //connect two nodes
  public void connect(int start,int end)
  {
    AjlistNode newEdge=new AjlistNode();
    newEdge.id=end;//end node
    newEdge.next=null;
    if(node[start].next==null)
    {
      node[start].next=newEdge;
    }else
    {
      AjlistNode temp=node[start].next;

      while(temp.next!=null)
      {
        temp=temp.next;
      }
      temp.next=newEdge;
    }
  }
  //Add edge at the end
  public void addEdge(int start,int end)
  {
    if(start < size && end < size && node != null)
    {
      connect(start,end);

    }else
    {
      Console.WriteLine("\nInvalid nodes "+start+" "+end);
    }
  }

  public void printGraph()
  {

    if(size>0 && node!=null)
    {
      for(int index=0;index<size;index++)
      {
        Console.Write("\nAdjacency list of vertex "+index+" :");

        AjlistNode temp=node[index].next;

        while(temp!=null)
        {
          Console.Write(" "+node[temp.id].data);

          temp=temp.next;
        }
      }
    }
  }

  //pick a path 
  void  DFS(int start,int []visit)
  {

    if(start >size ||start<0 || this.node==null)
    {
      //invalid input
      return ;
    }
    if(visit[start]==1)
    {
      return;
    }

    visit[start]=1;

    AjlistNode  temp=node[start].next;
    while(temp!=null)
    {
      DFS(temp.id,visit); 
      temp=temp.next;
    }
  }
  //Check path between two nodes
  public void  check_path(int start,
    int end,
    int  []visit)
  {

    if(start >size 
      || end >size 
      || start<0 
      || end<0 
      || this.node==null)
    {
      //invalid input
      return ;
    }
    if(start == end)
    {
      //when node is connected
      visit[start]=1;
      this.result=1;
      return;
    }
    if(visit[start]==1)
    {
      //node which is already check
      return;
    }
    if( this.result==0)
    {

      visit[start]=1;
      AjlistNode  temp=node[start].next;
      while(temp!=null)
      {
        check_path(temp.id,end,visit); 
        temp=temp.next;
      }
    }

  }

  //Handling the execution of two nodes, 
  //And checking that two nodes are connected or not
  public void connection()
  {

    int status=1;
    this.result=1;
    int  []visit=new int[size];
    //first we are check, node 0 are connected or not to all other nodes
    DFS(0,visit);

    for (int i = 0; i < size; ++i)
    {
      if(visit[i]!=1)
      {
        //When not connect
        this.result=0;

        break;
      }
    }

    status=this.result;


    if(status==1)
    {
      //Check other nodes are capable to visit first node or not
      for (int i = 1; i < size && status==1; ++i)
      {
        this.result=0;

        for (int j = 0; j < size; ++j)
        {
          visit[j]=0;
        }

        //0 is first node i is other node
        check_path(i,0,visit);


        //get new modification
        status=result;
      }
    }

    if(status==1)
    {
      Console.WriteLine("\n Strongly Connected Graph");
    }else
    {
      Console.WriteLine("\n Not Strongly Connected Graph");
    }
  }
}
class Program
{

  static void Main(string[] args)
  {
    int totalNode=5;

    MyGraph g=new MyGraph(totalNode);

    g.setData();


    //Connected two node with Edges
    g.addEdge(0, 4); 
    g.addEdge(1, 0); 
    g.addEdge(1, 2); 
    g.addEdge(2, 1); 
    g.addEdge(2, 4); 
    g.addEdge(3, 1);  
    g.addEdge(3, 2); 
    g.addEdge(4, 3); 
    g.printGraph();
    g.connection();

  }
}

Output

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

<?php
class AjlistNode {
  public $id;
  public $next;
}
class Vertices {
  public $data;
  public $next;
}
class MyGraph {
  public $size;
  public $result;
  public $node;

  function __construct($size) {
    $this->size = $size;
    $this->node = [];
    $this->result = 0;
  }
  public  function setData() {
    if ($this->size <=0 ) {
      echo("\nEmpty Graph");
    } else {
      for ($index = 0; $index < $this->size; $index++) {
        $this->node[$index] = new Vertices();
        $this->node[$index]->data = $index;
        $this->node[$index]->next = null;
      }
    }
  }
  public  function connect($start, $end) {
    $newEdge = new AjlistNode();
    $newEdge->id = $end;
    $newEdge->next = null;
    if ($this->node[$start]->next == null) {
      $this->node[$start]->next = $newEdge;
    } else {
      $temp = $this->node[$start]->next;
      while ($temp->next != null) {
        $temp = $temp->next;
      }
      $temp->next = $newEdge;
    }
  }
  public  function addEdge($start, $end) {
    if ($start < $this->size && $end < $this->size && $this->node != null) {
      $this->connect($start, $end);
    } else {
      echo("\nInvalid nodes ". $start ." ". $end);
    }
  }
  public  function printGraph() {
    if ($this->size > 0 && $this->node != null) {
      for ($index = 0; $index < $this->size; $index++) {
        echo("\nAdjacency list of vertex ". $index ." :");
        $temp = $this->node[$index]->next;
        while ($temp != null) {
          echo(" ". $this->node[$temp->id]->data);
          $temp = $temp->next;
        }
      }
    }
  }

  function DFS($start, &$visit) {
    if ($start > $this->size || $start < 0 || $this->node == null) {
      return;
    }
    if ($visit[$start] == 1) {
      return;
    }
    $visit[$start] = 1;
    $temp = $this->node[$start]->next;
    while ($temp != null) {
      $this->DFS($temp->id, $visit);
      $temp = $temp->next;
    }
  }
  public  function check_path($start, $end, &$visit) {
    if ($start > $this->size || $end > $this->size || $start < 0 || $end < 0 || $this->node == null) {
      return;
    }
    if ($start == $end) {
      $visit[$start] = 1;
      $this->result = 1;
      return;
    }
    if ($visit[$start] == 1) {
      return;
    }
    if ($this->result == 0) {
      $visit[$start] = 1;
      $temp = $this->node[$start]->next;
      while ($temp != null) {
        $this->check_path($temp->id, $end, $visit);
        $temp = $temp->next;
      }
    }
  }
  public  function connection() {
    $status = 1;
    $this->result = 1;
    $visit = array_fill(0, $this->size, 0);
    $this->DFS(0, $visit);
    for ($i = 0; $i < $this->size; ++$i) {
      if ($visit[$i] != 1) {
        $this->result = 0;
        break;;
      }
    }
    $status = $this->result;
    if ($status == 1) {
      for ($i = 1; $i < $this->size && $status == 1; ++$i) {
        $this->result = 0;
        for ($j = 0; $j < $this->size; ++$j) {
          $visit[$j] = 0;
        }
        $this->check_path($i, 0, $visit);
        $status = $this->result;
      }
    }
    if ($status == 1) {
      echo("\n Strongly Connected Graph");
    } else {
      echo("\n Not Strongly Connected Graph");
    }
  }

}
function main() {
  $totalNode = 5;
  $g = new MyGraph($totalNode);
  $g->setData();
  $g->addEdge(0, 4);
  $g->addEdge(1, 0);
  $g->addEdge(1, 2);
  $g->addEdge(2, 1);
  $g->addEdge(2, 4);
  $g->addEdge(3, 1);
  $g->addEdge(3, 2);
  $g->addEdge(4, 3);
  $g->printGraph();
  $g->connection();
}
main();

Output

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