如何查找图是否为Bipartite？

可以将图的顶点划分为两个独立的集合，以使该图中的每个边要么从第一个集合开始并在第二个集合中结束，要么从第二个集合开始，连接到第一组，换句话说，我们可以说在同一组中找不到任何边缘。

通过使用顶点着色可以检查二部图。当一个顶点在同一集合中时，它具有相同的颜色，对于另一个集合，颜色将发生变化。

输入输出

Input:
The adjacency matrix.
0 1 1 1 0 0
1 0 0 1 1 0
1 0 0 1 0 1
1 1 1 0 1 1
0 1 0 1 0 1
0 0 1 1 1 0

Output:
该图是二分图。

算法

isBipartite(source)

输入-源顶点。
Outpu牛逼：当图是二分真。

Begin
   define an empty queue qu, and a color list coloArray
   initially any node is not colored with any color
   color the source vertex as color red
   add source in the qu
   when qu is not empty, do
      remove item from the qu and take in u
      if there is any self-loop, then
         return false
      for all vertices v, which is connected with u, do
         if v has no color, then
            if colorArray[u] = red, then
               colorArray[v] := blue
            else if colorArray[u] = blue, then
               colorArray[v] := red
            add v into the queue
         if colorArray[v] = colorArray[u], then
            return false
      done
   done
   return true
End

示例

#include<iostream>
#include<string>
#include<queue>
#define NODE 6
using namespace std;

/*int graph[NODE][NODE] = {
   {0, 1, 1, 1, 0, 0},
   {1, 0, 0, 1, 1, 0},
   {1, 0, 0, 1, 0, 1},
   {1, 1, 1, 0, 1, 1},
   {0, 1, 0, 1, 0, 1},
   {0, 0, 1, 1, 1, 0}
}; */

int graph[NODE][NODE] = {
   {0, 1, 0, 0, 0, 1},
   {1, 0, 1, 0, 0, 0},
   {0, 1, 0, 1, 0, 0},
   {0, 0, 1, 0, 1, 0},
   {0, 0, 0, 1, 0, 1},
   {1, 0, 0, 0, 1, 0}
};

bool isBipartite(int source) {
   queue<int> qu;
   string colorArray[NODE];

   for(int i = 0; i< NODE; i++)
      colorArray[i] = "No Color";    //initially no color is set for all vertices
   colorArray[source] = "Red";    //assign red with the source vertex
   qu.push(source);             //add source into the queue.

   while(!qu.empty()) {
      int u = qu.front();
      qu.pop();
      if(graph[u][u] == 1)    //there is a self loop
         return false;

      for(int v = 0; v < NODE; v++) {
         if(graph[u][v] != 0 && colorArray[v] == "No Color") {
            if(colorArray[u] == "Red")       //assign adjacent list with alternate color
               colorArray[v] = "Blue";
            else if(colorArray[u] == "Blue")
               colorArray[v] = "Red";
            qu.push(v);          //new adjacent node added to queue
         } else if(graph[u][v] != 0 && colorArray[v] == colorArray[u]) {
            return false;       //when u and adjacent are of same color.  
         }
      }
   }
   return true;
}

int main() {
   bool check;
   check = isBipartite(0);

   if(check)
      cout << "该图是二分图。" << endl;
   else
      cout << "该图不是二分图。" << endl;
}

输出结果

该图是二分图。