อัลกอริทึม Fleury ใช้เพื่อแสดง Euler path หรือ Euler circuit จากกราฟที่กำหนด ในอัลกอริทึมนี้ เริ่มจากเส้นขอบหนึ่ง แล้วพยายามย้ายไปยังโหนดติดกันโดยการลบโหนดก่อนหน้า ทำให้กราฟง่ายลงในแต่ละขั้นตอนเพื่อหา Euler path หรือ circuit
เราต้องตรวจสอบกฎบางอย่างเพื่อให้ได้ path หรือ circuit −
- กราฟต้องเป็น Euler Graph
- เมื่อมีสองเส้นขอบ หนึ่งเป็น bridge อีกหนึ่งไม่ใช่ bridge เราต้องเลือก non-bridge ก่อน
การเลือกโหนดเริ่มต้นก็ทริกกีเช่นกัน เราไม่สามารถใช้โหนดใดก็ได้เป็นจุดเริ่มต้น หากกราฟไม่มีโหนดที่มี degree คี่ เราสามารถเลือกโหนดใดก็ได้เป็นจุดเริ่มต้น มิฉะนั้นถ้ามีโหนดใดมี degree คี่ เราต้องเลือกโหนดนั้นก่อน
อินพุต − เมทริกซ์ตyacency ของกราฟ
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 |
เอาต์พุต − Euler Path หรือ Circuit: 1--0 0--2 2--1 1--3 3--0 0--4 4--3 3—2
อัลกอริทึม
findStartVert(graph) Input: กราฟที่กำหนด Output: หาโหนดเริ่มต้นสำหรับอัลกอริทึม Begin for all vertex i, in the graph, do deg := 0 for all vertex j, which are adjacent with i, do deg := deg + 1 done if deg is odd, then return i done when all degree is even return 0 End isBridge(u, v) Input: โหนดเริ่มต้นและโหนดสิ้นสุด Output: True เมื่อ u และ v สร้าง bridge Begin deg := 0 for all vertex i which are adjacent with v, do deg := deg + 1 done if deg > 1, then return false return true End fleuryAlgorithm(start) Input: โหนดเริ่มต้น Output: แสดง Euler path หรือ circuit Begin edge := get the number of edges in the graph // จะไม่ initialize ใหม่ในการเรียกซ้ำ for all vertex v, which are adjacent with start, do if edge <= 1 OR isBridge(start, v) is false, then display path from start and v remove edge (start,v) from the graph decrease edge by 1 fleuryAlgorithm(v) done End
ตัวอย่าง
#include<iostream> #include<vector> #define NODE 5 using namespace std; int graph[NODE][NODE] = {{0, 1, 1, 1, 1}, {1, 0, 1, 1, 0}, {1, 1, 0, 1, 0}, {1, 1, 1, 0, 1}, {1, 0, 0, 1, 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++; //เพิ่ม degree เมื่อพบเส้นขอบเชื่อม } if(deg % 2 != 0) //เมื่อ degree ของโหนดเป็นคี่ return i; // i คือโหนดที่มี degree คี่ } return 0; //เมื่อทุกโหนดมี degree คู่ เริ่มจาก 0 } bool isBridge(int u, int v){ int deg = 0; for(int i = 0; i<NODE; i++) if(tempGraph[v][i]) deg++; if(deg>1){ return false; //เส้นขอบไม่ได้สร้าง bridge } return true; //เส้นขอบสร้าง bridge } 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(); for(int v = 0; v<NODE; v++){ if(tempGraph[start][v]){ //เมื่อมีเส้นขอบ (u,v) และไม่ได้สร้าง bridge if(edge <= 1 || !isBridge(start, v)){ cout << start << "--" << v << " "; tempGraph[start][v] = tempGraph[v][start] = 0; //ลบเส้นขอบออกจากกราฟ edge--; //ลดจำนวนเส้นขอบ fleuryAlgorithm(v); } } } } int main(){ for(int i = 0; i<NODE; i++) //คัดลอกกราฟหลักไปยัง tempGraph for(int j = 0; j<NODE; j++) tempGraph[i][j] = graph[i][j]; cout << "Euler Path Or Circuit: "; fleuryAlgorithm(findStartVert()); }ผลลัพธ์
Euler Path Or Circuit: 1--0 0--2 2--1 1--3 3--0 0--4 4--3 3—2
