Introduction
In this article, we will learn about the bipartite graph. A bipartite graph, also called a bigraph, is a set of graph vertices decomposed into two disjoint sets such that no two graph vertices within the same set are adjacent. Remember Adjacent nodes are any two nodes that are connected by an edge.
You can understand a bipartite graph this way also: A bipartite graph is possible if the graph coloring is possible using two colors such that vertices in a set are colored with the same color.
In technical interviews, we are generally given questions where we need to check whether the given graph is bipartite or not. So let’s move to this part now:
Algorithm to check if the Graph is Bipartite or not
- Assign a RED color to the source vertex (putting into set U).
- Color all the neighbors with BLUE color (putting into set V).
- Color all neighbor’s neighbors with RED color (putting into set U).
- This way, assign a color to all vertices such that it satisfies all the constraints of the m-way coloring problem where m = 2.
- While assigning colors, if we find a neighbor which is colored with the same color as the current vertex, then the graph cannot be colored with 2 vertices (or the graph is not Bipartite).
#include <iostream>
#include <queue>
#define V 4
using namespace std;
// This function returns true if graph
// G[V][V] is Bipartite, else false
bool isBipartite(int G[][V], int src)
{
// Create a color array to store colors
// assigned to all veritces. Vertex
// number is used as index in this array.
// The value '-1' of colorArr[i]
// is used to indicate that no color
// is assigned to vertex 'i'. The value 1
// is used to indicate first color
// is assigned and value 0 indicates
// second color is assigned.
int colorArr[V];
for (int i = 0; i < V; ++i)
colorArr[i] = -1;
// Assign first color to source
colorArr[src] = 1;
// Create a queue (FIFO) of vertex
// numbers and enqueue source vertex
// for BFS traversal
queue <int> q;
q.push(src);
// Run while there are vertices
// in queue (Similar to BFS)
while (!q.empty())
{
// Dequeue a vertex from queue ( Refer http://goo.gl/35oz8 )
int u = q.front();
q.pop();
// Return false if there is a self-loop
if (G[u][u] == 1)
return false;
// Find all non-colored adjacent vertices
for (int v = 0; v < V; ++v)
{
// An edge from u to v exists and
// destination v is not colored
if (G[u][v] && colorArr[v] == -1)
{
// Assign alternate color to this adjacent v of u
colorArr[v] = 1 - colorArr[u];
q.push(v);
}
// An edge from u to v exists and destination
// v is colored with same color as u
else if (G[u][v] && colorArr[v] == colorArr[u])
return false;
}
}
// If we reach here, then all adjacent
// vertices can be colored with alternate color
return true;
}
//Program to test above function
int main()
{
int G[][V] = {{0, 1, 0, 1},
{1, 0, 1, 0},
{0, 1, 0, 1},
{1, 0, 1, 0}
};
isBipartite(G, 0) ? cout << "Yes, the graph is Bipartite" : cout << "No, the graph is not Bipartite";
return 0;
} |
Output:
Time Complexity: If V is the number of vertices and E is the number of edges, then the time complexity of a graph represented using an adjacency list will be:
O(V+E)
Now, one more bonus is here! We can check the bipartite-ness of a graph by using the DFS algorithm also.
Using DFS
// C++ program to find out whether a given graph is Bipartite or not.
// Using recursion.
#include <iostream>
using namespace std;
#define V 4
bool colorGraph(int G[][V],int color[],int pos, int c){
if(color[pos] != -1 && color[pos] !=c)
return false;
// color this pos as c and all its neighbours and 1-c
color[pos] = c;
bool ans = true;
for(int i=0;i<V;i++){
if(G[pos][i]){
if(color[i] == -1)
ans &= colorGraph(G,color,i,1-c);
if(color[i] !=-1 && color[i] != 1-c)
return false;
}
if (!ans)
return false;
}
return true;
}
bool isBipartite(int G[][V]){
int color[V];
for(int i=0;i<V;i++)
color[i] = -1;
//start is vertex 0;
int pos = 0;
// two colors 1 and 0
return colorGraph(G,color,pos,1);
}
int main()
{
int G[][V] = {{0, 1, 0, 1},
{1, 0, 1, 0},
{0, 1, 0, 1},
{1, 0, 1, 0}
};
isBipartite(G) ? cout<< "Yes" : cout << "No";
return 0;
} |
Output:
Time Complexity: O(V+E)
Auxiliary Space: O(V)
Now you must be wondering what is the use of a Bipartite graph.
Applications of bipartite graphs
- The bipartite graph can be used in the medical field in the detection of lung cancer, throat cancer, etc.
- Used in search advertising and e-commerce for similarity ranking.
- Predict the movie preferences of a person.
- Stable marriage6 and other matching problems.