การตรวจสอบกราฟแบ่งสองส่วน (Check if Graph is Bipartite)

กราฟเรียกว่า "กราฟแบ่งสองส่วน" (Bipartite Graph) เมื่อจุด (Vertices) สามารถแบ่งออกเป็นสองเซตอิสระได้ โดยที่ทุกเส้นเชื่อม (Edge) จะเชื่อมระหว่างเซตแรกและเซตที่สองเท่านั้น ไม่มีเส้นเชื่อมภายในเซตเดียวกัน

การตรวจสอบสามารถทำได้โดยการระบายสีจุด (Vertex Coloring) จุดในเซตเดียวกันจะมีสีเดียวกัน เซตต่างกันจะมีสีต่างกัน

การรับค่าและแสดงผล

Input: เมทริกซ์ตyacency
0 1 1 1 0 0
1 0 0 1 1 0
1 0 0 1 0 1
1 1 1 0 1 1
0 1 0 1 0 1
0 0 1 1 1 0

Output: The graph is bipartite.

อัลกอริทึม

isBipartite(source)

Input: โหนดต้นทาง

Output: True ถ้ากราฟเป็น Bipartite

Begin
  กำหนดคิวว่าง และอาร์เรย์สี colorArray
  เริ่มต้นไม่มีจุดใดถูกระบายสี
  ระบายสีโหนดต้นทางเป็นสีแดง
  เพิ่มต้นทางเข้าในคิว
  
  while คิวไม่ว่าง do
    นำโหนด u ออกจากคิว
    if มี self-loop แล้ว return false
    
    for ทุกโหนด v ที่ติดกับ u do
      if v ยังไม่มีสี then
        if colorArray[u] = แดง then colorArray[v] := น้ำเงิน
        else if colorArray[u] = น้ำเงิน then colorArray[v] := แดง
        เพิ่ม v เข้าคิว
      else if colorArray[v] = colorArray[u] then
        return false
      end if
    done
  done
  
  return true
End

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

#include <iostream>
#include <string>
#include <queue>
#define NODE 6
using namespace std;

int graph[NODE][NODE] = {
  {0, 1, 0, 0, 0, 1},
  {1, 0, 1, 0, 0, 0},
  {0, 1, 0, 1, 0, 0},
  {0, 0, 1, 0, 1, 0},
  {0, 0, 0, 1, 0, 1},
  {1, 0, 0, 0, 1, 0}
};

bool isBipartite(int source) {
  queue<int> qu;
  string colorArray[NODE];
  
  for(int i = 0; i < NODE; i++) colorArray[i] = "No Color";
  colorArray[source] = "Red";
  qu.push(source);
  
  while(!qu.empty()) {
    int u = qu.front(); qu.pop();
    
    if(graph[u][u] == 1) return false;
    
    for(int v = 0; v < NODE; v++) {
      if(graph[u][v] != 0 && colorArray[v] == "No Color") {
        if(colorArray[u] == "Red") colorArray[v] = "Blue";
        else if(colorArray[u] == "Blue") colorArray[v] = "Red";
        qu.push(v);
      } else if(graph[u][v] != 0 && colorArray[v] == colorArray[u]) {
        return false;
      }
    }
  }
  return true;
}

int main() {
  bool check = isBipartite(0);
  if(check) cout << "The graph is bipartite." << endl;
  else cout << "The graph is not bipartite." << endl;
}

ผลลัพธ์

The graph is bipartite.