Do you think IIT Guwahati certified course can help you in your career?
No
Introduction
Graphs are non-linear Data Structure composed of nodes and edges. There are different types of graphs like directed graphs, undirected graphs, Euler graphs, hamiltonian graphs, etc. One of them is a Bipartite graph.
In this article, we will learn everything about Bipartite graphs in one of the simplest ways. We will start with a quick definition of bipartite graphs, their properties, and examples. Our primary focus will be to understand an algorithm to check whether a graph is bipartite, along with its analysis in terms of time and space complexity.
What is a Bipartite Graph?
Bipartite graphs or Bi-graphs are a type of graph where all of the vertices are divided into two independent groups, U and V, such that each edge [u,v] in the graph connects a vertex u from set U and a vertex v from set V. In other words, none of the edges connects two vertices from the same set.
Example of a bipartite graph
Let's see an example of a bipartite graph -
The above graph is undirected, in which every edge connects one vertex of blue color and the other vertex of green color. The two colors represent two different sets. For instance, see the edge [E, F], E is green while F is blue. Similarly, other edges also like [A, E], [A, B], [E, H],[H, G],[G, C], [D, C], [B, C], etc.
We can also see the mapping below to get a clear picture as to why the above graph is an example of a bipartite graph -
1. Balanced Bipartite: If both the sets of vertices in a bipartite graph have an equal number of vertices or, in other words, have equal cardinality, then the graph is called balanced bipartite.
2. Complete Bipartite: A bipartite graph is said to be complete if all the vertices in set-1 are connected to every vertex of set-2. So, if set-1 has m vertices and set-2 has n vertices, then the total number of edges will be - m*n.
Characteristics of Bipartite Graph
There are several characteristics of a Bipartite Graph:
Two Sets of Vertices A bipartite graph has two disjoint vertex sets, with edges only between vertices in different sets, never within the same set.
No Odd-Length Cycles A graph is bipartite if and only if it contains no odd-length cycles, as such cycles would imply connections within the same set.
Two-Colorable Bipartite graphs can be colored using only two colors, assigning one color to each set, without adjacent vertices sharing the same color.
Perfect Matching Possible In some bipartite graphs, perfect matching occurs, meaning every vertex in one set is connected to exactly one vertex in the other set.
Applications in Real-World Problems Used in tasks like job assignments and network flow where elements of two different types need to be linked without internal conflicts.
Maximum Bipartite Matching Algorithms like the Hopcroft–Karp are used to find the maximum number of matching edges, crucial in optimization problems.
Complete Bipartite Graph If every vertex in one set is connected to every vertex in the other, it’s called a complete bipartite graph, denoted as Km,nK_{m,n}Km,n.
Adjacency Matrix Properties The adjacency matrix of a bipartite graph can be rearranged into block form, with zero diagonal blocks and two off-diagonal blocks filled.
Can be Multigraph Bipartite graphs can be multigraphs, meaning multiple edges between two vertices are allowed, expanding the graph’s application in some models.
Planarity Some bipartite graphs are planar, meaning they can be drawn on a plane without edges crossing, often seen in network structures.
Properties of Bipartite Graphs
All the bipartite graphs are 2-colorable, which means that using only two colors, every vertex of the bipartite graph can be assigned a color such that none of the adjacent nodes has the same color.
Every subgraph of a bipartite graph is also bipartite.
It does not have odd cycles. This is because a graph having a cycle of odd length is not 2-colorable, so it can't be bipartite.
In a bipartite graph with the sets of vertices, as set U and set V, the following always holds:
Sum of the degrees of all vertices in set U = Sum of the degrees of all vertices in set V
How to Check if a Given Graph is Bipartite or Not?
Problem Statement
Given a graph, check whether the graph is bipartite or not. Your function should return true if the given graph's vertices are divided into two independent groups, U and V, such that each edge [u,v] in the graph connects a vertex u from set U and a vertex v from set V.
You are given a 2D vector or adjacency matrix edges which contains 0 and 1, where edges[i][j] = 1 denotes a bi-directional edge from i to j. A bi-directional edge implies that the graph is undirected.
Before moving on to the solution approach, please first try to solve the question - Check Bipartite Graph
Approach
We know that all the bipartite graphs are 2-colorable, which means that using only two colors, every vertex of the bipartite graph can be assigned a color such that none of the adjacent nodes has the same color.
Adjacent nodes - Two nodes connected by an edge in a graph are said to be adjacent to each other.
So, for a given graph, we will check if the graph is 2-colorable or not. If it is 2-colorable, then it is a bipartite graph; else, it is not bipartite. We will use both DFS Algorithm(Depth First Search) and BFS(Breadth First Search) to solve this problem.
Algorithm
Following are the steps of the algorithm:
Assign a color (say green) to the source node.
Assign a different color(say blue) to all of the neighbours of the source node.
Iterate over all the neighbours and assign the color green to their neighbours.
If, at any point in time, we encounter a neighbour node with the same color as the current node, the process stops because it means that the graph is not 2-colorable and is not bipartite.
Dry Run
Let’s understand the working before implementation using an example. The graph we are using for this example is displayed below:
We will create an array of size = No of vertex and an empty queue. And assign all elements of that array as zero. In this example, the number of vertices = 5.
We will start with vertex 0 and assign a color to it (say green).
Check all its neighboring vertex and assign a color to them(say blue).
After removing 0 from the queue, 1 is the first element, so we will visit all neighboring vertices of 1 and assign the opposite color if uncolored.
After removing 1 from the queue, 3 is at the top. But all neighboring vertices satisfy the condition of Bipartite Graph. So, no change will is made. After removing 3, vertex 2 will be checked.
As the color of vertex 2 and 4 is the same, the loop will go to the else block and return false. So our graph is not a Bipartite graph.
Implementation
Using DFS(Depth First Search)
The code to check if a given graph is bipartite or not using DFS is given below:
C++
Java
Python
C++
// C++ code using DFS #include <bits/stdc++.h> using namespace std;
// Function to add nodes in graph void storeNodes(vector<int> adj[], int u, int v) { adj[u].push_back(v); adj[v].push_back(u); } bool isBipartite(vector<int> edges[], int vtx, vector<bool>& searched, vector<int>& colors) { // Start traversing nodes for (int i : edges[vtx]) { // Check if vertex i is searched before or not if (searched[i] == false) { // Mark vertex == searched searched[i] = true; colors[i] = !colors[vtx];
// Check recursively for subtree if (!isBipartite(edges, i, searched, colors)) return false; }
// Check if color is same then return false else if (colors[i] == colors[vtx]) return false; }
// Otherwise graph is Bipartite return true; }
// Main Code int main() { int no_of_vertex = 5; // Declare adjacency list vector<int> edges[no_of_vertex]; // Declare required arrays vector<bool> searched(no_of_vertex); vector<int> colors(no_of_vertex); // adding edges to the graph storeNodes(edges, 0,1); storeNodes(edges, 2,0); storeNodes(edges, 0,3); storeNodes(edges, 3,4); storeNodes(edges, 2,4); storeNodes(edges, 4,1); storeNodes(edges, 3,2); // Mark start vertex = searched and assign a color searched[0] = true; colors[0] = 0; bool result = isBipartite(edges, 1, searched, colors); if (result == true) cout << "The given graph is Bipartite.\n"; else cout << "The given graph is not Bipartite.\n";
return 0; }
You can also try this code with Online C++ Compiler
public class BipartiteGraph { // Function to add nodes in the graph static void storeNodes(List<Integer>[] adj, int u, int v) { adj[u].add(v); adj[v].add(u); }
static boolean isBipartite(List<Integer>[] edges, int vtx, boolean[] searched, int[] colors) { // Traverse nodes for (int i : edges[vtx]) { // Check if vertex i is searched before or not if (!searched[i]) { // Mark vertex as searched searched[i] = true; colors[i] = 1 - colors[vtx];
// Check recursively for subtree if (!isBipartite(edges, i, searched, colors)) { return false; } } // If the color is the same, return false else if (colors[i] == colors[vtx]) { return false; } } // Otherwise, the graph is bipartite return true; }
public static void main(String[] args) { int no_of_vertex = 5;
// Declare adjacency list List<Integer>[] edges = new ArrayList[no_of_vertex]; for (int i = 0; i < no_of_vertex; i++) { edges[i] = new ArrayList<>(); }
// Declare required arrays boolean[] searched = new boolean[no_of_vertex]; int[] colors = new int[no_of_vertex];
// Mark start vertex as searched and assign a color searched[0] = true; colors[0] = 0;
boolean result = isBipartite(edges, 1, searched, colors); if (result) { System.out.println("The given graph is Bipartite."); } else { System.out.println("The given graph is not Bipartite."); } } }
You can also try this code with Online Java Compiler
# Function to add nodes in the graph def store_nodes(adj, u, v): adj[u].append(v) adj[v].append(u)
def is_bipartite(edges, vtx, searched, colors): # Traverse nodes for i in edges[vtx]: # Check if vertex i is searched before or not if not searched[i]: # Mark vertex as searched searched[i] = True colors[i] = not colors[vtx]
# Check recursively for subtree if not is_bipartite(edges, i, searched, colors): return False # If the color is the same, return False elif colors[i] == colors[vtx]: return False # Otherwise, the graph is bipartite return True
# Main code if __name__ == "__main__": no_of_vertex = 5
# Declare adjacency list edges = defaultdict(list)
It is O(N), where ‘N’ is the number of nodes. As we are traversing all the nodes onces. So, for N number of nodes the number of traversals are also equal to N. Hence, the overall time complexity is O(N).
Space Complexity
It is O(N), where ‘N’ is the number of nodes. Since we are using an array to store the colour of each node and an array to store visited nodes for DFS traversal, so the overall space complexity will be O(N).
Using BFS(Breadth First Search)
The code to check if a graph is bipartite or not using BFS is given below:
C++
Java
Python
C++
#include <bits/stdc++.h> using namespace std;
bool isBipartite(vector<vector<int>> &graph) { // N is total number of nodes in graph int n = graph.size();
// initialize an array of size N with all 0 values vector<int> colors(n, 0);
// Create an empty queue for BFS traversal queue<int> q;
// Loop over all the nodes one by one for (int i = 0; i < n; i++) { // If color already assigned if (colors[i] == 1) continue;
// Assign color 1 to the node colors[i] = 1;
// Push current node to the queue for bfs q.push(i);
while (!q.empty()) { int temp = q.front();
// Loop over all the neighbors of current node for (auto neighbor : graph[temp]) { // Check if color is not assigned to the neighbor if (!colors[neighbor]) { // Assign an opposite color to the neighbors colors[neighbor] = -colors[temp]; q.push(neighbor); }
// If neighbor has the same color return false else if (colors[neighbor] == colors[temp]) return false; }
// Pop the front node from the queue q.pop(); } } return true; }
// Main code to test int main() { int no_of_vertex = 5;
// Declare adjacency list vector<vector<int>> edges(no_of_vertex, vector<int>(no_of_vertex, 0));
// Construct adjacency list from adjacency matrix vector<vector<int>> graph(no_of_vertex, vector<int>()); for (int i = 0; i < no_of_vertex; i++) for (int j = 0; j < no_of_vertex; j++) if (edges[i][j] == 1) graph[i].push_back(j);
bool result = isBipartite(graph); if (result == true) cout << "The given graph is Bipartite.\n";
else cout << "The given graph is not Bipartite.\n"; }
You can also try this code with Online C++ Compiler
public class BipartiteCheck { static boolean isBipartite(List<List<Integer>> graph) { int n = graph.size(); // Total number of nodes in graph
// Initialize an array to store colors, 0 means uncolored int[] colors = new int[n];
// Create an empty queue for BFS traversal Queue<Integer> q = new LinkedList<>();
// Loop over all nodes for (int i = 0; i < n; i++) { // If node is already colored, skip it if (colors[i] != 0) continue;
// Assign color 1 to the node colors[i] = 1; q.add(i);
// BFS traversal while (!q.isEmpty()) { int temp = q.poll();
// Loop over all neighbors of the current node for (int neighbor : graph.get(temp)) { // If the neighbor has no color, assign opposite color if (colors[neighbor] == 0) { colors[neighbor] = -colors[temp]; q.add(neighbor); } // If the neighbor has the same color, graph is not bipartite else if (colors[neighbor] == colors[temp]) { return false; } } } } return true; // Graph is bipartite }
public static void main(String[] args) { int no_of_vertex = 5;
// Construct adjacency list from adjacency matrix List<List<Integer>> graph = new ArrayList<>(); for (int i = 0; i < no_of_vertex; i++) { graph.add(new ArrayList<>()); for (int j = 0; j < no_of_vertex; j++) { if (edges[i][j] == 1) { graph.get(i).add(j); } } }
boolean result = isBipartite(graph); if (result) { System.out.println("The given graph is Bipartite."); } else { System.out.println("The given graph is not Bipartite."); } } }
You can also try this code with Online Java Compiler
# Function to check if the graph is bipartite def is_bipartite(graph): n = len(graph) # Total number of nodes in graph
# Initialize an array to store colors, 0 means uncolored colors = [0] * n
# BFS traversal using a queue q = deque()
# Loop over all nodes for i in range(n): # If the node is already colored, skip it if colors[i] != 0: continue
# Assign color 1 to the node colors[i] = 1 q.append(i)
while q: temp = q.popleft()
# Loop over all neighbors of the current node for neighbor in graph[temp]: # If the neighbor has no color, assign opposite color if colors[neighbor] == 0: colors[neighbor] = -colors[temp] q.append(neighbor) # If the neighbor has the same color, graph is not bipartite elif colors[neighbor] == colors[temp]: return False return True # Graph is bipartite
# Main code to test if __name__ == "__main__": no_of_vertex = 5
# Construct adjacency list from adjacency matrix graph = [[] for _ in range(no_of_vertex)] for i in range(no_of_vertex): for j in range(no_of_vertex): if edges[i][j] == 1: graph[i].append(j)
result = is_bipartite(graph) if result: print("The given graph is Bipartite.") else: print("The given graph is not Bipartite.")
You can also try this code with Online Python Compiler
It is O(N ^ 2), where ‘N’ is the number of nodes. As we have to color all the nodes present, and for each node, we have to traverse its neighbours. In the worst cases, there can be at most ‘N’ neighbours. Hence, the overall time complexity is O(N ^ 2).
Space Complexity
It is O(N), where ‘N’ is the number of nodes. Since we are using an array to store the color of each node and a queue to do BFS, the overall space complexity will be O(N).
Applications of Bipartite Graphs
Bipartite graphs are used for similarity ranking in search advertising and e-commerce.
They are used to predict the movie preferences of a person.
It is extensively used in coding theory. Bipartite graphs are used for decoding codewords.
Bipartite graphs are also used to mathematically model real-world problems like big data, cloud computing, etc.
Frequently Asked Questions
What is the rule of bipartite graph?
A bipartite graph consists of two disjoint sets of vertices, with edges only between vertices from different sets. No edge connects vertices within the same set, and it must not contain odd-length cycles.
What are the differences between bipartite graphs and complete graphs?
A bipartite graph has two disjoint sets of vertices with edges between them, while a complete graph connects every vertex to every other vertex. Bipartite graphs don't require all vertices to be connected, but complete graphs do.
Is a tree a bipartite graph?
Yes, a tree is always a bipartite graph because it does not contain any cycles, and any acyclic graph (tree) can be colored with two colors without adjacent vertices having the same color.
Can a bipartite graph contain a cycle of odd length?
No, a bipartite graph cannot contain a cycle of odd length. The presence of an odd-length cycle would force some adjacent vertices to share the same color, violating the bipartite property.
What is bipartite vs tripartite graph?
A bipartite graph has two disjoint vertex sets with edges between them, while a tripartite graph has three disjoint sets of vertices. In a tripartite graph, edges only connect vertices from different sets, similar to bipartite graphs but with three sets.
Conclusion
In this article, we learnt all about bipartite graphs. Bipartite graphs play a crucial role in graph theory and have significant applications in real-world scenarios like matching problems, network design, and resource allocation. Their unique structure, defined by two disjoint vertex sets and the absence of odd-length cycles, makes them both simple and versatile.
If you want to get confident about the various algorithms in graphs, do check out: