Bipartite Check using DFS
Problem Overview
The problem asks us to determine if a given graph is bipartite. A graph is bipartite if its vertices can be divided into two disjoint and independent sets such that every edge connects a vertex in one set to a vertex in the other set.
This is an essential concept in graph theory with applications in numerous areas such as scheduling, matching problems, and network flow problems.
Understanding the Problem
To determine if a graph is bipartite, we must check if it's possible to color the graph using two colors in such a way that no two adjacent vertices share the same color. If such a coloring is possible, the graph is bipartite. The input graph is provided as an adjacency list, where each node's neighbors are listed in a typical adjacency list format.
Key DSA Concepts and Theory
Bipartite Graphs
A bipartite graph is a special type of graph that can be colored using two colors without two adjacent nodes having the same color. Alternatively, it is a graph that can be split into two sets, such that there are no edges between nodes of the same set.
Graph Representation
In this problem, graphs are represented using an adjacency list. This representation is efficient in terms of space usage, especially when dealing with sparse graphs, as it only stores information about edges that actually exist.
Graph Traversal
To solve this problem, we can employ graph traversal techniques such as Depth First Search (DFS) or Breadth First Search (BFS). Both these traversal algorithms visit nodes in a graph systematically and can be used to try coloring the graph to determine if it's bipartite.
Solution Approach
The goal is to attempt to color the graph using two colors. We can employ either BFS or DFS to help us track and color each node. Let's present the solution using both approaches.
BFS Approach
The BFS approach involves using a queue to manage our traversal, and an array to keep track of colors.
C++ Implementation - BFS
#include <vector>
#include <queue>
bool isBipartite(std::vector<std::vector<int>>& graph) {
int n = graph.size();
std::vector<int> color(n, -1); // -1 = uncolored, 0 = color1, 1 = color2
for (int i = 0; i < n; ++i) {
if (color[i] == -1) { // Not colored
std::queue<int> q;
q.push(i);
color[i] = 0; // Start coloring with 0
while (!q.empty()) {
int node = q.front();
q.pop();
for (int neighbor : graph[node]) {
if (color[neighbor] == -1) {
color[neighbor] = 1 - color[node]; // Alternate color
q.push(neighbor);
} else if (color[neighbor] == color[node]) {
return false; // Same color as current node
}
}
}
}
}
return true;
}
Java Implementation - BFS
import java.util.*;
class Solution {
public boolean isBipartite(int[][] graph) {
int n = graph.length;
int[] color = new int[n];
Arrays.fill(color, -1); // -1 represents uncolored
for (int i = 0; i < n; i++) {
if (color[i] == -1) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(i);
color[i] = 0; // Start coloring with 0
while (!queue.isEmpty()) {
int node = queue.poll();
for (int neighbor : graph[node]) {
if (color[neighbor] == -1) {
color[neighbor] = 1 - color[node]; // Alternate color
queue.offer(neighbor);
} else if (color[neighbor] == color[node]) {
return false; // Conflict detected
}
}
}
}
}
return true;
}
}
DFS Approach
Alternatively, we can use a DFS approach to allow recursive coloring.
C++ Implementation - DFS
#include <vector>
bool dfs(std::vector<std::vector<int>>& graph, std::vector<int>& color, int node) {
for (int neighbor : graph[node]) {
if (color[neighbor] == -1) {
color[neighbor] = 1 - color[node]; // Assign opposite color
if (!dfs(graph, color, neighbor)) {
return false;
}
} else if (color[neighbor] == color[node]) {
return false; // Found a conflict
}
}
return true;
}
bool isBipartite(std::vector<std::vector<int>>& graph) {
int n = graph.size();
std::vector<int> color(n, -1);
for (int i = 0; i < n; ++i) {
if (color[i] == -1) {
color[i] = 0;
if (!dfs(graph, color, i)) {
return false;
}
}
}
return true;
}
Java Implementation - DFS
class Solution {
public boolean isBipartite(int[][] graph) {
int n = graph.length;
int[] color = new int[n];
Arrays.fill(color, -1);
for (int i = 0; i < n; i++) {
if (color[i] == -1 && !dfs(graph, color, i, 0)) {
return false;
}
}
return true;
}
private boolean dfs(int[][] graph, int[] color, int node, int c) {
color[node] = c;
for (int neighbor : graph[node]) {
if (color[neighbor] == -1) {
if (!dfs(graph, color, neighbor, 1 - c)) {
return false;
}
} else if (color[neighbor] == color[node]) {
return false;
}
}
return true;
}
}
Time and Space Complexity Analysis
Both the BFS and DFS approaches have a similar time and space complexity:
- Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges. Each node and edge is considered once.
- Space Complexity: O(V), due to the space needed to store color information and the queue or recursion call stack.
Common Mistakes to Avoid
- Not handling disconnected components: Ensure to loop through all nodes as the graph may consist of multiple components.
- Inappropriate initialization of color: Remember to initialize colors to -1 (or an uncolored state) initially.
Similar Problems on Leetcode
Additional Resources and References
- Graph Theory Basics: Bipartite Graphs
- CLRS Book: "Introduction to Algorithms" - Graph algorithms
- Online Advanced Graph Tutorials - Topics on graph coloring and bipartite checking
This article should provide you with a thorough understanding of how to approach the bipartite graph problem effectively using both BFS and DFS methods. Understanding the key DSA concepts will also help solve related graph problems on LeetCode and beyond.