Problem description
Given a directed or undirected graph, determine whether it is connected or not. Specifically is it possible for any pair of nodes to communicate with each other?
This brief post reproduces this web page whereby the problem was to determine whether a graph is strongly connected or not. I use a slight modification of Graph so that the user can define whether the graph consists of directed or undirected edges. When setting the directed parameter to false, the Graph class assumes that the edges are undirected, and so adds an additional link in the opposite direction to maintain bi-connectivity between edges (links).
The algorithm uses a depth-first search algorithm to test whether all the graph nodes get visited during the recursive search. For the purpose of brevity I have also removed a number of code comments, given that the code was fairly self-documenting to start with:
Example Graphs
1. A disconnected un-directed graph, whereby nodes [3,4] are disconnected from nodes [0,1,2]:
2. A disconnected directed graph. For example, node [1] can communicate with nodes [0,2,3] but not node [4]:
3. A connected un-directed graph. All nodes can communicate with any other node:
4. A disconnected directed graph. For example, node [0] can communicate with nodes [1,2,3] but node [3] cannot communicate with any other node:
5. A connected un-directed graph. All nodes can communicate with any other node:
6. A connected directed graph. All nodes can communicate with any other node. For example, although there is no direct link between nodes [0,3], a direct path between the two nodes still exists, via nodes [0,1,2,3].
Code listing
The following code listing shows how to implement each of the six examples listed above:
// Program to check if a given directed graph is strongly connected or not
#include <iostream>
#include <list>
#include <stack>
// Storage for visited nodes
bool visited[ 100000 ];
class Graph
{
int V; // No. of vertices
bool directed;
std::list<int> *adj; // An array of adjacency lists
// A recursive function to print DFS starting from v
void DFSUtil(int v, bool visited[]);
public:
// Constructor and Destructor
Graph(int V, bool directed)
{
this->V = V;
this->directed = directed;
adj = new std::list<int>[V];
}
~Graph() { delete [] adj; }
// Method to add an edge
void addEdge(int v, int w);
// The main function that returns true if the graph is strongly
// connected, otherwise false
bool isSC();
// Function that returns reverse (or transpose) of this graph
Graph* getTranspose();
};
// A recursive function to print DFS starting from v
void Graph::DFSUtil(int v, bool visited[])
{
// Mark the current node as visited and print it
visited[v] = true;
// Recur for all the vertices adjacent to this vertex
std::list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFSUtil(*i, visited);
}
// Function that returns reverse (or transpose) of this graph
Graph* Graph::getTranspose()
{
Graph* g = new Graph(V, directed);
for (int v = 0; v < V; v++)
{
// Recur for all the vertices adjacent to this vertex
std::list<int>::iterator i;
for(i = adj[v].begin(); i != adj[v].end(); ++i)
{
g->adj[*i].push_back(v);
}
}
return g;
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
if ( !directed) adj[w].push_back(v);
}
// The main function that returns true if graph is strongly connected
bool Graph::isSC()
{
// Step 1: Mark all the vertices as not visited (For first DFS)
for (int i = 0; i < V; i++)
visited[i] = false;
// Step 2: Do DFS traversal starting from first vertex.
DFSUtil(0, visited);
// If DFS traversal doesn’t visit all vertices, then return false.
for (int i = 0; i < V; i++)
if (visited[i] == false)
return false;
// Step 3: Create a reversed graph
Graph* gr = getTranspose();
// Step 4: Mark all the vertices as not visited (For second DFS)
for(int i = 0; i < V; i++)
visited[i] = false;
// Step 5: Do DFS for reversed graph starting from first vertex.
// Starting Vertex must be same starting point of first DFS
gr->DFSUtil(0, visited);
// If all vertices are not visited in second DFS, then
// return false
for (int i = 0; i < V; i++)
if (visited[i] == false)
return false;
return true;
}
// Driver program to test above functions
int main()
{
// Example 1: disconnected un-directed graph:
//
// 0 3
// / \ /
// 1 2 4
// nodes [3,4] disconnected from nodes [0,1,2]
Graph g1( 5, false );
g1.addEdge(0, 1);
g1.addEdge(0, 2);
g1.addEdge(3, 4);
g1.isSC() ? std::cout << "Yes\n" :
std::cout << "No\n";
// Example 2: disconnected (directed) graph:
//
// 3 <- 2 <- 1 -> 0 <- 4
// eg 1 can communicate with [2,3,0] but not 4
Graph g2( 5, true );
g2.addEdge(1, 0);
g2.addEdge(4, 0);
g2.addEdge(1, 2);
g2.addEdge(2, 3);
g2.isSC() ? std::cout << "Yes\n" :
std::cout << "No\n";
// Example 3: connected (un-directed) graph:
//
// 3 <-> 2 <-> 1 <-> 0 <-> 4
// All nodes can communicate with any other node
Graph g3( 5, false );
g3.addEdge(1, 0);
g3.addEdge(4, 0);
g3.addEdge(1, 2);
g3.addEdge(2, 3);
g3.isSC() ? std::cout << "Yes\n" :
std::cout << "No\n";
// Example 4: disconnected (directed) graph
//
// 0 -> 1 -> 2 -> 3
// 0 can communicate with [1,2,3] but 3 cannot communicate
// with any other node
Graph g4( 4, true );
g4.addEdge(0, 1);
g4.addEdge(1, 2);
g4.addEdge(2, 3);
g4.isSC() ? std::cout << "Yes\n" :
std::cout << "No\n";
// Example 5: connected (un-directed) graph
//
// 0 <-> 1 <-> 2 <-> 3
// All nodes can communicate with any other node
Graph g5( 4, false );
g5.addEdge(0, 1);
g5.addEdge(1, 2);
g5.addEdge(2, 3);
g5.isSC() ? std::cout << "Yes\n" :
std::cout << "No\n";
// Example 6: connected directed graph
//
// 0 -> 1 -> 2 -> 3 -> 0
//
// 4 -> 2 -> 4
// All nodes can communicate with any other node
Graph g6( 5, true );
g6.addEdge(0, 1);
g6.addEdge(1, 2);
g6.addEdge(2, 3);
g6.addEdge(3, 0);
g6.addEdge(2, 4);
g6.addEdge(4, 2);
g6.isSC() ? std::cout << "Yes\n" :
std::cout << "No\n";
return 0;
}
Giving the following output:
No
No
Yes
No
Yes
Yes