检查一个图是否是二分图的算法

使用的是宽度搜索：

１　初始化一个颜色记录数组

２　利用ｑｕｅｕｅ宽度遍历图

３　从随意源点出发。染色０。　或１

４　遍历这点的邻接点。假设没有染色就染色与这个源点相反的颜色，假设已经染色而且和源点的值相反。那么就是合法点，假设是同样的颜色。那么就不能是二分图

　

參考：http://www.geeksforgeeks.org/bipartite-graph/

#include 
     
      #include 
      
       #include 
       
        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
        
          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";	}};