C++ Program to Check whether a Graph is Bipartite using BFS

This C++ Program checks whether Graph is a Bipartite using BFS

Here is source code of the C++ Program to check whether Graph is a Bipartite 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 Graph is a Bipartite using BFS

```
 */
```
```
#include <iostream>
```
```
#include <queue>
```
```
#define V 4
```
```
using namespace std;
```
```
 
```
```
/* 
```

 * Returns true if graph G[V][V] is Bipartite

```
 */
```
```
bool isBipartite(int G[][V], int src)
```
```
{
```
```
    int colorArr[V];
```
```
    for (int i = 0; i < V; ++i)
```
```
        colorArr[i] = -1;
```
```
    colorArr[src] = 1;
```
```
    queue <int> q;
```
```
    q.push(src);
```
```
    while (!q.empty())
```
```
    {
```
```
        int u = q.front();
```
```
        q.pop();
```
```
	for (int v = 0; v < V; ++v)
```
```
        {
```

            if (G[u][v] && colorArr[v] == -1)

```
            {
```

                colorArr[v] = 1 - colorArr[u];

```
                q.push(v);
```
```
            }
```

            else if (G[u][v] && colorArr[v] == colorArr[u])

```
                return false;
```
```
        }
```
```
    }
```
```
    return true;
```
```
}
```
```
 
```
```
/* 
```
```
 * Main Contains Menu 
```
```
 */
```
```
int main()
```
```
{
```
```
    int G[][V] = {{0, 1, 0, 1},
```
```
        {1, 0, 1, 0},
```
```
        {0, 1, 0, 1},
```
```
        {1, 0, 1, 0}
```
```
    };
```
```
    if (isBipartite(G, 0)) 
```

        cout << "The Graph is Bipartite"<<endl;

```
    else
```

        cout << "The Graph is Not Bipartite"<<endl;

```
    return 0;
```
```
}
```

$ g++ bipartite_bfs.cpp
$ a.out
The Graph is Bipartite
 
 
------------------
(program exited with code: 1)
Press return to continue

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

If you wish to look at all C++ Programming examples, go to C++ Programs.

« Prev - C++ Program to Check whether a Graph is Bipartite using 2 Color Algorithm

» Next - C++ Program to Check whether a Graph is Bipartite using DFS

Related Posts:

Recommended Articles: