Breadth First Search(BFS)和Depth First Search(BFS)都可以处理Bipartite问题。BFS可以理解为各扫门前雪，而DFS则是一条道走到黑。
BFS
public class BFSSolution {
public boolean isBipartite(List<GraphNode> graph) {
HashMap<GraphNode, Integer> visited = new HashMap<>();
for (GraphNode node: graph) {
if (!isBipartite(node, visited)) {
return false;
}
}
return true;
}
private boolean isBipartite(GraphNode node, HashMap<GraphNode, Integer> visited) {
if (visited.containsKey(node)) {
return true;
}
Queue<GraphNode> queue = new LinkedList<GraphNode>();
queue.offer(node);
visited.put(node, 0);
while (!queue.isEmpty()) {
GraphNode curr = queue.poll();
int neighborGroup = visited.get(curr) == 0 ? 1 : 0;
for (GraphNode neighbor: curr.neighbors) {
if (visited.containsKey(neighbor)) {
if (visited.get(neighbor) != neighborGroup) {
return false;
}
} else {
visited.put(neighbor, neighborGroup);
queue.offer(neighbor);
}
}
}
return true;
}
}
DFS
public class DFSSolution {
public boolean isBipartite(List<GraphNode> graph) {
HashMap<GraphNode, Integer> visited = new HashMap<>();
for (GraphNode node: graph) {
if (!isBipartite(node, visited)) {
return false;
}
}
return true;
}
private boolean isBipartite(GraphNode node, HashMap<GraphNode, Integer> visited) {
if (visited.containsKey(node)) {
return true;
}
Deque<GraphNode> stack = new LinkedList<GraphNode>();
stack.offerFirst(node);
visited.put(node, 0);
while (!stack.isEmpty()) {
GraphNode curr = stack.pollFirst();
int neighborGroup = visited.get(curr) == 0 ? 1 : 0;
for (GraphNode neighbor: curr.neighbors) {
if (visited.containsKey(neighbor)) {
if (visited.get(neighbor) != neighborGroup) {
return false;
}
} else {
visited.put(neighbor, neighborGroup);
stack.offerFirst(neighbor);
}
}
}
return true;
}
}
Code Carpenter 