ปัญหาวงจรแฮมิลตัน (Hamiltonian Cycle)

บทนำ

ในกราฟไม่มีทิศทาง (Undirected Graph) เส้นทางแฮมิลตัน (Hamiltonian Path) คือเส้นทางที่ผ่านทุกโหนด (Vertex) ครบเพียงครั้งเดียว ส่วนวงจรแฮมิลตัน (Hamiltonian Cycle) คือเส้นทางแฮมิลตันที่มีเส้นขอบเชื่อมจากโหนดสุดท้ายกลับไปยังโหนดแรก

ปัญหานี้คือการตรวจสอบว่ากราฟมีวงจรแฮมิลตันหรือไม่ และพิมพ์วงจรออกมาหากมี

อินพุตและเอาต์พุต

Input: เมทริกซ์ติดกันของกราฟ G(V, E)
Output: อัลกอริทึมพบเส้นทางแฮมิลตันคือ (0, 1, 2, 4, 3, 0) กราฟนี้มีเส้นทางแฮมิลตันอื่นอีก หากไม่มีจะคืนค่า false

อัลกอริทึม

isValid(v, k)

Input: โหนด v และตำแหน่ง k
Output: ตรวจสอบว่าการวาง v ที่ตำแหน่ง k ถูกต้องหรือไม่

Begin
    if ไม่มีเส้นขอบระหว่างโหนด(k-1) ถึง v then return false
    if v ถูกใช้ไปแล้ว then return false
    return true
End

cycleFound(node k)

Input: โหนดของกราฟ
Output: True ถ้ามีวงจรแฮมิลตัน, มิฉะนั้น false

Begin
    if รวมโหนดครบทุกตัวแล้ว then
        if มีเส้นขอบระหว่างโหนด k และ 0 then return true
        else return false
    สำหรับโหนด v ทุกตัว ยกเว้นจุดเริ่มต้น do
        if isValid(v, k) then
            ใส่ v เข้าไปในเส้นทาง
            if cycleFound(k+1) == true then return true
            มิฉะนั้น นำ v ออกจากเส้นทาง (Backtrack)
    done
    return false
End

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

#include<iostream>
#define NODE 5
using namespace std;

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

int path[NODE];

void displayCycle() {
    cout << "Cycle: ";
    for (int i = 0; i < NODE; i++) cout << path[i] << " ";
    cout << path[0] << endl;  // พิมพ์โหนดแรกอีกครั้ง
}

bool isValid(int v, int k) {
    if (graph[path[k-1]][v] == 0) return false;  // ไม่มีเส้นขอบ
    for (int i = 0; i < k; i++)                  // โหนดถูกใช้ไปแล้ว
        if (path[i] == v) return false;
    return true;
}

bool cycleFound(int k) {
    if (k == NODE) {
        if (graph[path[k-1]][path[0]] == 1) return true;
        else return false;
    }
    for (int v = 1; v < NODE; v++) {
        if (isValid(v, k)) {
            path[k] = v;
            if (cycleFound(k+1) == true) return true;
            path[k] = -1;  // backtrack
        }
    }
    return false;
}

bool hamiltonianCycle() {
    for (int i = 0; i < NODE; i++) path[i] = -1;
    path[0] = 0;  // โหนดแรกเป็น 0
    if (cycleFound(1) == false) {
        cout << "Solution does not exist" << endl;
        return false;
    }
    displayCycle();
    return true;
}

int main() { hamiltonianCycle(); }

ผลลัพธ์

Cycle: 0 1 2 4 3 0