อัลกอริทึมของฟลูรี (Fleury's Algorithm)

อัลกอริทึมของฟลูรี (Fleury's Algorithm) ใช้สำหรับหาเส้นทางออยเลอร์ (Euler Path) หรือวงจรออยเลอร์ (Euler Circuit) จากกราฟที่กำหนด อัลกอริทึมเริ่มจากเส้นเชื่อมหนึ่งเส้น แล้วพยายามเคลื่อนที่ไปยังโหนดติดกันโดยการลบโหนดก่อนหน้า ทำให้กราฟง่ายขึ้นในแต่ละขั้นตอน

กติกาสำคัญ:

• กราฟต้องเป็นกราฟออยเลอร์
• เมื่อมีสองเส้นเชื่อม หนึ่งเป็นสะพาน (Bridge) อีกเส้นไม่ใช่ ต้องเลือกเส้นที่ไม่ใช่สะพานก่อน

การเลือกโหนดเริ่มต้น: หากกราฟไม่มีโหนดที่มีองศาคี่ สามารถเริ่มจากโหนดไหนก็ได้ แต่ถ้ามีโหนดองศาคี่ ต้องเริ่มจากโหนดนั้น

อัลกอริทึม

findStartVert(graph) - หาโหนดเริ่มต้น

dfs(prev, start, visited) - นับจำนวนโหนดหลัง DFS

isBridge(u, v) - ตรวจสอบว่าเป็นสะพานหรือไม่

fleuryAlgorithm(start) - แสดงเส้นทางออยเลอร์

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

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

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

int tempGraph[NODE][NODE];

int findStartVert() {
  for(int i = 0; i < NODE; i++) {
    int deg = 0;
    for(int j = 0; j < NODE; j++)
      if(tempGraph[i][j]) deg++;
    if(deg % 2 != 0) return i;
  }
  return 0;
}

int dfs(int prev, int start, bool visited[]) {
  int count = 1;
  visited[start] = true;
  for(int u = 0; u < NODE; u++) {
    if(prev != u && !visited[u] && tempGraph[start][u])
      count += dfs(start, u, visited);
  }
  return count;
}

bool isBridge(int u, int v) {
  int deg = 0;
  for(int i = 0; i < NODE; i++)
    if(tempGraph[v][i]) deg++;
  return (deg <= 1);
}

int edgeCount() {
  int count = 0;
  for(int i = 0; i < NODE; i++)
    for(int j = i; j < NODE; j++)
      if(tempGraph[i][j]) count++;
  return count;
}

void fleuryAlgorithm(int start) {
  static int edge = edgeCount();
  static int v_count = NODE;
  
  for(int v = 0; v < NODE; v++) {
    if(tempGraph[start][v]) {
      bool visited[NODE] = {false};
      if(isBridge(start, v)) v_count--;
      
      int cnt = dfs(start, v, visited);
      if(abs(v_count - cnt) <= 2) {
        cout << start << "--" << v << " ";
        if(isBridge(v, start)) v_count--;
        tempGraph[start][v] = tempGraph[v][start] = 0;
        edge--;
        fleuryAlgorithm(v);
      }
    }
  }
}

int main() {
  for(int i = 0; i < NODE; i++)
    for(int j = 0; j < NODE; j++)
      tempGraph[i][j] = graph[i][j];
  
  cout << "Euler Path Or Circuit: ";
  fleuryAlgorithm(findStartVert());
}

ผลลัพธ์

Euler Path Or Circuit: 0--1 1--2 2--3 3--1 1--4 4--5 5--6 6--4 4--7 7--5 5--2 2--0