Skip to content
AI360Xpert
Back to Graphs
Medium

Is Graph Bipartite?

There is an undirected graph with `n` nodes, where each node is numbered between `0` and `n - 1`. You are given a 2D array `graph`, where `graph[u]` is an array of nodes that node `u` is adjacent to. A bipartite graph is a graph that can be partitioned into two independent sets `A` and `B` such that every edge in the graph connects a node in set `A` and a node in set `B`. Return `true` if and only if it is bipartite.

Examples

Input:graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output:false
There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.
Input:graph = [[1,3],[0,2],[1,3],[0,2]]
Output:true
We can partition the nodes into two sets: {0, 2} and {1, 3}.

Constraints

  • graph.length == n
  • 1 <= n <= 100
  • 0 <= graph[u].length < n
  • 0 <= graph[u][i] <= n - 1
  • graph[u] does not contain u.
  • All the values of graph[u] are unique.
  • If graph[u] contains v, then graph[v] contains u.

Graph Coloring (BFS)

Approach

We can use BFS to color the graph. We try to color nodes with two alternating colors (e.g., 1 and -1). For each uncolored node, we color it 1 and put it in a queue. Then we process the queue: for each node, we check all its neighbors. If a neighbor is uncolored, we color it with the opposite color and add it to the queue. If a neighbor is already colored with the *same* color as the current node, the graph cannot be bipartite, and we return false. Since the graph might be disconnected, we need to ensure we run this check starting from every uncolored node.

Complexity Analysis

Time Complexity
O(V + E)
Space Complexity
O(V)

Time complexity is O(V + E) as each node and edge is processed at most once. Space complexity is O(V) for the queue and colors array.

Solution.java
class Solution {    public boolean isBipartite(int[][] graph) {        int n = graph.length;        // 0: uncolored, 1: color A, -1: color B        int[] colors = new int[n];                // Check every node, as the graph might be disconnected        for (int i = 0; i < n; i++) {            // If the node is already colored, skip it            if (colors[i] != 0) continue;                        Queue<Integer> queue = new LinkedList<>();            queue.offer(i);            colors[i] = 1; // Start coloring with 1                        while (!queue.isEmpty()) {                int curr = queue.poll();                                for (int neighbor : graph[curr]) {                    // If neighbor is uncolored, color it with opposite color                    if (colors[neighbor] == 0) {                        colors[neighbor] = -colors[curr];                        queue.offer(neighbor);                    }                     // If neighbor has the same color, it's not bipartite                    else if (colors[neighbor] == colors[curr]) {                        return false;                    }                }            }        }                return true;    }}