ตรวจสอบ Eulerian Path ใน Undirected Graph ด้วย C++

Eulerian Path ในกราฟไม่มีทิศทาง (Undirected Graph) เงื่อนไข:

1. กราฟต้อง connected
2. ไม่มี vertex คี่เลย = Euler Circuit (ซึ่งก็เป็น Euler Path)
3. มี vertex คี่เพียง 2 จุด = Euler Path
4. มากกว่า 2 จุด = ไม่มี Euler Path

อัลกอริทึม

• DFS เช็ค connectivity
• นับ degree ของแต่ละ vertex
• นับจำนวน vertex ที่มี degree คี่

โค้ดสำคัญ

int isEulerian() {
    if (!isConnected()) return 0;
    vector<int> degree(NODE, 0);
    int oddDegree = 0;
    for (int i=0; i 2) return 0;
    return 1; // 0 = circuit, 2 = path
}

ผลลัพธ์

The graph has Eulerian path.