Leetcode 785. Is Graph Bipartite?

Problem Explanation

In this problem, we are given an undirected graph, and we need to return true if it is bipartite. A bipartite graph is basically a graph whose nodes can be divided into two subsets such that every edge of the graph connects two nodes from different subsets.

The graph is presented in the form of a 2D list, where the integer i in the list of graph[j] means there is an edge between node i and j.

The problem solves by using the Breadth-first search with color marking criteria algorithm which requires the nodes be reachable after color-marking two adjacent nodes differently.

Solution Approach

In the given solution, we follow the Breadth-First Search (BFS) with color marking strategy.

1. Iterate each node, if the node has not be colored yet, color it and put it in the queue.
2. Do a loop to take out the node out of the queue.
3. Color every neighbor with the opposite color and put it into the queue.
4. If you find a painted node that should have a different color, then the graph is not bipartite, return false.
5. Repeat step 2, 3 and 4 until the queue is empty.

Solution walk-through with an example

Suppose we have the graph: [[1,3], [0,2], [1,3], [0,2]] The graph can be represented visually like this:

1
2
30----1
4|    |
5|    |
63----2

Here, we can form the 2 subsets {0, 2} and {1, 3} such that each edge of the graph connects nodes from these different subsets.

Now let's see the algorithm of the solution.

Initialize Colors: Initialize an array to keep track of colors(no color, color1, color2) for each node.

Color Marking: Start from the first node (0), mark it with color1 (kRed in solution). Mark all its neighbours (1,3) with color2 (kGreen in solution).

BFS: Put the marked nodes into a Queue data structure for BFS.

Neighbor Check: Dequeue a node, check its all neighbors. If all neighbors are of different color, continue. If any neighbor has the same color, return false.

Coloring and BFS Repeat: While queue is not empty, repeat the Color marking and BFS process for all the nodes in queue.

Return Result: If all nodes passed the Neighbor Check, then graph is bipartite, return true.

Solution (Python)

1
2python
3class Solution:
4    def isBipartite(self, graph):
5        color = {}
6        for node in range(len(graph)):
7            if node not in color:
8                stack = [node]
9                color[node] = 0
10                while stack:
11                    node = stack.pop()
12                    for nei in graph[node]:
13                        if nei not in color:
14                            stack.append(nei)
15                            color[nei] = color[node] ^ 1
16                        elif color[nei] == color[node]:
17                            return False
18        return True

Solution (Java)

1
2java
3class Solution {
4    public boolean isBipartite(int[][] graph) {
5        int n = graph.length;
6        int[] color = new int[n];
7        Arrays.fill(color, -1);
8        
9        for(int i=0; i<n; i++) {
10            if(color[i] == -1) {
11                color[i] = 0;
12                Queue<Integer> queue = new LinkedList<>();
13                queue.offer(i);
14                while(!queue.isEmpty()) {
15                    int node = queue.poll();
16                    for(int adjacent : graph[node]) {
17                        if(color[adjacent] == -1) {
18                            queue.offer(adjacent);
19                            color[adjacent] = color[node]^1;
20                        } else if(color[adjacent] == color[node]) {
21                            return false;
22                        }
23                    }   
24                }
25            }
26        }
27        return true;
28    }
29}

Solution(C++)

1
2c++
3class Solution {
4public:
5    bool isBipartite(vector<vector<int>>& graph) {
6        vector<int> color(graph.size(), -1);
7        
8        for(int i=0; i<graph.size(); i++) {
9            if(color[i] == -1) {
10                queue<int> q;
11                q.push(i);
12                color[i] = 0;
13                while(!q.empty()) {
14                    int node = q.front();
15                    q.pop();
16                    for(int& it : graph[node]) {
17                        if(color[it] == -1) {
18                            q.push(it);
19                            color[it] = color[node]^1;
20                        } else if(color[it] == color[node]) {
21                            return false;
22                        }
23                    }
24                }
25            }
26        }
27        return true;
28    }
29};

Solution(C#)

1
2csharp
3public class Solution {
4    public bool IsBipartite(int[][] graph) {
5        int n = graph.Length;
6        int[] color = new int[n];
7        for(int i=0;i<n;i++) color[i]=-1;
8        
9        for(int i=0; i<n; i++) {
10            if(color[i] == -1) {
11                color[i] = 0;
12                Queue<int> q = new Queue<int>();
13                q.Enqueue(i);
14                while(q.Count>0) {
15                    int node = q.Dequeue();
16                    for(int adj : graph[node]) {
17                        if(color[adj] == -1) {
18                            q.Enqueue(adj);
19                            color[adj] = color[node]^1;
20                        } else if(color[adj] == color[node]) {
21                            return false;
22                        }
23                    }
24                }
25            }
26        }
27        return true;
28    }
29}

Solution(Javascript)

1
2javascript
3var isBipartite = function(graph) {
4    let colors = new Array(graph.length).fill(0);
5    for(let i=0; i<graph.length; i++) {
6        if(colors[i] != 0) continue;    //continue if already colored
7        let queue = [i];
8        colors[i] = 1;  //start with color1
9        while(queue.length) {
10            let node = queue.shift();
11            for(let neighbor of graph[node]) {
12                if(colors[neighbor] == 0) {    //color if not colored
13                    colors[neighbor] = -colors[node];
14                    queue.push(neighbor);
15                } else if(colors[neighbor] != -colors[node]) {  //if the neighbor is colored, check if it is different from the current node
16                    return false;  //if same, graph is not bipartite
17                }
18            }
19        }
20    }
21    return true;
22};

Overall Explanation

In all the given code solutions, we are trying to color the graph in two colors (representing two groups 0 and 1) using BFS and validating whether it is a bipartite graph or not. If we encounter a node while performing BFS that is a neighboring node and is already colored with the same color, we return false immediately as it violates the bipartite's condition. If we have successfully colored all the nodes such that all neighboring nodes have different colors, we are returning true as it implies the graph is a bipartite.

Let's look at solutions in more detail:

Python:

The python solution is simple and easy to understand. We start by iterating through each node in the graph, and for each node, if it has not yet been colored, we color it (with 0). We then add it to a stack (for the BFS operation).

If the node's neighbor has not been colored, we color it with an alternate color. In python, we use the XOR operator to alternate between 0 and 1. If while coloring the neighbors, we find a neighbor that already has the same color as the node, we instantly return False; this is because the same colors for neighboring nodes do not satisfy the condition for a bipartite graph.

Java:

The Java solution is also quite similar to Python one. In Java, we use a Queue data structure, which helps to store the nodes for the BFS operation. We even make use of an Array to store the colors of the nodes. We initialize all elements of the colors Array as -1 to represent that no node is colored in the beginning.

We then start coloring the nodes (with 0) and perform BFS. If we find any node's neighbor that already has the same color as the node during this operation, we return False.

C++:

The C++ solution is pretty much the same as the Java one, except that we make use of a queue data structure (small 'q' in this case) to perform BFS.

C#:

The logic is the same as in the other solutions. The only difference with the C# solution is the syntax.

JavaScript:

In the Javascript solution, we use an array colors initialized with 0's to represent that initially, no nodes are colored. We then start coloring the nodes 1 (representing color1). We push every neighboring node that isn't colored into a queue and check if it violates the bi-partite condition.

In all the mentioned solutions, we return True at last, representing that the graph is, indeed, a bipartite as it satisfies the bipartite's condition.

Keep in mind that this problem is a typical BFS problem where we have to color the graph nodes such that no two neighboring nodes have the same color. If we can do so, the graph will be a bipartite; otherwise, it won't be. So, the BFS with Color marking approach works.