Bipartite

Hard

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.

Examples

1 -- 2

/

3 -- 4

is bipartite (1, 3 in group 1 and 2, 4 in group 2).

1 -- 2

/ |

3 -- 4

is not bipartite.

Assumptions

• The graph is represented by a list of nodes, and the list of nodes is not null.

public class Solution {
  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 already visited, skip
    if (visited.containsKey(node)) return true;
    
    //BFS queue
    Queue<GraphNode> queue = new LinkedList<GraphNode>();
    queue.offer(node);
    visited.put(node, 0);
    
    //start coloring
    //first node color is 0
    while(!queue.isEmpty()){
      GraphNode cur = queue.poll();

      //current color
      int curGroup = visited.get(cur);
      //neighbors nodes should be the opposite color of current node
      int neiGroup = curGroup == 0 ? 1 : 0;
      
      for(GraphNode nei : cur.neighbors){
        //insert new nodes with color
        if (!visited.containsKey(nei)){
          visited.put(nei, neiGroup);
          queue.offer(nei);
        } else if (visited.get(nei) != neiGroup){
        //if previously seen, but has same color as current node.
        //Means there exists an edge between two nodes of same group
          return false;
        }
      }
    }
    return true;
  }
}

Time Complexity: O(N^2) BFS each node

Space Complexity: O(N) Hashmap and Queue