使用C ++使用DFS检查给定图是否为Bipartite

二分图是这样的图：如果仅使用两种颜色可以使图着色，即：一组顶点的颜色相同。这是一个C ++程序，用于检查是否使用DFS进行图形二分。

算法

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]) {
      //如果之前未探索顶点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