Problem Description

The "Is Graph Bipartite?" problem asks you to determine whether a given undirected graph can be colored using only two colors such that no two adjacent nodes share the same color. The input is provided as an adjacency list: graph[i] is a list of all nodes connected to node i. The graph may consist of multiple disconnected components.

• You must return True if the graph is bipartite, otherwise False.
• There may be multiple connected components.
• The input graph is undirected and does not contain self-loops.
• All nodes are labeled from 0 to n - 1 (where n is the number of nodes).

Thought Process

At first glance, this problem looks similar to coloring a map so that no two neighboring countries have the same color, but with the restriction of only two colors. The brute-force way would be to try all possible colorings, but that quickly becomes infeasible as the number of nodes increases.

Instead, the key insight is to realize that a bipartite graph is one whose nodes can be split into two groups, with every edge connecting a node from one group to a node from the other. This is equivalent to being able to color the graph with two colors such that no two connected nodes share the same color.

A practical way to check this is to attempt to color the graph using two colors (e.g., 0 and 1) while traversing it. If at any point we find two adjacent nodes that must be the same color, the graph is not bipartite.

Since the graph may be disconnected, we need to check every component, not just the part reachable from node 0.

Solution Approach

We can solve this problem by performing a BFS (Breadth-First Search) or DFS (Depth-First Search) on each component of the graph and attempting to assign colors to nodes as we go.

1. Initialize a color array: Create an array (or hash map) to store the color assigned to each node. Initially, all nodes are uncolored.
2. Traverse each node: For each node, if it is uncolored, start a BFS/DFS from that node, coloring it with one color (say, 0).
3. Color neighbors: For each neighbor of the current node, check:
   • If the neighbor is uncolored, assign it the opposite color and add it to the search queue/stack.
   • If the neighbor is already colored with the same color as the current node, the graph is not bipartite. Return False.
4. Repeat for all components: Since the graph may be disconnected, repeat the process for every node that hasn't been colored yet.
5. If successful: If all nodes can be colored without conflicts, return True.

We use an array for coloring because it allows O(1) lookups and updates, making the algorithm efficient.

Example Walkthrough

Let's walk through an example. Suppose the input graph is:

  graph = [
    [1,3],    # Node 0 is connected to 1 and 3
    [0,2],    # Node 1 is connected to 0 and 2
    [1,3],    # Node 2 is connected to 1 and 3
    [0,2]     # Node 3 is connected to 0 and 2
  ]
  

This is a 4-node cycle. Let's try to color it using BFS:

• Start at node 0, color it 0.
• Neighbors: 1 and 3. Color both with 1 (opposite of 0).
• Next, process node 1 (color 1). Its neighbors: 0 (already colored 0, OK), 2 (uncolored, color it 0).
• Process node 3 (color 1). Its neighbors: 0 (already colored 0, OK), 2 (already colored 0, OK).
• Process node 2 (color 0). Its neighbors: 1 (already colored 1, OK), 3 (already colored 1, OK).

All nodes are colored successfully with no conflicts. The function returns True.

Time and Space Complexity

• Brute-force approach: Trying all possible 2-colorings would take O(2^n) time, which is infeasible for large graphs.
• Optimized BFS/DFS approach: Each node and each edge is visited at most once. Thus, the time complexity is O(V + E), where V is the number of nodes and E is the number of edges.
• Space complexity: We need O(V) space to store the color of each node and for the BFS/DFS queue or stack.

Summary

The "Is Graph Bipartite?" problem is efficiently solved by attempting to color the graph with two colors using BFS or DFS. If any two connected nodes are forced to have the same color, the graph is not bipartite. This approach leverages the definition of bipartite graphs and avoids brute-force enumeration, making it both elegant and efficient. The key is to check all components and use a simple coloring scheme to detect conflicts.

Code Implementation

class Solution:
    def isBipartite(self, graph):
        n = len(graph)
        color = [None] * n

        for i in range(n):
            if color[i] is None:
                queue = [i]
                color[i] = 0
                while queue:
                    node = queue.pop(0)
                    for neighbor in graph[node]:
                        if color[neighbor] is None:
                            color[neighbor] = 1 - color[node]
                            queue.append(neighbor)
                        elif color[neighbor] == color[node]:
                            return False
        return True
      

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> color(n, -1);

        for (int i = 0; i < n; ++i) {
            if (color[i] == -1) {
                queue<int> q;
                q.push(i);
                color[i] = 0;
                while (!q.empty()) {
                    int node = q.front(); q.pop();
                    for (int neighbor : graph[node]) {
                        if (color[neighbor] == -1) {
                            color[neighbor] = 1 - color[node];
                            q.push(neighbor);
                        } else if (color[neighbor] == color[node]) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
};
      

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) {
                Queue<Integer> queue = new LinkedList<>();
                queue.offer(i);
                color[i] = 0;
                while (!queue.isEmpty()) {
                    int node = queue.poll();
                    for (int neighbor : graph[node]) {
                        if (color[neighbor] == -1) {
                            color[neighbor] = 1 - color[node];
                            queue.offer(neighbor);
                        } else if (color[neighbor] == color[node]) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
}
      

var isBipartite = function(graph) {
    const n = graph.length;
    const color = new Array(n).fill(null);

    for (let i = 0; i < n; i++) {
        if (color[i] === null) {
            const queue = [i];
            color[i] = 0;
            while (queue.length > 0) {
                const node = queue.shift();
                for (const neighbor of graph[node]) {
                    if (color[neighbor] === null) {
                        color[neighbor] = 1 - color[node];
                        queue.push(neighbor);
                    } else if (color[neighbor] === color[node]) {
                        return false;
                    }
                }
            }
        }
    }
    return true;
};