home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

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

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

  1. กราฟต้อง connected (ทุก vertex ไปถึงกันได้)
  2. มี vertex แค่ 1 จุดที่ out-degree = in-degree + 1 (จุดเริ่ม)
  3. มี vertex แค่ 1 จุดที่ in-degree = out-degree + 1 (จุดสิ้นสุด)
  4. vertex ที่เหลือต้องมี in-degree = out-degree

อัลกอริทึม

  • DFS ตรวจสอบ connectivity
  • นับ in-degree และ out-degree ทุก vertex
  • ตรวจสอบเงื่อนไขข้างต้น

โค้ดสำคัญ

bool hasEulerPath() {
    if (!isConnected()) return false;
    vector<int> in(NODE,0), out(NODE,0);
    for (int i=0; i

ผลลัพธ์


Euler Path Found.