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

บทนำ

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

อัลกอริทึม

Begin
  Function Bipartite():
    1) กำหนดสีให้โหนดต้นทาง
    2) ระบายสีเพื่อนบนทั้งหมดด้วยสีอีกสีหนึ่ง
    3) ระบายสีเพื่อนบนของเพื่อนบนด้วยสีแรก
    4) ทำเช่นนี้ต่อไปจนระบายสีทุกโหนด ตรงตามเงื่อนไข k-way coloring โดย k=2
    5) ถ้าพบเพื่อนบนที่มีสีเดียวกับโหนดปัจจุบัน แสดงว่าไม่ใช่ Bipartite
End

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

#include <iostream>
#include <queue>
#define V 5
using namespace std;

bool Bipartite(int G[][V], int s) {
    int colorA[V];
    for (int i = 0; i < V; ++i)
        colorA[i] = -1;
    colorA[s] = 1;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int w = q.front();
        q.pop();
        for (int v = 0; v < V; ++v) {
            if (G[w][v] && colorA[v] == -1) {
                colorA[v] = 1 - colorA[w];
                q.push(v);
            } else if (G[w][v] && colorA[v] == colorA[w])
                return false;
        }
    }
    return true;
}

int main() {
    int G[][V] = {
        {0, 1, 0, 0},
        {1, 0, 0, 0},
        {0, 0, 0, 1},
        {1, 0, 1, 0}
    };
    if (Bipartite(G, 0))
        cout << "The Graph is Bipartite" << endl;
    else
        cout << "The Graph is Not Bipartite" << endl;
    return 0;
}

ผลลัพธ์

The Graph is Bipartite