C++ Programming Code Examples

C++ > Computer Graphics Code Examples

Program to Check Whether a Graph is Strongly Connected or Not

Program to Check Whether a Graph is Strongly Connected or Not

This is a C++ Program to check whether given graph is strongly connected or not. If there exists multiple strongly connected component, graph is not strongly connected, it is otherwise.

    // Implementation of Kosaraju's algorithm to print all SCCs

    #include <iostream>

    #include <list>

    #include <stack>

    using namespace std;

    class Graph

    {

            int V; // No. of vertices

            list<int> *adj; // An array of adjacency lists

            // Fills Stack with vertices (in increasing order of finishing times)

            // The top element of stack has the maximum finishing time

            void fillOrder(int v, bool visited[], stack<int> &Stack);

            // A recursive function to print DFS starting from v

            void DFSUtil(int v, bool visited[]);

        public:

            Graph(int V);

            void addEdge(int v, int w);

            // The main function that finds and prints strongly connected components

            int printSCCs();

            // Function that returns reverse (or transpose) of this graph

            Graph getTranspose();

    };

    Graph::Graph(int V)

    {

        this->V = V;

        adj = new list<int> [V];

    }

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

        cout << v << " ";

        // Recur for all the vertices adjacent to this vertex

        list<int>::iterator i;

        for (i = adj[v].begin(); i != adj[v].end(); ++i)

            if (!visited[*i])

                DFSUtil(*i, visited);

    }

    Graph Graph::getTranspose()

    {

        Graph g(V);

        for (int v = 0; v < V; v++)

        {

            // Recur for all the vertices adjacent to this vertex

            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); // Add w to v's list.

    }

    void Graph::fillOrder(int v, bool visited[], stack<int> &Stack)

    {

        // Mark the current node as visited and print it

        visited[v] = true;

        // Recur for all the vertices adjacent to this vertex

        list<int>::iterator i;

        for (i = adj[v].begin(); i != adj[v].end(); ++i)

            if (!visited[*i])

                fillOrder(*i, visited, Stack);

        // All vertices reachable from v are processed by now, push v to Stack

        Stack.push(v);

    }

    // The main function that finds and prints all strongly connected components

    int Graph::printSCCs()

    {

        stack<int> Stack;

        // Mark all the vertices as not visited (For first DFS)

        bool *visited = new bool[V];

        for (int i = 0; i < V; i++)

            visited[i] = false;

        // Fill vertices in stack according to their finishing times

        for (int i = 0; i < V; i++)

            if (visited[i] == false)

                fillOrder(i, visited, Stack);

        // Create a reversed graph

        Graph gr = getTranspose();

        // Mark all the vertices as not visited (For second DFS)

        for (int i = 0; i < V; i++)

            visited[i] = false;

        int count = 0;

        // Now process all vertices in order defined by Stack

        while (Stack.empty() == false)

        {

            // Pop a vertex from stack

            int v = Stack.top();

            Stack.pop();

            // Print Strongly connected component of the popped vertex

            if (visited[v] == false)

            {

                gr.DFSUtil(v, visited);

                cout << endl;

            }

            count++;

        }

        return count;

    }

    // Driver program to test above functions

    int main()

    {

        // Create a graph given in the above diagram

        Graph g(5);

        g.addEdge(1, 0);

        g.addEdge(0, 2);

        g.addEdge(2, 1);

        g.addEdge(0, 3);

        g.addEdge(3, 4);

        cout << "Following are strongly connected components in given graph \n";

        g.printSCCs();

        return 0;

    }