Graph - DSA: Bipartite Graph | BFS | C++ | Java

This chapter covers the fundamental concept of Bipartite Graphs and demonstrates how to solve bipartiteness detection using Breadth-First Search (BFS). We will examine the core definition, structural properties (such as even vs. odd cycle lengths), intuition, dry runs, complete C++ and Java implementations, handling disconnected components, and complexity analysis.

1. What is a Bipartite Graph? (Definition & Core Concept)

A Bipartite Graph is a graph that can be colored using two distinct colors (e.g., yellow and green, or color 0 and color 1) such that no two adjacent nodes (neighbors) share the same color.

Real-Life Analogy

Mental Hook: Imagine assigning seating for two rival teams in a room where everyone sitting next to each other must belong to opposing teams. If you can successfully alternate team colors across every connection without any two teammates sitting side-by-side, the seating arrangement is valid (bipartite). If two teammates are forced to sit next to each other, the configuration is invalid (non-bipartite).

Visualizing Bipartite vs. Non-Bipartite

• Bipartite Graph Example:

  CODE

  Copy

  Yellow (0) --- Green (1) --- Yellow (0) --- Green (1)
  

  Adjacent nodes always have opposite colors.

• Non-Bipartite Graph Example: When a cycle forces an odd number of nodes, two adjacent nodes inevitably end up with the same color, violating the rule.

2. Structural Properties: Cycles and Bipartiteness

Before jumping into algorithms, we can determine bipartiteness instantly by observing the graph's cycles:

Note: If you are checking for bipartiteness and find that a graph is not bipartite, it is a definitive proof that the graph contains at least one odd-length cycle.

3. Algorithm Requirements for BFS Approach

To implement BFS-based bipartiteness testing, we need two primary data structures:

1. Queue (queue): Standard BFS queue to keep track of nodes to visit level by level.
2. Color Array (color[]): Replaces the standard visited array.
   • Initialized to -1 (meaning uncolored).
   • Filled with alternating values: 0 or 1.

4. Step-by-Step Flow Walkthrough (BFS Traversal)

Let's trace how the algorithm colors a graph and catches conflicts:

Conflict Detection (Non-Bipartite Case)

When visiting a neighbor that is already colored, we check:

5. C++ and Java Implementations

Below are the complete, production-ready implementations in C++ and Java for checking bipartiteness across potentially disconnected components.

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    bool checkBipartiteBFS(int start, int V, vector<int> adj[], vector<int>& color) {
        queue<int> q;
        
        q.push(start);
        color[start] = 0; // Assign initial color 0
        
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            
            for (auto neighbor : adj[node]) {
                // If the adjacent node is yet uncolored, give the opposite color
                if (color[neighbor] == -1) {
                    color[neighbor] = 1 - color[node];
                    q.push(neighbor);
                }
                // If the adjacent node has the same color, graph is not bipartite
                else if (color[neighbor] == color[node]) {
                    return false;
                }
            }
        }
        return true;
    }

public:
    bool isBipartite(int V, vector<int> adj[]) {
        vector<int> color(V, -1);
        
        // Iterate through all nodes to handle disconnected components
        for (int i = 0; i < V; i++) {
            if (color[i] == -1) {
                if (!checkBipartiteBFS(i, V, adj, color)) {
                    return false;
                }
            }
        }
        return true;
    }
};

Java Implementation

import java.util.*;

class Solution {
    private boolean checkBipartiteBFS(int start, int V, ArrayList<ArrayList<Integer>> adj, int[] color) {
        Queue<Integer> q = new LinkedList<>();
        
        q.add(start);
        color[start] = 0; // Assign initial color 0
        
        while (!q.isEmpty()) {
            int node = q.poll();
            
            for (int neighbor : adj.get(node)) {
                // If the adjacent node is yet uncolored, give the opposite color
                if (color[neighbor] == -1) {
                    color[neighbor] = 1 - color[node];
                    q.add(neighbor);
                }
                // If the adjacent node has the same color, graph is not bipartite
                else if (color[neighbor] == color[node]) {
                    return false;
                }
            }
        }
        return true;
    }

    public boolean isBipartite(int V, ArrayList<ArrayList<Integer>> adj) {
        int[] color = new int[V];
        Arrays.fill(color, -1);
        
        // Iterate through all nodes to handle disconnected components
        for (int i = 0; i < V; i++) {
            if (color[i] == -1) {
                if (!checkBipartiteBFS(i, V, adj, color)) {
                    return false;
                }
            }
        }
        return true;
    }
}

6. Industry Reality & Debugging: Handling Disconnected Components

When testing graph algorithms on platforms like LeetCode or GeeksforGeeks, code often fails on larger test cases due to disconnected components.

Why Single-Component Traversals Fail

If a graph has multiple isolated islands (sub-graphs not connected to node 0), starting traversal solely from node 0 leaves other components unvisited (color == -1), resulting in incomplete checks or false positives.

The Fix

Wrap your traversal inside a component-checking loop:

7. Complexity Analysis

• Time Complexity: $\mathcal{O}(V + E)$
  • $V$ = Number of vertices (each node is visited and pushed into the queue once).
  • $E$ = Number of edges (each edge is traversed twice in an undirected graph).
• Space Complexity: $\mathcal{O}(V)$
  • $\mathcal{O}(V)$ for the color array.
  • $\mathcal{O}(V)$ for the BFS queue in the worst-case scenario (e.g., a star graph).

Summary and Key Takeaways

• Bipartite Definition: A graph whose vertices can be divided into two disjoint sets such that no edges connect vertices within the same set, colored using 2 alternating colors.
• Cycle Rule: Linear graphs and graphs with even-length cycles are always bipartite. Graphs with odd-length cycles can never be bipartite.
• Color Array State: We initialize a color[] array with -1 representing uncolored nodes, using 0 and 1 as alternating colors.
• Neighbor Conflict Check: During BFS, if an adjacent neighbor already has the same color as the current node, the graph is immediately classified as non-bipartite.
• Brute Force Intuition: The algorithm is a systematic brute-force coloring technique driven by BFS traversal.
• Disconnected Graphs Support: Always include a component-checking outer loop (for (int i = 0; i < V; i++)) to guarantee all isolated sub-graphs are evaluated.
• Optimal Efficiency: Achieves linear efficiency with an optimal $\mathcal{O}(V + E)$ time complexity and $\mathcal{O}(V)$ auxiliary space.