C++ Program to Check the Connectivity of Directed Graph Using BFS

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

Here is source code of the C++ Program to Check the Connectivity of Directed Graph Using BFS. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/*
```

 * C++ Program to Check whether Undirected Graph is Connected 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;
```
```
}
```

Output:

$ g++ ConnectivityUsingBFSDiredctedGraph.cpp
$ a.out
 
The Graph 1 is not Connected
The Graph 2 is Connected
 
------------------
(program exited with code: 0)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

« Prev - C++ Program to Find the Connected Components in an UnDirected Graph

» Next - C++ Program to Implement Dijkstra’s Algorithm using Queue

Related Posts:

Recommended Articles: