数据结构
网络
关系型数据库管理系统
操作系统
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究如何查找图是否是二分图？
当图中的顶点可以分成两个独立的集合，使图中的每条边要么从第一个集合开始并结束于第二个集合，要么从第二个集合开始并连接到第一个集合，换句话说，我们可以说在同一个集合中找不到边，则该图被称为二分图。
可以使用顶点着色来检查二分图。当一个顶点在同一个集合中时，它具有相同的颜色，对于另一个集合，颜色将改变。
输入和输出
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: The graph is bipartite.
算法
isBipartite(source)
输入 − 源顶点。
输出：当图是二分图时返回 True。
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 << "The graph is bipartite." << endl;
else
cout << "The graph is not bipartite." << endl;
} 输出
The graph is bipartite.
更新于： 2020 年 6 月 16 日
4K+ 浏览
广告