检查一个图是否是二分图的算法
使用的是宽度搜索：
１ 初始化一个颜色记录数组
２ 利用ｑｕｅｕｅ宽度遍历图
３ 从随意源点出发。染色０。 或１
４ 遍历这点的邻接点。假设没有染色就染色与这个源点相反的颜色，假设已经染色而且和源点的值相反。那么就是合法点，假设是同样的颜色。那么就不能是二分图
參考：http://www.geeksforgeeks.org/bipartite-graph/
#include <stdio.h>
#include <iostream>
#include <queue>
using namespace std; class CheckwhetheragivengraphisBipartiteornot
{
const static int V = 4;
bool isBipartite(int G[][V], int src)
{
int colors[V];
fill(colors, colors+V, -1); colors[src] = 1; queue<int> qu;
qu.push(src);
while (qu.size())
{
int u = qu.front();
qu.pop(); for (int v = 0; v < V; v++)
{
if (G[u][v] && colors[v] == -1)
{
colors[v] = 1 - colors[u];
qu.push(v);
}
else if (G[u][v] && colors[v] == colors[u]) return false;
}
}
return true;
}
public:
CheckwhetheragivengraphisBipartiteornot()
{
int G[][V] =
{
{0, 1, 0, 1},
{1, 0, 1, 0},
{0, 1, 0, 1},
{1, 0, 1, 0}
}; isBipartite(G, 0) ? cout << "Yes" : cout << "No";
}
};