home

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

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

Eulerian Cycle (Circuit) ในกราฟไม่มีทิศทาง เงื่อนไขเข้มงวดกว่า Path:

  1. กราฟต้อง connected
  2. ทุก vertex ต้องมี degree เป็นเลขคู่ (oddDegree = 0)

โค้ดสำคัญ

int hasEulerianCircuit() {
    if (!isConnected()) return 0;
    vector<int> degree(NODE, 0);
    int oddDegree = 0;
    for (int i=0; i

ผลลัพธ์


The graph has Eulerian Circuit.


ต่างจาก Euler Path ที่ยอมรับ vertex คี่ 2 จุดได้