数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时装研究
法律研究使用 C++ 的 DFS 检查给定的图是二分图
二分图是一种图，其中如果只使用两种颜色（即一组中的顶点用同一种颜色着色），就可以给图着色。这是一个使用 DFS 检查图是否为二分图的 C++ 程序。
算法
Begin An array color[] is used to stores 0 or 1 for every node which denotes opposite colors. Call function DFS from any node. 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. If at any instance, color[u] is equal to !color[v], then the node is bipartite. 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]) {
// if vertex w is not explored before
if (visited[w] == false) {
// mark present vertex as visited
visited[w] = true;
color[w] = !color[v]; //mark color opposite to its parents
if (!Bipartite(adj, w, visited, color))
return false;
}
// if two adjacent are colored with same color then the graph is not bipartite
else if (color[w] == color[v])
return false;
}
return true;
}
int main()
{
int M = 6;
vector<int> adj[M + 1];
// to keep a check on whether a node is discovered or not
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
更新时间：2019 年 7 月 30 日
160 次浏览
广告