Check If a Graph is a Bipartite Graph

Problem: Given a graph, check it is a bipartite graph. A bipartite graph is a graph whose vertices can be divided into two sets. Then for every edge, the vertices connected by the edge are distributed in the two different sets (can't be both in one set).

Solution: If is similar to a coloring problem. We can do a BFS traversal to the graph. We need some extra space to store i) if a vertex is visited ii) the parity of that vertex. Or we can just use two hash tables.

• start from any vertex in the graph, we mark that vertex as visited, its parity as 1. Then we set the parity of its neighbors as 2. Since all the neighbors are not visited now, we put them in a queue.
• remove a vertex from the queue, if it is visited, ignore it. Otherwise, mark it as visited, check all its visited neighbors, if the parities are all odd or even, then the graph is not bipartite. Otherwise, set the parity of its non-visited neighbors as i+1 (assume the current vertex's parity is i) and add non-visited vertices to the queue.
• repeat the above step util the queue is empty. If the graph is not fully connected, need one extra step to check if all the vertices are visited