Check whether a graph is Bipartite or Not
Problem Statement
Given an undirected graph, determine whether it is bipartite. A graph is bipartite if its vertices can be divided into two groups such that every edge connects a vertex in one group to a vertex in the other group. No edge should connect two vertices in the same group.
Example:
- Input:
V = 4, edges = [(0,1), (1,2), (2,3), (3,0)] - Output:
true(bipartite — groups: 2 and 3) - Input:
V = 3, edges = [(0,1), (1,2), (2,0)] - Output:
false(odd cycle, not bipartite)
Noob-Friendly Explanation
Imagine you're organising a party and you want to split everyone into two teams. The rule is: friends must be on different teams. If you can split everyone following this rule, the friend network is "bipartite."
You try colouring each person with one of two colours (red or blue). If a person is red, all their friends must be blue, and vice versa. If at any point you find two friends with the same colour, it's impossible — the graph is NOT bipartite.
Approach 1: Brute Force (DFS Colouring)
Intuition
Use DFS to try 2-colouring the graph. Assign a colour to the start node. For every neighbour, assign the opposite colour. If a neighbour already has the same colour as the current node, the graph is not bipartite.
Algorithm
- Create a colour array initialized to -1 (uncoloured).
- For each unvisited vertex, start DFS and colour it 0.
- For each neighbour, if uncoloured, colour it with the opposite colour and recurse.
- If a neighbour has the same colour, return false.
import java.util.*;
public class BipartiteDFS {
public static boolean isBipartite(int V, List<List<Integer>> adj) {
int[] colour = new int[V];
Arrays.fill(colour, -1);
for (int i = 0; i < V; i++) {
if (colour[i] == -1) {
if (!dfs(i, 0, adj, colour)) {
return false;
}
}
}
return true;
}
static boolean dfs(int node, int c, List<List<Integer>> adj, int[] colour) {
colour[node] = c;
for (int neigh : adj.get(node)) {
if (colour[neigh] == -1) {
if (!dfs(neigh, 1 - c, adj, colour)) {
return false;
}
} else if (colour[neigh] == c) {
return false;
}
}
return true;
}
public static void main(String[] args) {
int V = 4;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
int[][] edges = {{0,1},{1,2},{2,3},{3,0}};
for (int[] e : edges) {
adj.get(e[0]).add(e[1]);
adj.get(e[1]).add(e[0]);
}
System.out.println("Is bipartite: " + isBipartite(V, adj));
}
}Complexity Analysis
- Time Complexity: O(V + E) - standard DFS traversal
- Space Complexity: O(V) - colour array and recursion stack
Approach 2: Optimal (BFS Colouring)
Intuition
BFS can also 2-colour the graph level by level. Nodes at even levels get one colour, nodes at odd levels get the other. If any edge connects two nodes at the same level (same colour), the graph is not bipartite. BFS is often preferred because it avoids deep recursion stack overflow.
Algorithm
- Create a colour array initialized to -1.
- For each unvisited vertex, start BFS and colour it 0.
- For each neighbour of the current node:
- If uncoloured, assign opposite colour and enqueue.
- If same colour, return false.
import java.util.*;
public class BipartiteBFS {
public static boolean isBipartite(int V, List<List<Integer>> adj) {
int[] colour = new int[V];
Arrays.fill(colour, -1);
for (int i = 0; i < V; i++) {
if (colour[i] == -1) {
if (!bfs(i, adj, colour)) {
return false;
}
}
}
return true;
}
static boolean bfs(int start, List<List<Integer>> adj, int[] colour) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
colour[start] = 0;
while (!queue.isEmpty()) {
int node = queue.poll();
for (int neigh : adj.get(node)) {
if (colour[neigh] == -1) {
colour[neigh] = 1 - colour[node];
queue.offer(neigh);
} else if (colour[neigh] == colour[node]) {
return false;
}
}
}
return true;
}
public static void main(String[] args) {
int V = 4;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
int[][] edges = {{0,1},{1,2},{2,3},{3,0}};
for (int[] e : edges) {
adj.get(e[0]).add(e[1]);
adj.get(e[1]).add(e[0]);
}
System.out.println("Is bipartite (BFS): " + isBipartite(V, adj));
}
}Complexity Analysis
- Time Complexity: O(V + E) - BFS visits each vertex and edge once
- Space Complexity: O(V) - colour array and queue