C ++程序使用BFS检查图是否为二分图
二分图是其中可以使用两种颜色进行着色的图形，即：一组顶点的颜色相同。这是一个C++程序，用于检查是否使用BFS进行图形二分。
算法
Begin Function Bipartite(): 1) Assign a color to the source vertex 2) Color all the neighbors with another color except first one color. 3) Color all neighbor’s neighbor with First color. 4) Like this way, assign color to all vertices such that it satisfies all the constraints of k way coloring problem where k = 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 i.e.; graph is not Bipartite End
示例
#include <iostream>
#include <queue>
#define V 5
using namespace std;
bool Bipartite(int G[][V], int s) {
int colorA[V];
for (int i = 0; i < V; ++i)
colorA[i] = -1;
colorA[s] = 1; //Assign a color to the source vertex
queue <int> q; //Create a queue of vertex numbers and enqueue source vertex for BFS traversal
q.push(s);
while (!q.empty()) {
int w = q.front(); //dequeue a vertex
q.pop();
for (int v = 0; v < V; ++v) //Find all non-colored adjacent vertices {
if (G[w][v] && colorA[v] == -1) //An edge from w to v exists and destination v is not colored {
colorA[v] = 1 - colorA[w]; //Assign alternate color to this adjacent v of w
q.push(v);
} else if (G[w][v] && colorA[v] == colorA[w]) //An edge from w to v exists and destination
//v的颜色与u相同
return false;
}
}
return true; //if all adjacent vertices can be colored with alternate color
}
int main() {
int G[][V] = {{ 0, 1, 0, 0},
{ 1, 0, 0, 0},
{ 0, 0, 0, 1},
{ 1, 0, 1, 0}};
if (Bipartite(G, 0))
cout << "The Graph is Bipartite"<<endl;
else
cout << "The Graph is Not Bipartite"<<endl;
return 0;
}输出结果
The Graph is Bipartite
热门推荐
1 如何训练狗狗不叫
2 训练狗狗不叫
3 训练狗狗随行
4 怎么训练狗狗不叫
7 训练比熊狗狗教程
10 上海狗狗训练
11 怎么训练狗狗上厕所
12 训练狗狗趴下
13 狗狗服从训练
14 训练狗狗拒食
15 训练狗狗笑
16 训练狗狗大便
17 训练狗狗立
18 训练狗狗捡东西