What is a Bipartite Graph?

A Bipartite Graph is a graph whose vertices can be divided into two sets such that no two vertices within the same set are adjacent. In other words, it is a graph that can be coloured with only two colors such that no two adjacent vertices have the same colour.
Bipartite graphs are widely used in various applications such as matching problems, scheduling, and resource allocation. They are also used in various fields of science and engineering, such as genetics, computer science, and operations research.

Example

Problem statement

Given a graph G, check whether it’s a Bipartite graph or not.

Pseudocode

isBipartite (G)

1. Initialise a boolean array visited (to mark nodes as visited) and an integer array colour (to mark the colour of nodes).
2. Perform DFS (Depth-First Search) on graph G.
3. Iterate through all the adjacent vertices of the current node.
4. If the adjacent vertex v has been visited before and has the same colour as the current node, return false. This means that the graph is not Bipartite. (Explanation is below)
5. If all the adjacent vertices have been visited and assigned different colors, return true. This means that the graph is Bipartite.

Explanation

Why visiting a node that has been visited before and has the same colour as the current node means graph is not Bipartite?
It is because if a vertex has already been visited and has the same colour as the current vertex, it means that there is an odd-length cycle in the graph, and hence the graph cannot be Bipartite.

In general, if we encounter an odd-length cycle in the graph during the depth-first search, we can be sure that the graph is not Bipartite. This is because in a Bipartite graph, all cycles have an even length. So, if we find an odd-length cycle, it must mean that the graph cannot be coloured with two colors without any adjacent vertices having the same colour.

Code Implementation

//
//  main.cpp
//  Bipartite Graph
//
//  Created by Himanshu on 25/02/23.
//

#include <iostream>
#include <vector>
#include <cstring>
#define N 6
using namespace std;

vector<int> graphFirst[N+1];
vector<int> graphSecond[N+1];

int color[N+1];
bool visited[N+1];

void intializeGraphs() {
    
    graphFirst[1].push_back(2);
    graphFirst[2].push_back(1);
    graphFirst[2].push_back(3);
    graphFirst[2].push_back(4);
    graphFirst[3].push_back(2);
    graphFirst[3].push_back(4);
    graphFirst[4].push_back(2);
    graphFirst[4].push_back(3);
    graphFirst[4].push_back(5);
    graphFirst[4].push_back(6);
    graphFirst[5].push_back(4);
    graphFirst[6].push_back(4);
    
    graphSecond[1].push_back(2);
    graphSecond[1].push_back(4);
    graphSecond[2].push_back(1);
    graphSecond[2].push_back(5);
    graphSecond[3].push_back(6);
    graphSecond[4].push_back(1);
    graphSecond[5].push_back(2);
    graphSecond[5].push_back(6);
    graphSecond[6].push_back(3);
    graphSecond[6].push_back(5);
    
}

bool dfs(vector<int> graph[], int node, int c) {
    
    visited[node] = true;
    color[node] = c;
    
    for (int i=0; i<graph[node].size(); i++) {
        
        int v = graph[node][i];
        
        if (!visited[v]) {
            if (!dfs(graph, v, ~c)) {
                return false;
            }
        } else if (color[node]==color[v]) {
            return false;
        }
    }
    
    return true;
}

bool isGraphBipartite(vector<int> graph[]) {
    
    bool flag = true;
    
    for (int i=1; i<=N; i++){
        if (!visited[i]){
            if (!dfs(graph, i, 0)) {
                flag = false;
                break;
            }
        }
    }
    
    return flag;
}

int main() {
    
    intializeGraphs();
    
    if (isGraphBipartite(graphFirst)) {
        cout<<"graphFirst is Bipartite"<<endl;
    } else {
        cout<<"graphfirst is not Bipartite"<<endl;
    }

    memset(visited, false, sizeof visited);
    memset(color, 0, sizeof visited);
    
    if (isGraphBipartite(graphSecond)) {
        cout<<"graphSecond is Bipartite"<<endl;
    } else {
        cout<<"graphSecond is not Bipartite"<<endl;
    }
    
    return 0;
}

Output

graphfirst is not Bipartite
graphSecond is Bipartite

Time complexity: O(V + E), where V is the number of vertices and E is the number of edges in the graph.
Traversing Graph (G) using DFS (Depth-First search), we visit each vertex only once, and we visit each edge at most twice (once for each of its endpoints). Therefore, the total time complexity of the algorithm is proportional to the sum of the number of vertices and edges in the graph.