数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用 C++ 程序中的 DFS 检查给定图是否为二分图
假设我们有一个连通图；我们需要检查该图是否为二分图。如果可以通过使用两种颜色进行图着色，使得一组节点用同一种颜色着色。
因此，如果输入类似于
则输出将为 True
为了解决这个问题，我们将遵循以下步骤 -
- 定义一个函数 insert_edge()，它将接收一个边数组 adj、u、v，
- 将 v 插入到 adj[u] 的末尾
- 将 u 插入到 adj[v] 的末尾
- 从主方法执行以下操作，
- 对于 adj[v] 中的每个 u，执行
- 如果 visited[u] 为 false，则 -
- visited[u] := true
- color[u] := color[v] 的反值
- 如果 !is_bipartite_graph(adj, u, visited, color)，则 -
- 返回 false
- 否则，当 color[u] 等于 color[v] 时，则 -
- 返回 false
- 如果 visited[u] 为 false，则 -
- 返回 true
示例（C++）
让我们看看以下实现以获得更好的理解 -
#include <bits/stdc++.h>
using namespace std;
void insert_edge(vector<int> adj[], int u, int v){
adj[u].push_back(v);
adj[v].push_back(u);
}
bool is_bipartite_graph(vector<int> adj[], int v, vector<bool>& visited, vector<int>& color){
for (int u : adj[v]) {
if (visited[u] == false) {
visited[u] = true;
color[u] = !color[v];
if (!is_bipartite_graph(adj, u, visited, color))
return false;
}
else if (color[u] == color[v])
return false;
}
return true;
}
int main() {
int N = 6;
vector<int> adj_list[N + 1];
vector<bool> visited(N + 1);
vector<int> color(N + 1);
insert_edge(adj_list, 1, 2);
insert_edge(adj_list, 2, 3);
insert_edge(adj_list, 3, 4);
insert_edge(adj_list, 4, 5);
insert_edge(adj_list, 5, 6);
insert_edge(adj_list, 6, 1);
visited[1] = true;
color[1] = 0;
cout << (is_bipartite_graph(adj_list, 1, visited, color));
}输入
insert_edge(adj_list, 1, 2); insert_edge(adj_list, 2, 3); insert_edge(adj_list, 3, 4); insert_edge(adj_list, 4, 5); insert_edge(adj_list, 5, 6); insert_edge(adj_list, 6, 1);
输出
1
更新于: 2020-08-27
580 次查看
广告