โปรแกรม C++ ตรวจสอบกราฟ Bipartite ด้วย DFS

บทนำ

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

อัลกอริทึม

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

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

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

void addEdge(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);
    addEdge(adj, 3, 2);
    addEdge(adj, 1, 4);
    addEdge(adj, 2, 1);
    addEdge(adj, 5, 3);
    addEdge(adj, 6, 2);
    addEdge(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