If a graph’s node can be divided into two disjoint sets so that every edge connects two nodes of different sets then this graph is a bipartite graph. In another way, if a graph is bi-colorable then this is a bipartite graph.
To check if a graph is bipartite or not, we can use any graph traversal algorithm like BFS and DFS.
In this blog, we will use DFS. If you don’t know DFS, read Depth First Search Algorithm (DFS). Previously we used 2 colors 0 and 1. 0 is for unvisited and 1 is for visited nodes.
In this problem, we will use 3 colors 0, 1, and 2. 0 is for unvisited nodes. 1 and 2 for visited nodes. At first, we will take any node and color it with any color. Then we will color adjacent nodes to alternate colors. If we can color all the nodes then it is bipartite otherwise it is not a bipartite graph.
Bipartite Graph checking C++
#include<bits/stdc++.h>
using namespace std;
vector<vector<int> > adj;
vector<int> visited;
int dfs(int r, int c)
{
visited[r]=c;
int nc;
if(c==1) nc=2;
else nc=1;
for(auto it:adj[r])
{
if(visited[it]==0)
{
if(dfs(it, nc)==0) return 0;
}
else
{
if(visited[it]!=nc) return 0;
}
}
return 1;
}
int main()
{
int n,m;
cin>>n; // n is the number of vertices
cin>>m; // m is the number of edges
adj.resize(n); // n vector for each node
// input edgelist
for(int i=0;i<m;i++)
{
int a, b;
cin>>a>>b;
adj[a].push_back(b);
adj[b].push_back(a);
}
visited.resize(n);
if(dfs(0, 1))
{
cout<<"Bipartite graph"<<endl;
return 0;
}
else
{
cout<<"Not bipartite graph"<<endl;
return 0;
}
return 0;
}
The code you provided is an implementation of the depth-first search algorithm to check whether a given graph is bipartite or not. A bipartite graph is a graph in which the vertices can be divided into two disjoint sets such that no two vertices within the same set are adjacent.
The code first takes the number of vertices and the number of edges as input. Then, it creates an adjacency list for the given graph. The input edgelist is taken from the user and stored in the adjacency list.
The code then initializes a vector called visited which stores whether a node is visited or not. The code starts the depth-first search from the first vertex (0) and assigns color 1 to it. If the current vertex is assigned color 1, it assigns color 2 to its neighbors. If the current vertex is assigned color 2, it assigns color 1 to its neighbors. This process is continued recursively until all vertices are visited.
If, during the traversal, the current vertex’s neighbor is already visited and has the same color as the current vertex, the graph is not bipartite. In this case, the function dfs returns 0. If all the vertices are visited without any conflicts, the function dfs returns 1, indicating that the graph is bipartite.
Finally, the main function checks the output of the dfs function. If it returns 1, the graph is bipartite. Otherwise, the graph is not bipartite.
Bipartite Graph checking Python
adj=[]
n=int(input()) # number of vertices.
m=int(input()) # number of edges
for i in range(n):
adj.append([])
# input edge list.
for i in range(m):
a, b=map(int, input().split())
adj[a].append(b)
adj[b].append(a)
visited=[]
for i in range(n):
visited.append(0)
def dfs(r, c):
global visited, adj
visited[r]=c
nc=1
if c==1:
nc=2
for i in adj[r]:
if visited[i]==0:
if dfs(i, nc)==0:
return 0
elif visited[i]!=nc:
return 0
return 1
if dfs(0, 1):
print("Bipartite graph")
else:
print("Not Bipartite graph")
The Python code you provided looks good and implements the same logic as the C++ code for checking whether a given graph is bipartite or not. The only difference is that it is written in Python instead of C++.
The Python code first reads in the number of vertices and edges, creates an adjacency list to represent the graph, and then performs a depth-first search on the graph to color the vertices with two colors, such that no two adjacent vertices have the same color. If it is possible to color all the vertices in this way, the graph is bipartite; otherwise, it is not.
