## C++ Program to Check whether Graph is a Bipartite using DFS Full Project For Beginners

• Post author:
• Post category:c++

`main.cpp`

``````/*
* C++ Program to Check whether Graph is a Bipartite using DFS
*/
#include <iostream>
#include <cstdio>
#include <stack>
#include <list>
using namespace std;
/*
* Class Declaration
*/
class Graph
{
public:
int V;
Graph(int V);
};
/*
* Constructor
*/
Graph::Graph(int V)
{
this->V = V;
}
/*
*/
{
}
/*
* Class Bipartite Declaration
*/
class Bipartite
{
private:
bool isBipartite;
bool *color;
bool *marked;
int *edgeTo;
stack<int> cycle;
public:
Bipartite(Graph G)
{
isBipartite = true;
color = new bool [G.V];
marked = new bool [G.V];
edgeTo = new int [G.V];
for (int v = 0; v < G.V; v++)
{
if (!marked[v])
{
color[v] = false;
dfs(G, v);
}
}
}
/*
* DFS
*/
void dfs(Graph G, int v)
{
marked[v] = true;
list<int>::iterator w;
{
if (!cycle.empty())
return;
if (!marked[*w])
{
edgeTo[*w] = v;
color[*w] = !color[v];
dfs(G, *w);
}
else if (color[*w] == color[v])
{
isBipartite = false;
cycle.push(*w);
for (int x = v; x != *w; x = edgeTo[x])
{
cycle.push(x);
}
cycle.push(*w);
}
}
}
/*
* Returns true if graph is Bipartite
*/
bool isBi()
{
return isBipartite;
}
};

/*
*/
int main()
{
Graph g1(4);