C ++程序使用DFS检查图是否为二分图
二分图是其中可以使用两种颜色进行着色的图形，即：一组顶点的颜色相同。这是一个C++程序，用于检查是否使用DFS进行图形二分。
算法
Begin
1. An array color[] is used to stores 0 or 1 for every node which denotes opposite colors.
2. Call function DFS from any node.
3. If the node w has not been visited previously, then assign !
color[v] to color[w] and call DFS again to visit nodes connected to w.
4. If at any instance, color[u] is equal to !color[v], then the node is bipartite.
5. Modify the DFS function
End示例
#include<iostream>
#include <bits/stdc++.h>
using namespace std;
void addEd(vector<int> adj[], int w, int v) //adding edge to the graph {
adj[w].push_back(v); //add v to w’s list
adj[v].push_back(w); //add w to v’s list
}
bool Bipartite(vector<int> adj[], int v,
vector<bool>& visited, vector<int>& color) {
for (int w : adj[v]) {
//如果之前未探索顶点w-
if (visited[w] == false) {
//将当前顶点标记为已访问
visited[w] = true;
color[w] = !color[v]; //mark color opposite to its parents
if (!Bipartite(adj, w, visited, color))
return false;
}
//如果两个相邻的对象使用相同的颜色着色，则该图不是二分图
else if (color[w] == color[v])
return false;
}
return true;
}
int main() {
int M = 6;
vector<int> adj[M + 1];
//来检查是否
//是否发现节点
vector<bool> visited(M + 1);
vector<int> color(M + 1); //to color the vertices of the graph with 2 color
addEd(adj, 3,2);
addEd(adj, 1,4 );
addEd(adj, 2, 1);
addEd(adj, 5,3);
addEd(adj, 6,2);
addEd(adj, 3,1);
visited[1] = true;
color[1] = 0;
if (Bipartite(adj, 1, visited, color)) {
cout << "Graph is Bipartite";
} else {
cout << "Graph is not Bipartite";
}
return 0;
}输出结果
Graph is not Bipartite