What is Strongly Connected Graph? How To Detect Strongly Connected Graph Using C++
What is Graph?
In computer science, a graph is an abstract data type that is meant to implement the undirected graph and directed graph concepts from the field of graph theory within mathematics.
A graph is a pictorial representation of a set of objects where some pairs of objects are connected by links. The interconnected objects are represented by points termed as vertices, and the links that connect the vertices are called edges.
Types of Graph
There are two types of graph. They are:
- Directed Graph
- Undirected Graph
Directed Graph
A directed graph (or digraph) is a set of vertices and a collection of directed edges that each connects an ordered pair of vertices. We say that a directed edge points from the first vertex in the pair and points to the second vertex in the pair.
Undirected Graph
An undirected graph is graph that are connected together, where all the edges are bidirectional. An undirected graph is sometimes called an undirected network. In undirected graph edges don’t have a specific direction. So it is called undirected graph.
What is Strongly Connected Graph?
A graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of an arbitrary directed graph form a partition into subgraphs that are themselves strongly connected.
A directed graph is called strongly connected if there is a path in each direction between each pair of vertices of the graph. That is, a path exists from the first vertex in the pair to the second, and another path exists from the second vertex to the first.
Normally a strongly connected graph is considered in case of Directed graph only. Because in undirected graphs every node can be visit if they are connected as a graph.
What is Strongly Connected Component?
In a graph if there is any part which are strongly connected is called strongly connected component. In a strongly connected there may have one or more strongly connected component. In a graph which is not strongly connected may have one or more strongly connected component as well.
How to Know Whether a Graph is Strongly Connected?
To know whether a graph is strongly connected or not you need to check for each node. Check each node whether they can travel all other node directly or indirectly. If all node can travel all other nodes then the graph is said to be strongly connected.
In programming we need to know Path Matrix to detect strongly connected graph. Path matrix can be derived using Warshal Algorithm. To derive path matrix we need to know the adjacency matrix.
What is Adjacency Matrix?
An adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In adjacency matrix row means where the edge from and column means where the edge end. If there is value 0 in column – 3 and row – 2 that means there is no edge from node – 2 to node – 3.
What is Path Matrix?
A path matrix is a matrix representing a graph where each value in m’th row and n’th column project whethere there is a path from m to n. The path may be direct or indirect. It may have a single edge or multiple edge.
C++ Code To Find Path Matrix From Adjacency Matrix
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main(){ //Main Function
int m,i,j,k;
//m is Number of Vertices or Point
//i,j,k is normal integer to forward loop
cout<<"Number of Vertics will be: ";
cin>>m;
long A[m][m],A2[m][m],A3[m][m],A4[m][m],B4[m][m],P[m][m];
//A is name of Adjacency Matrix
//A2,A3,A4 are square,cube and quadric
//B4 are the sum of matrices from A to A4
//For loop to take input the Adjacency Matrix
cout<<"Enter the Adjacency Matrix Below in "<<m<<"x"<<m<<" size:"<<endl;
for(i=0;i<m;i++){
for(j=0;j<m;j++){
cin>>A[i][j];
}
}
cout<<endl;
//Finding A2 or AxA
for(i=0;i<m;i++){
for(j=0;j<m;j++){
A2[i][j]=0;
for(k=0;k<m;k++){
A2[i][j]=A2[i][j]+A[i][k]*A[k][j];
}
}
}
//Finding A3 or AxAxA
for(i=0;i<m;i++){
for(j=0;j<m;j++){
A3[i][j]=0;
for(k=0;k<m;k++){
A3[i][j]=A3[i][j]+A2[i][k]*A[k][j];
}
}
}
//Finding A4 or AxAxAxA
for(i=0;i<m;i++){
for(j=0;j<m;j++){
A4[i][j]=0;
for(k=0;k<m;k++){
A4[i][j]=A4[i][j]+A2[i][k]*A2[k][j];
}
}
}
//Finding B4 or A+A2+A3+A4 and printing B4
cout<<"Br :"<<endl;
for(i=0;i<m;i++){
for(j=0;j<m;j++){
B4[i][j]=A[i][j]+A2[i][j]+A3[i][j]+A4[i][j];
if(B4[i][j]!=0)P[i][j]=1; //Finding path matrix
else{
P[i][j]=0;
}
cout<<B4[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
//Printing Path Matrix
cout<<"Path Matrix :"<<endl;
for(i=0;i<m;i++){
for(j=0;j<m;j++){
cout<<P[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
return 0;
}
C++ Code to Find Strongly Connected Graph
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main(){ //Main Function
int m,i,j,k,counter=0;
//m is Number of Vertices or Point
//i,j,k is normal integer to forward loop
//counter is an integer which will count the number of zero in path matrix
cout<<"Number of Vertics will be: ";
cin>>m;
long A[m][m],A2[m][m],A3[m][m],A4[m][m],B4[m][m],P[m][m];
//A is name of Adjacency Matrix
//A2,A3,A4 are square,cube and quadric
//B4 are the sum of matrices from A to A4
//For loop to take input the Adjacency Matrix
cout<<"Enter the Adjacency Matrix Below in "<<m<<"x"<<m<<" size:"<<endl;
for(i=0;i<m;i++){
for(j=0;j<m;j++){
cin>>A[i][j];
}
}
cout<<endl;
//Finding A2 or AxA
for(i=0;i<m;i++){
for(j=0;j<m;j++){
A2[i][j]=0;
for(k=0;k<m;k++){
A2[i][j]=A2[i][j]+A[i][k]*A[k][j];
}
}
}
//Finding A3 or AxAxA
for(i=0;i<m;i++){
for(j=0;j<m;j++){
A3[i][j]=0;
for(k=0;k<m;k++){
A3[i][j]=A3[i][j]+A2[i][k]*A[k][j];
}
}
}
//Finding A4 or AxAxAxA
for(i=0;i<m;i++){
for(j=0;j<m;j++){
A4[i][j]=0;
for(k=0;k<m;k++){
A4[i][j]=A4[i][j]+A2[i][k]*A2[k][j];
}
}
}
//Finding B4 or A+A2+A3+A4 and printing B4
cout<<"Br :"<<endl;
for(i=0;i<m;i++){
for(j=0;j<m;j++){
B4[i][j]=A[i][j]+A2[i][j]+A3[i][j]+A4[i][j];
if(B4[i][j]!=0)P[i][j]=1; //Finding path matrix and checking zero in path matrix
else{
P[i][j]=0;
counter++;
}
cout<<B4[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
//Printing Path Matrix
cout<<"Path Matrix :"<<endl;
for(i=0;i<m;i++){
for(j=0;j<m;j++){
cout<<P[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
//Checking if strongly connecting or not from checking counter from line 68-71
if(counter!=0)cout<<"This is not Strongly Connected."<<endl;
else cout<<"This is Strongly Connected."<<endl;
cout<<endl;
return 0;
}
Hope you like the tutorial. If you have any confusion please comment. Comment what do you feel about this tutorial. Subscribe for latest posts.