1.1 Bipartite

Determine if an undirected graph is bipartite. A bipartite graph is one in which the nodes can be divided into two groups such that no nodes have direct edges to other nodes in the same group.

Assumption: Given graph is not null.

Input: List<GraphNode>

Output: boolean determine if the graph is bipartite

Solution:

1. The parent and children cannot be in the same group, which means after the parent is expanded, it cannot be visited again.

2. Use HashMap to store the expanded nodes. When generating a new node, if its child exists in the same group as this new node, the graph cannot be Bipartite.

3. For each step

Expand: the first element of the queue

Generate: all neighbor elements

Case 1: the neighbor has been generated before

1.1 the neighbor is in the same group of the parent, false

1.2 in the different group from the parent, ignore

Case 2: the neighbor has not been generated before

Assign it the other group other than its parent's

1. Termination condition: when queue is empty or return false

TC: O(Vertex + Edge)

SC: O(Vertex)

class GraphNode {
  public int key;
  public List<GraphNode> neighbors;
  public GraphNode(int key) {
    this.key = key;
    this.neighbors = new ArrayList<GraphNode>();
  }
}

// visited: <key=node, value=group 0 or 1>
public boolean isBipartite (List<GraphNode> graph) {
  HashMap<GraphNode, Integer> visited = new HashMap<>();
  for (GraphNode node : graph) {
    if (!bfs(node, visited)) { 
      return false;
    }
  }
  return true;
}

private boolean bfs(GraphNode node, HashMap<GraphNode, Integer> visited) {
  if (visited.containsKey(node)) {
    return true;
  }

  Queue<GraphNode> queue = new LinkedList<>();
  queue.offer(node);
  visited.put(node, 0);

  while (!queue.isEmpty()) {
    GraphNode cur = queue.poll();
    int curGroup = visited.get(cur);
    int neiGroup = curGroup == 0 ? 1 : 0;

    for (GraphNode nei : cur.neighbors) {
      if (!visited.containsKey(nei)) {
        visited.put(nei, neiGroup);
        queue.offer(nei);
      } else if (visited.get(nei) != neiGroup) {
         return false;
      }
    }
  }
  return true;
}