ตรวจสอบว่ากราฟเป็น Bipartite หรือไม่ด้วย DFS ใน C++

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

อัลกอริทึม

Begin
  อาเรย์ color[] ใช้เก็บ 0 หรือ 1 สำหรับทุกโหนด แทนสีตรงข้าม
  เรียกฟังก์ชัน DFS จากโหนดใดก็ได้
  ถ้าโหนด w ยังไม่เคยเยี่ยมชม ให้กำหนด !color[v] ให้ color[w] และเรียก DFS อีกครั้งเพื่อเยี่ยมชมโหนดที่เชื่อมกับ w
  ถ้าในบางกรณี color[u] เท่ากับ !color[v] โหนดจึงเป็น bipartite
  ปรับเปลี่ยนฟังก์ชัน DFS
End

ตัวอย่างโค้ด

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

void addEd(vector<int> adj[], int w, int v) {
  adj[w].push_back(v);
  adj[v].push_back(w);
}

bool Bipartite(vector<int> adj[], int v, vector<bool>& visited, vector<int>& color) {
  for (int w : adj[v]) {
    if (visited[w] == false) {
      visited[w] = true;
      color[w] = !color[v];
      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);
  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