数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用 BFS 检查图是否是二分的 C++ 程序
二分图是如果图着色可以只用两种颜色进行（即一组中所有顶点都用同一种颜色着色），则二分图就是一幅图。本文提供了一个使用 BFS 检查图是否为二分图的 C++ 程序。
算法
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 is colored with same color as 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
更新于: 2019 年 7 月 30 日
645 次浏览
广告