首页 > 代码库 > Geeks - Check whether a given graph is Bipartite or not 二分图检查
Geeks - Check whether a given graph is Bipartite or not 二分图检查
检查一个图是否是二分图的算法
使用的是宽度搜索:
1 初始化一个颜色记录数组
2 利用queue宽度遍历图
3 从任意源点出发,染色0, 或1
4 遍历这点的邻接点,如果没有染色就染色与这个源点相反的颜色,如果已经染色并且和源点的值相反,那么就是合法点,如果是相同的颜色,那么就不能是二分图
参考: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"; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。