Thuật toán Fleury được sử dụng để hiển thị đường dẫn Euler hoặc mạch Euler từ một đồ thị nhất định. Trong thuật toán này, bắt đầu từ một cạnh, nó cố gắng di chuyển các đỉnh liền kề khác bằng cách loại bỏ các đỉnh trước đó. Sử dụng thủ thuật này, biểu đồ sẽ trở nên đơn giản hơn trong mỗi bước để tìm đường dẫn hoặc mạch Euler.
Chúng tôi phải kiểm tra một số quy tắc để lấy đường dẫn hoặc mạch -
-
Biểu đồ phải là Đồ thị Euler.
-
Khi có hai cạnh, một cạnh là cầu, một cạnh khác không phải là cầu, lúc đầu chúng ta phải chọn không cầu.
Việc chọn đỉnh xuất phát cũng khó, ta không thể dùng đỉnh nào làm đỉnh xuất phát, nếu đồ thị không có đỉnh bậc lẻ thì ta có thể chọn đỉnh bất kỳ làm điểm bắt đầu, ngược lại khi một đỉnh có bậc lẻ thì ta phải chọn đỉnh đó trước. .
Thuật toán
findStartVert(graph) Input: The given graph. Output: Find the starting vertex to start algorithm. 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 dfs(prev, start, visited) Input: The pervious and start vertex to perform DFS, and visited list. Output: Count the number of nodes after DFS. Begin count := 1 visited[start] := true for all vertex b, in the graph, do if prev is not u, then if u is not visited, then if start and u are connected, then count := count + dfs(start, u, visited) end if end if end if done return count End isBridge(u, v) Input: The start and end node. Output: True when u and v are forming a 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: The starting vertex. Output: Display the Euler path or circuit. Begin edge := get the number of edges in the graph //it will not initialize in next recursion call v_count = number of nodes //this will not initialize in next recursion call for all vertex v, which are adjacent with start, do make visited array and will with false value if isBridge(start, v), then decrease v_count by 1 cnt = dfs(start, v, visited) if difference between cnt and v_count <= 2, then print the edge (start →‡ v) if isBridge(v, start), then decrease v_count by 1 remove edge from start and v decrease edge by 1 fleuryAlgorithm(v) end if done End
Ví dụ
#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++; //increase degree, when connected edge found
}
if(deg % 2 != 0) //when degree of vertices are odd
return i; //i is node with odd degree
}
return 0; //when all vertices have even degree, start from 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){
if(!visited[u]){
if(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++;
if(deg>1) {
return false; //the edge is not forming bridge
}
return true; //edge forming a 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();
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; //remove edge from graph
edge--;
fleuryAlgorithm(v);
}
}
}
}
int main() {
for(int i = 0; i<NODE; i++) //copy main graph to tempGraph
for(int j = 0; j<NODE; j++)
tempGraph[i][j] = graph[i][j];
cout << "Euler Path Or Circuit: ";
fleuryAlgorithm(findStartVert());
} Đầu ra
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