In this article, we will explain how we can check if a given graph is bipartite or not in detail.

**Basic Terminologies**

**Bipartite Graph:**A simple graph G(V, E) is called Bipartite Graph if it’s vertices can be partitioned into two disjoint sets – V1 and V2, such that no edge connects vertices belonging to the same set ( or every edge in G connects a vertex in V1 and a vertex in V2).

**Algorithm**

The algorithm to check if a graph is bipartite or not is based on the fact that each node in the graph must be in set V1 or V2. It cannot be in V1 and V2 simultaneously.

We will use the DFS algorithm to traverse the graph and assign set V1 or V2 to each vertex. Suppose we are currently on vertex **a**. **a** is assigned set V1. Let **x** be a vertex adjacent to **a**. We have two situations.

- If
**x**is not visited, then we will mark**x**as visited and assign**x**to set V2. - If
**x**is already visited. Then we have to check if**x**belongs to set V1 or V2.- If
**x**belongs to set V2 then there is no problem. We simply continue with the algorithm. - If
**x**belongs to set V1 then there is a conflict. Vertex**a**and**x**are adjacent so they cannot be in same set. Therefore, the graph is not bipartite since we cannot divide the vertices in set V1 and V2 such that no adjacent vertices are in same set.

- If

**Program to check if a graph is bipartite using Depth First Search**

*Assumptions*

- The graph is undirected.
- The graph contains no self-loops.

#include <stdio.h> #include <iostream> #include <vector> using namespace std; bool dfs(int v, vector<vector<int>>& adj, vector<int>& setNum) { bool isBipartite = true; for (auto u : adj[v]) { // checking if u is assigned to any set or not if (setNum[u] == -1) { setNum[u] = 2 - (setNum[v] / 2); // the following statement put u to set 1 if v belongs to set 2 // if v belongs to set 1 then it assigns set 2 to u isBipartite = isBipartite && dfs(u, adj, setNum); } else { // this statement is executed if u already belongs to a set // in this case, we need to check if u and v belongs to different set or not // if they belongs to different set then we simple move to next children of v // if they belongs to different set then the graph is not bipartite. We simple return false if (setNum[u] == setNum[v]) { return false; } } } return isBipartite; } bool checkIfGraphIsBipartite(vector<vector<int>>& adj, int n) { vector<int> setNum(n, -1); // list to check to which set a node belongs to // -1 means the node is not assigned any set // 1 means the node belongs to set 1 // 2 means the node belongs to set 2 bool isBipartite = true; for (int i = 0; i < n; ++i) { if (setNum[i] == -1) { setNum[i] = 1; // putting vertex i in set 1 isBipartite = isBipartite && dfs(i, adj, setNum); } } return isBipartite; } void addEdge(vector<vector<int>>& adj, int v, int u) { adj[v].push_back(u); adj[u].push_back(v); } int main() { int n = 5; // number of vertices vector<vector<int>> adj(n); // adjacency list to store graph addEdge(adj, 0, 1); addEdge(adj, 2, 1); addEdge(adj, 3, 4); addEdge(adj, 2, 4); addEdge(adj, 1, 4); if (checkIfGraphIsBipartite(adj, n)) { cout << "Graph is Bipartite" << endl; } else { cout << "Graph is not Bipartite" << endl; } }

**Output**

Graph is not Bipartite --------------------------------

**Program to check if a graph is bipartite using Breadth First Search**

The logic is the same as in DFS. We will try to assign adjacent vertices to different sets. If we are able to partition the vertices into 2 sets, then the graph is bipartite otherwise the graph is not bipartite.

#include <stdio.h> #include <iostream> #include <vector> #include <stack> using namespace std; bool bfs(int v, vector<vector<int>>& adj, vector<int>& setNum) { bool isBipartite = true; stack<int> s; s.push(v); while(!s.empty()) { int p = s.top(); s.pop(); for (auto u : adj[p]) { if (setNum[u] == -1) { setNum[u] = 2 - (setNum[p] / 2); // the following statement put u to set 1 if p belongs to set 2 // if p belongs to set 1 then it assigns set 2 to u s.push(u); } else { // this statement is executed if u already belongs to a set // in this case, we need to check if u and p belongs to different set or not // if they belongs to different set then we simple move to next node in the stack // if they belongs to different set then the graph is not bipartite. We simple return false if (setNum[u] == setNum[p]) { return false; } } } } return isBipartite; } bool checkIfGraphIsBipartite(vector<vector<int>>& adj, int n) { vector<int> setNum(n, -1); // list to check to which set a node belongs to // -1 means the node is not assigned any set // 1 means the node belongs to set 1 // 2 means the node belongs to set 2 bool isBipartite = true; for (int i = 0; i < n; ++i) { if (setNum[i] == -1) { setNum[i] = 1; // putting vertex i in set 1 isBipartite = isBipartite && bfs(i, adj, setNum); } } return isBipartite; } void addEdge(vector<vector<int>>& adj, int v, int u) { adj[v].push_back(u); adj[u].push_back(v); } int main() { int n = 5; // number of vertices vector<vector<int>> adj(n); // adjacency list to store graph addEdge(adj, 0, 1); addEdge(adj, 2, 1); addEdge(adj, 3, 4); addEdge(adj, 2, 4); addEdge(adj, 1, 4); if (checkIfGraphIsBipartite(adj, n)) { cout << "Graph is Bipartite" << endl; } else { cout << "Graph is not Bipartite" << endl; } }

**Output**

Graph is not Bipartite --------------------------------