วงจรออยเลอร์ในกราฟมีทิศทาง (Euler Circuit in Directed Graph)

วงจรออยเลอร์ในกราฟมีทิศทาง (Directed Graph) คือเส้นทางที่ผ่านทุกเส้นเชื่อมเพียงครั้งเดียวและกลับมายังจุดเริ่มต้น

เงื่อนไขในการเป็นกราฟออยเลอร์แบบมีทิศทาง:

• กราฟต้องเชื่อมต่อ (Strongly Connected)
• องศาเข้า (In-degree) และองศาออก (Out-degree) ของทุกโหนดต้องเท่ากัน

การรับค่าและแสดงผล

Input: เมทริกซ์ตyacency
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

Output: Euler Circuit Found.

อัลกอริทึม

traverse(u, visited) - DFS ตรวจสอบการเชื่อมต่อ

isConnected(graph) - ตรวจสอบการเชื่อมต่ออย่างแข็งแกร่ง

isEulerCircuit(Graph) - ตรวจสอบวงจรออยเลอร์

Begin
  if isConnected() เป็น false then return false
  
  นับองศาเข้าและองศาออกของแต่ละโหนด
  for ทุกโหนด i do
    sum := 0
    for ทุกโหนด j ที่ติดกับ i do
      เพิ่มองศาเข้าของ j
      เพิ่ม sum
    done
    องศาออกของ i คือ sum
  done
  
  if รายการองศาเข้าและองศาออกเหมือนกัน then return true
  else return false
End

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

#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] && !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()) 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;
  }
  
  return (inward == outward);
}

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

ผลลัพธ์

Euler Circuit Found.