โปรแกรม C++ ตรวจสอบกราฟมีทิศทาง (Directed Graph) ว่ามี Eulerian Cycle หรือไม่

Eulerian Cycle ในกราฟมีทิศทาง

Euler cycle/circuit คือเส้นทาง ที่เราสามารถเยี่ยมชมทุกขอบ (edge) ได้ทีละขอบเพียงครั้งเดียว เราสามารถใช้จุดยอด (vertices) เดิมได้หลายครั้ง Euler Circuit เป็นประเภทพิเศษของ Euler path เมื่อจุดเริ่มต้นของ Euler path เชื่อมต่อกับจุดสิ้นสุดของ path นั้นๆ แล้ว จะเรียกว่า Euler Circuit

เพื่อตรวจสอบว่ากราฟเป็น Eulerian หรือไม่ เราต้องตรวจสอบ 2 เงื่อนไข

• กราฟต้องเชื่อมต่อกัน (connected)
• อินดีกรี (in-degree) และเอาต์ดีกรี (out-degree) ของแต่ละจุดยอดต้องเท่ากัน

Input - เมทริกซ์ความติดกัน (Adjacency matrix) ของกราฟ

Output - Euler Circuit Found

อัลกอริทึม

traverse(u, visited)

Input - โหนดเริ่มต้น u และโหนดที่เยี่ยมชมแล้วเพื่อทำเครื่องหมายว่าโหนดไหนถูกเยี่ยมชมแล้ว

Output - เยี่ยมชมโหนดที่เชื่อมต่อทั้งหมด

เริ่มต้น
  ทำเครื่องหมาย u ว่าเยี่ยมชมแล้ว
  สำหรับทุกโหนด v ที่ติดกับ u
    ถ้า v ยังไม่ถูกเยี่ยมชม ให้ traverse(v, visited)
สิ้นสุด

isConnected(graph)

Input - กราฟ

Output - True ถ้ากราฟเชื่อมต่อกัน

เริ่มต้น
  ประกาศอาร์เรย์ visited สำหรับทุกโหนด
  สำหรับทุกโหนด u ในกราฟ
    ทำเครื่องหมายทุกโหนดว่าไม่ได้เยี่ยมชม
    traverse(u, visited)
    ถ้ามีโหนดที่ยังไม่ถูกเยี่ยมชมอยู่ ให้คืนค่า false
  คืนค่า true
สิ้นสุด

isEulerCircuit(Graph)

Input - กราฟที่กำหนด

Output - True เมื่อพบ Euler circuit

เริ่มต้น
  ถ้า isConnected() เป็น false ให้คืนค่า false
  ประกาศลิสต์สำหรับนับขอบเข้า (inward) และขอบออก (outward) ของแต่ละโหนด
  สำหรับทุกโหนด i ในกราฟ
    sum := 0
    สำหรับทุกโหนด j ที่เชื่อมต่อกับ i
      เพิ่มขอบเข้า (inward edges) ของโหนด i
      เพิ่ม sum
    จำนวนขอบออกของโหนด i คือ sum
  ถ้ารายการ inward และ outward เหมือนกัน ให้คืนค่า true
  ไม่เช่นนั้น คืนค่า false
สิ้นสุด

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

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

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

void traverse(int u, bool visited[]) {
    visited[u] = true;
    for(int v = 0; v < NODE; v++) {
        if(graph[u][v]) {
            if(!visited[v])
                traverse(v, visited);
        }
    }
}

bool isConnected() {
    bool *vis = new bool[NODE];
    for(int u = 0; u < NODE; u++) {
        for(int i = 0; i < NODE; i++)
            vis[i] = false;
        traverse(u, vis);
        for(int i = 0; i < NODE; i++) {
            if(!vis[i])
                return false;
        }
    }
    return true;
}

bool isEulerCircuit() {
    if(isConnected() == false) {
        return false;
    }
    vector<int> inward(NODE, 0), outward(NODE, 0);
    for(int i = 0; i < NODE; i++) {
        int sum = 0;
        for(int j = 0; j < NODE; j++) {
            if(graph[i][j]) {
                inward[j]++;
                sum++;
            }
        }
        outward[i] = sum;
    }
    if(inward == outward)
        return true;
    return false;
}

int main() {
    if(isEulerCircuit())
        cout << "Euler Circuit Found.";
    else
        cout << "There is no Euler Circuit.";
}

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

Euler Circuit Found.