โปรแกรม C++ ตรวจสอบกราฟ Bipartite ด้วยอัลกอริทึม 2 สี (2 Color Algorithm)

บทนำ

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

ฟังก์ชันและ Pseudocode

Begin
  1. ฟังก์ชัน isSafe() ตรวจสอบว่าการกำหนดสีปัจจุบันปลอดภัยสำหรับโหนด v
  2. ฟังก์ชัน graphColoringtil(bool g[V][V], int k, int col[], int v):
      ถ้า v == V คืนค่า true
      สำหรับ c = 1 ถึง k:
        ถ้า isSafe(v, g, col, c):
          col[v] = c
          ถ้า graphColoringtil(g, k, col, v+1) == true คืนค่า true
          col[v] = 0
      คืนค่า false
  3. ฟังก์ชัน graphColoring(bool g[V][V], int k):
      เริ่มต้น color[i] = 0
      ถ้า graphColoringtil(g, k, color, 0) == false คืนค่า false
      คืนค่า true
End

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

#include <iostream>
#include <cstdio>
#define V 4
using namespace std;

bool isSafe(int v, bool g[V][V], int col[], int C) {
    for (int i = 0; i < V; i++)
        if (g[v][i] && C == col[i])
            return false;
    return true;
}

bool graphColoringtil(bool g[V][V], int k, int col[], int v) {
    if (v == V)
        return true;
    for (int c = 1; c <= k; c++) {
        if (isSafe(v, g, col, c)) {
            col[v] = c;
            if (graphColoringtil(g, k, col, v + 1) == true)
                return true;
            col[v] = 0;
        }
    }
    return false;
}

ผลลัพธ์

The graph is Bipartite