使用 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
  • 返回 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 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告