Chương trình C ++ để kiểm tra xem Graph có phải là Bipartite hay không bằng cách sử dụng DFS

Đồ thị hai bên là đồ thị trong đó nếu có thể tô màu đồ thị bằng cách sử dụng hai màu, tức là; các đỉnh trong một tập hợp được tô cùng màu. Đây là một chương trình C ++ để Kiểm tra xem một đồ thị có tính chất lưỡng phân hay không bằng cách sử dụng DFS.

Thuật toán

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

Ví dụ

#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;
}

Đầu ra

Graph is not Bipartite