home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

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

โจทย์

กำหนดกราฟเชื่อมต่อ (connected graph) ต้องการตรวจสอบว่ากราฟเป็น Bipartite หรือไม่ คือสามารถระบายสีโหนดด้วย 2 สีได้โดยโหนดที่ติดกันต้องมีสีต่างกัน

ขั้นตอนการแก้ปัญหา

  1. ฟังก์ชัน insert_edge(): เพิ่มขอบ u-v ใน adjacency list (แบบไม่มีทิศทาง)
  2. ฟังก์ชัน is_bipartite_graph(): DFS แบบ recursive
    • สำหรับเพื่อนบ้าน u ของ v: ถ้ายังไม่ได้เยี่ยม ให้ mark visited, ให้สีตรงข้ามกับ v, เรียก recursive
    • ถ้าเยี่ยมแล้วและสีเหมือน v → ไม่ใช่ Bipartite
  3. คืนค่า true หากไม่พบข้อขัดแย้ง

ตัวอย่างโค้ด 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);

เอาต์พุต

1