Using depth first search to test graph connectivity in C++

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

connect1

2. A disconnected directed graph. For example, node [1] can communicate with nodes [0,2,3] but not node [4]:

connect2

3. A connected un-directed graph. All nodes can communicate with any other node:

connect3

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:

connect4

5. A connected un-directed graph. All nodes can communicate with any other node:

connect5

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

connect6

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

Leave a Reply