C++ Programming Code Examples

C++ > Computer Graphics Code Examples

Program to Check the Connectivity of Directed Graph Using BFS



Program to Check the Connectivity of Directed Graph Using BFS

This is a C++ Program to check the connectivity of directed graph using BFS.

    #include <iostream>

    #include <list>

    #include <queue>

    using namespace std;

    /* Class Declaration     */

    class Graph

    {

        private:

            int V;

            list<int> *adj;

        public:

            Graph(int V)

            {

                this->V = V;

                adj = new list<int> [V];

            }

            void addEdge(int v, int w);

            void BFS(int s, bool visited[]);

            Graph getTranspose();

            bool isConnected();

    };

    /* Add Edge to connect v and w     */

    void Graph::addEdge(int v, int w)

    {

        adj[v].push_back(w);

        //adj[w].push_back(v);

    }

    /* A recursive function to print BFS starting from s     */

    void Graph::BFS(int s, bool visited[])

    {

        list<int> q;

        list<int>::iterator i;

        visited[s] = true;

        q.push_back(s);

        while (!q.empty())

        {

            s = q.front();

            q.pop_front();

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

            {

                if (!visited[*i])

                {

                    visited[*i] = true;

                    q.push_back(*i);

                }

            }

        }

    }

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

    Graph Graph::getTranspose()

    {

        Graph g(V);

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

        {

            list<int>::iterator i;

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

            {

                g.adj[*i].push_back(v);

            }

        }

        return g;

    }

    /* Check if Graph is Connected     */

    bool Graph::isConnected()

    {

        bool visited[V];

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

            visited[i] = false;

        BFS(0, visited);

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

            if (visited[i] == false)

                return false;

        Graph gr = getTranspose();

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

            visited[i] = false;

        gr.BFS(0, visited);

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

            if (visited[i] == false)

                return false;

        return true;

    }

    /* Main Contains Menu     */

    int main()

    {

        Graph g(4);

        g.addEdge(0, 1);

        g.addEdge(0, 2);

        g.addEdge(1, 2);

        g.addEdge(2, 3);

        g.addEdge(3, 3);

        if (g.isConnected())

            cout << "The Graph 1 is Connected" << endl;

        else

            cout << "The Graph 1 is not Connected" << endl;

        Graph g1(5);

        g1.addEdge(0, 1);

        g1.addEdge(1, 2);

        g1.addEdge(2, 3);

        g1.addEdge(3, 0);

        g1.addEdge(2, 4);

        g1.addEdge(4, 2);

        if (g1.isConnected())

            cout << "The Graph 2 is Connected" << endl;

        else

            cout << "The Graph 2 is not Connected" << endl;

        return 0;

    }