Is Graph Bipartite?

LeetCode Q 785 - Is Graph Bipartite?

Given an undirected graph, return true if and only if it is bipartite.
Recall that a graph is bipartite if we can split it’s set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B.
The graph is given in the following form: graph[i] is a list of indexes j for which the edge between nodes i and j exists. Each node is an integer between 0 and graph.length - 1. There are no self edges or parallel edges: graph[i] does not contain i, and it doesn’t contain any element twice.

Example 1:
Input: [[1,3], [0,2], [1,3], [0,2]] ; Output: true
Explanation:
The graph looks like this:
0—-1
| |
| |
3—-2
We can divide the vertices into two groups: {0, 2} and {1, 3}.

Example 2:
Input: [[1,2,3], [0,2], [0,1,3], [0,2]] ; Output: false
Explanation:
The graph looks like this:
0—-1
| |
| |
3—-2
We cannot find a way to divide the set of nodes into two independent subsets.

Note:

• graph will have length in range [1, 100].
• graph[i] will contain integers in range [0, graph.length - 1].
• graph[i] will not contain i or duplicate values.
• The graph is undirected: if any element j is in graph[i], then i will be in graph[j].

Solution

By coloring each node in the graph black or white, we can check is a graph is bipartite.

Traverse the graph, coloring the adjenct nodes to different colors. If we can finish the coloring procedure successfully, the graph is bipartite, otherwise it isn’t.

We can do this using DFS or BFS.

Solution 1 : BFS

int[] colors has three values, 0 : unvisiting, 1 : white, 2: black

Code:

public boolean isBipartite(int[][] graph) {
	int n = graph.length;   // n nodes
	int[] colors = new int[n];
	Arrays.fill(colors, -1);
	
	for (int i = 0; i < n; i++) {
		if (colors[i] == -1 && graph[i].length != 0) {
			colors[i] = 0;
			
			Queue<Integer> que = new LinkedList<>();
			que.offer(i);
			
			while(!que.isEmpty()) {
				int curr = que.poll();
				for (int next: graph[curr]) {
					if (colors[next] == -1) {
						que.offer(next); colors[next] = 1 - colors[curr];
					} else {
						if (colors[next] == colors[curr]) return false;
					}
				}   
			}
		}

	return true;
}

Solution 2 : DFS

Code:

public boolean isBipartite(int[][] graph) {
	int n = graph.length;   // n nodes
	int[] colors = new int[n];
	Arrays.fill(colors, -1);

	for (int i = 0; i < n; i++) {
		if (colors[i] == -1 && !validColor(graph, colors, 0, i))
			return false;
	}

	return true;
}

private boolean validColor(int[][] graph, int[] colors, int currColor, int node) {

	if (colors[node] != -1)
		return colors[node] == color;
	
	for (int next: graph[curr]) {
		if (color[next] != -1)
			return color[next] == 1 - currColor;
		color[next] == 1 - currColor;
		dfs(graph, next, 1 - currColor, color);
	}

	return true;
}