โปรแกรม C++ สำหรับ Graph Coloring บน Bipartite Graph

Bipartite Graph (กราฟสองส่วน) คือกราฟที่สามารถทำ graph coloring ได้ด้วย 2 สี กล่าวคือ โหนดในเซตเดียวกันจะมีสีเดียวกัน และไม่มีขอบเชื่อมโหนดในเซตเดียวกัน โปรแกรมนี้รับ Bipartite graph เป็นอินพุต และส่งออกสีของแต่ละโหนดหลังทำ coloring

อัลกอริธึม (BFS-based 2-Coloring)

1. ใช้ BFS (Breadth-First Search) เพื่อเยี่ยมชมโหนดทั้งหมด
2. เลือกโหนดเริ่มต้น ทาสีเหลือง (Yellow = 1)
3. ทาสีโหนดเพื่อนบ้านทั้งหมดเป็นสีน้ำเงิน (Blue = 0)
4. ทาสีโหนดชั้นถัดไปเป็นสีเหลือง สลับไปเรื่อยๆ จนครบทุกโหนด
5. หากพบขอบเชื่อมโหนดสีเดียวกัน → ไม่ใช่ Bipartite

โค้ดตัวอย่าง (ปรับปรุงให้อ่านง่ายและปลอดภัย)

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

int n, e;
vector<vector<int>> g;
vector<int> color; // -1 = uncolored, 0 = Blue, 1 = Yellow
vector<bool> visited;

void bfsColor(int start) {
    queue<int> q;
    q.push(start);
    color[start] = 1; // Yellow
    visited[start] = true;

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : g[u]) {
            if (!visited[v]) {
                visited[v] = true;
                color[v] = 1 - color[u]; // สลับสี: 0 <-> 1
                q.push(v);
            } else if (color[v] == color[u]) {
                cout << "Graph is NOT bipartite! Conflict at edge " << u << "-" << v << endl;
                exit(1);
            }
        }
    }
}

int main() {
    cout << "Enter number of vertices and edges: ";
    cin >> n >> e;
    cout << "'Y' = Yellow, 'B' = Blue\n";

    g.resize(n);
    color.assign(n, -1);
    visited.assign(n, false);

    for (int i = 0; i < e; ++i) {
        int a, b;
        cout << "Edge " << i+1 << " vertices: ";
        cin >> a >> b;
        --a; --b; // 0-based index
        g[a].push_back(b);
        g[b].push_back(a);
    }

    // อาจมีหลาย connected component
    for (int i = 0; i < n; ++i)
        if (!visited[i]) bfsColor(i);

    for (int i = 0; i < n; ++i) {
        cout << i+1 << " " << (color[i] ? 'Y' : 'B') << "\n";
    }
    return 0;
}

ตัวอย่างผลลัพธ์

Enter number of vertices and edges: 4 3
'Y' = Yellow, 'B' = Blue
Edge 1 vertices: 1 2
Edge 2 vertices: 3 2
Edge 3 vertices: 4 2
1 Y
2 B
3 B
4 B

คำอธิบาย: โหนด 2 ติดกับ 1, 3, 4 ดังนั้น 2 เป็นสีน้ำเงิน ส่วน 1, 3, 4 เป็นสีเหลือง (ไม่มีขอบเชื่อมระหว่าง 1-3, 1-4, 3-4 จึงเป็น Bipartite ได้)

โค้ดต้นฉบับมีปัญหา: ใช้ goto, array คงที่ขนาด 11101, logic สับสน โค้ดด้านบนใช้ vector, BFS มาตรฐาน, ตรวจสอบ conflict