Bipartite Graph

Difficulty Level Medium
Frequently asked in Samsung
Breadth First Search Depth First Search Graph Graph ColoringViews 1722

A bipartite graph is a type of graph in which we divide the vertices of a graph into two sets. There are no edges between the vertices of the same set. Here in the bipartite_graph, the length of the cycles is always even. Basically, the sets of vertices in which we divide the vertices of a graph are called the part of a graph. Let’s see the example of Bipartite Graph.

Bipartite Graph

Here we can divide the nodes into 2 sets which follow the bipartite_graph property. Let say set containing 1,2,3,4 vertices is set X and set containing 5,6,7,8 vertices is set Y. We see clearly there are no edges between the vertices of the same set.

Note: Complete Bipartite graph is a special type of bipartite_graph in which every vertex of set X is connected to every vertex of set Y through an edge.

Properties of Bipartite Graph

  • It does not contain odd-length cycles.
  • It must be two colors.
  • Subgraphs of a given bipartite_graph are also a bipartite_graph.
  • Here, the Sum of the degree of vertices of set X is equal to the sum of vertices of set Y.
  • If we need to check the spectrum of the graph is symmetric then we check the graph is bipartite or not. If it is not a bipartite_graph then we can say that the spectrum of the graph is not symmetric.
  • A bipartite_graph consisting of N vertices can have at most (1/4)*N*N edges.

There are basically two ways to check the graph is bipartite or not:

  • Using BFS to check that graph is containing the odd-length cycle or not. If cycle with odd length found then we say its not a BG.
  • Using DFS to check the graph is 2 colorable or not. If it is two colorable then we say that graph is bipartite in nature.

Check Graph is Bipartite or not using BFS

Algorithm

Step:1 Make a graph using the adjacency list.
Step:2 For i in range 1 to N:
       a) If i is unvisited then:
             i) BFS(i).
             ii) If we found the odd-length cycle then we stop the process and print graph is not bipartite.

Check Graph is Bipartite or not using DFS

Algorithm

Step:1 Use color 0,1 to color the vertices.
Step:2 Call DFS(start).
Step:3 Assign the opposite color of the parent to the current node and call DFS to visit the neighbors of current node.
Step:4 If any step we find the color of two nodes connected by each other is same then we return false.
Step:5 If we visit all the nodes and don't find the color of two nodes connected by each other is same then we return true.

Implementation

/*C++ Implementation for check a graph is bipartite or not.*/ 
#include<bits/stdc++.h>
using namespace std;
/*function to check for graph is bipartite or not.*/
int check_biaprtite(int node,vector<int> v[],bool visited[],int assign[])
{
    /*visited all connected nodes to node*/
    for(int itr: v[node])
    {
        /*if connected node is unvisited then check_biaprtite*/
        if(!visited[itr])
        {
            visited[itr]=true;
            assign[itr]=!assign[node];
            if(!check_biaprtite(itr,v,visited,assign))
            {
                return 0;
            }
        }
        /*if two adjacent node have the same color then return false*/
        else if(assign[itr]==assign[node])
        {
            return 0;
        }
    }
    /*else return true*/
    return 1;
}
int main() 
{ 
    int nodes,edges;
    /*take inputs the value of node and edges*/
    cin>>nodes>>edges;
    vector<int> v[nodes+1];
    /*create undirected graph*/
    for(int i=0;i<edges;i++)
    {
        int x,y;
        cin>>x>>y;
        /*add edge between x -> y*/
        v[x].push_back(y);
        /*add edge between y -> x*/
        v[y].push_back(x);
    }
    bool visited[nodes+1];
    /*set all the nodes as unvisited*/
    memset(visited,false,sizeof(visited));
    int assign[nodes];
    int test;
    /*check for all the nodes in the graph*/
    for(int i=1;i<=nodes;i++)
    {
        /*if node is unvisited*/
        if(!visited[i])
        {
           visited[i]=true;
           assign[i]=0;
           /*check for this connected component*/
           test=check_biaprtite(i,v,visited,assign);
           /*if test is 1 then graph is not Bipartite*/
           if(test==1)
           {
               goto label;
           }
        }
    }
    label:;
    /*print the result*/
    if(test==1)
    {
        cout<<"Graph is Bipartite"<<endl;
    }
    else
    {
        cout<<"Graph is not Bipartite"<<endl;
    }
    return 0; 
}
8 6
1 6
6 3
3 8
5 2
2 7
7 4
Graph is Bipartite

Time Complexity

O(N+E) where N is the number of nodes and E is the number of edges. During creating graph we use O(N+E) time which is the maximum possible for the whole process.

Space Complexity

O(N+E) where N is the number of nodes and E is the number of edges. Creating the adjacency list we use maximum space which is O(N+E).

References

Translate ยป