785. Is Graph Bipartite? #

Problem #

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].

Problem Summary #

Given an undirected graph graph, return true when this graph is bipartite.

graph will be given as an adjacency list, where graph[i] represents all nodes connected to node i in the graph. Each node is an integer between 0 and graph.length-1. There are no self-loops or parallel edges in this graph: graph[i] does not contain i, and there are no duplicate values in graph[i].

Note:

• The length of graph is in the range [1, 100].
• The elements in graph[i] are in the range [0, graph.length - 1].
• graph[i] will not contain i or duplicate values.
• The graph is undirected: if j is in graph[i], then i will also be in graph[j].

Solution Approach #

• Determine whether an undirected graph is bipartite. Definition of a bipartite graph: if we can split a graph’s set of nodes into two independent subsets A and B, and make the two nodes of every edge in the graph come one from set A and one from set B, we call this graph bipartite.
• This problem can be solved with BFS, DFS, or Union Find. Here is a DFS implementation. Choose any node to start, color it red, then perform DFS traversal on the entire graph, coloring all connected and uncolored nodes green. Nodes with different colors represent different sets. At this point, a second situation may occur: a connected node already has a color, and this color is the same as the color of the previous node, which indicates that the undirected graph is not bipartite. You can directly return false. Traverse like this until all nodes are colored. If coloring succeeds, it means the undirected graph is bipartite, so return true.

Code #

package leetcode

// DFS coloring, 1 is red, 0 is green, -1 is uncolored
func isBipartite(graph [][]int) bool {
	colors := make([]int, len(graph))
	for i := range colors {
		colors[i] = -1
	}
	for i := range graph {
		if !dfs(i, graph, colors, -1) {
			return false
		}
	}
	return true
}

func dfs(n int, graph [][]int, colors []int, parentCol int) bool {
	if colors[n] == -1 {
		if parentCol == 1 {
			colors[n] = 0
		} else {
			colors[n] = 1
		}
	} else if colors[n] == parentCol {
		return false
	} else if colors[n] != parentCol {
		return true
	}
	for _, c := range graph[n] {
		if !dfs(c, graph, colors, colors[n]) {
			return false
		}
	}
	return true
}