Bipartite Graph

来源：Twitter Second Phone Interview, EPI

原帖：http://www.fgdsb.com/2015/01/03/check-whether-a-graph-is-bipartite-or-not/

题目：

A Bipartite Graph is a graph whose vertices can be divided into two independent sets, U and V such that every edge (u, v) either connects a vertex from U to V or a vertex from V to U. In other words, for every edge (u, v), either u belongs to U and v to V, or u belongs to V and v to U. We can also say that there is no edge that connects vertices of same set.

1. Assign RED color to the source vertex (putting into set U).
2. Color all the neighbors with BLUE color (putting into set V).
3. Color all neighbor’s neighbor with RED color (putting into set U).
4. This way, assign color to all vertices such that it satisfies all the constraints of m way coloring problem where m = 2.
5. While assigning colors, if we find a neighbor which is colored with same color as current vertex, then the graph cannot be colored with 2 vertices (or graph is not Bipartite)

Time Complexity of the above approach is same as that Breadth First Search. In above implementation is O(V^2) where V is number of vertices. If graph is represented using adjacency list, then the complexity becomes O(V+E).

思路：使用BFS遍历

代码：

 // bipartite graph   
 // G=[(1,2), (2,3), (3,4)] yes   
 // G=[(1,2), (2,3), (3,1)] no   
 // G=[(1,2), (2,3), (3,4), (4,1)] yes    
   
 // adjacency list   
 struct GraphNode {   
   int visited; // -1 visited, 0: 1-color1; 1: 2-colors;   
   vector<GraphNode*> neighbors;   
 };   
   
 // adjacency matrixs   
 // vector<vector<int>> graph;   
 // vector<int> color(num_nodes);   
   
 bool isBipartite(vector<GraphNode*> g) {   
   if (g.empty()) return false;   
   for (int i = 0; i < g.size(); ++i) {   
     if (g[i]->visited == -1) {   
       g[i]->visited = 0;   
       queue<GraphNode*> q;   
       q.push(g[i]);   
       while (!q.empty()) {   
         auto node = q.front(); q.pop();       
         auto neighbors = node->neighbors;   
         for (int k = 0; k < neighbors.size(); ++k) {   
           if (neighbors[k]->visited == -1) {   
             neighbors[k]->visited = node->visited == 0 ? 1 : 0;   
             q.push(neighbors[k]);   
           } else {   
             if (neighbors[k]->visited == node->visited) return false;   
           }   
         }   
       }   
     }   
   }   
   return true;   
 }