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