ตรวจสอบว่ากราฟที่กำหนดเป็นแบบสองส่วนโดยใช้ DFS ในโปรแกรม C ++ หรือไม่

สมมติว่าเรามีกราฟที่เชื่อมโยงกัน เราต้องตรวจสอบว่ากราฟเป็นไบพาร์ไทต์หรือไม่ หากการระบายสีกราฟเป็นไปได้ด้วยการใช้สองสี จะทำให้โหนดในชุดมีสีเดียวกัน

ดังนั้นหากอินพุตเป็นแบบ

แล้วผลลัพธ์จะเป็น True

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

กำหนดฟังก์ชัน insert_edge() ซึ่งจะใช้ edge array adj, u, v,
ใส่ v ต่อท้าย adj[u]
ใส่ u ที่ท้าย adj[v]
จากวิธีหลัก ให้ทำดังต่อไปนี้
สำหรับคุณแต่ละคนใน adj[v],do
- หากมาเยี่ยม[u] ก็เหมือนกับเท็จ ดังนั้น −
  - เยี่ยมชม[u] :=จริง
  - สี[u] :=สลับสี[v]
  - ถ้าไม่ใช่ is_bipartite_graph(adj, u, visit, color) แล้ว −
    - คืนค่าเท็จ
- มิฉะนั้น เมื่อ color[u] เหมือนกับ color[v] แล้ว −
  - คืนค่าเท็จ
คืนค่าจริง

ตัวอย่าง (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);