Thuật toán Fleury được dùng để hiển thị đường đi Euler hoặc chu trình Euler từ một đồ thị cho trước. Trong thuật toán này, bắt đầu từ một cạnh, nó cố gắng di chuyển đến các đỉnh kề khác bằng cách loại bỏ các đỉnh trước đó. Sử dụng thủ thuật này, đồ thị trở nên đơn giản hơn ở mỗi bước để tìm đường đi hoặc chu trình Euler.
Chúng ta cần kiểm tra một số quy tắc để lấy đường đi hoặc chu trình:
- Đồ thị phải là đồ thị Euler.
- Khi có hai cạnh, một là cầu (bridge), một không phải cầu, chúng ta phải chọn cạnh không phải cầu trước.
Việc chọn đỉnh bắt đầu cũng phức tạp: nếu đồ thị không có đỉnh bậc lẻ, ta có thể chọn bất kỳ đỉnh nào làm điểm bắt đầu; ngược lại nếu có đỉnh bậc lẻ, phải chọn đỉnh đó trước.
Đầu vào
Ma trận kề của đồ thị:
| 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 |
Đầu ra
Đường đi hoặc Chu trình Euler: 1--0 0--2 2--1 1--3 3--0 0--4 4--3 3—2
Thuật toán
timDinhBatDau(dothi)
Đầu vào: Đồ thị cho trước. Đầu ra: Tìm đỉnh bắt đầu cho thuật toán.
Bắt đầu
với mọi đỉnh i trong đồ thị, làm
bac := 0
với mọi đỉnh j kề với i, làm
bac := bac + 1
kết thúc
nếu bac là lẻ, thì
trả về i
kết thúc nếu
kết thúc vòng lặp
khi tất cả bậc đều chẵn trả về 0
Kết thúc
laCau(u, v)
Đầu vào: Nút bắt đầu và nút kết thúc. Đầu ra: True khi u và v tạo thành cầu.
Bắt đầu
bac := 0
với mọi đỉnh i kề với v, làm
bac := bac + 1
kết thúc
nếu bac > 1, thì
trả về false
trả về true
Kết thúc
fleuryAlgorithm(batdau)
Đầu vào: Đỉnh bắt đầu. Đầu ra: Hiển thị đường đi hoặc chu trình Euler.
Bắt đầu
canh := lấy số cạnh trong đồ thị // không khởi tạo lại ở đệ quy sau
với mọi đỉnh v kề với batdau, làm
nếu canh <= 1 HOẶC laCau(batdau, v) là false, thì
hiển thị đường đi từ batdau và v
loại bỏ cạnh (batdau,v) khỏi đồ thị
giảm canh đi 1
fleuryAlgorithm(v)
kết thúc nếu
kết thúc vòng lặp
Kết thúc
Ví dụ mã C++
#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 timDinhBatDau(){
for(int i = 0; i<NODE; i++){
int bac = 0;
for(int j = 0; j<NODE; j++){
if(tempGraph[i][j])
bac++; // tăng bậc khi tìm thấy cạnh kết nối
}
if(bac % 2 != 0) // khi bậc của đỉnh là lẻ
return i; // i là nút có bậc lẻ
}
return 0; // khi tất cả đỉnh đều có bậc chẵn, bắt đầu từ 0
}
bool laCau(int u, int v){
int bac = 0;
for(int i = 0; i<NODE; i++)
if(tempGraph[v][i])
bac++;
if(bac>1){
return false; // cạnh không tạo thành cầu
}
return true; // cạnh tạo thành cầu
}
int demCanh(){
int count = 0;
for(int i = 0; i<NODE; i++)
for(int j = i; j<NODE; j++)
if(tempGraph[i][j])
count++;
return count; // đếm số cạnh trong đồ thị
}
void fleuryAlgorithm(int batdau){
static int canh = demCanh();
for(int v = 0; v<NODE; v++){
if(tempGraph[batdau][v]){ // khi cạnh (u,v) tồn tại và không tạo cầu
if(canh <= 1 || !laCau(batdau, v)){
cout << batdau << "--" << v << " ";
tempGraph[batdau][v] = tempGraph[v][batdau] = 0; // loại bỏ cạnh khỏi đồ thị
canh--; // giảm số cạnh
fleuryAlgorithm(v);
}
}
}
}
int main(){
for(int i = 0; i<NODE; i++) // sao chép đồ thị chính sang tempGraph
for(int j = 0; j<NODE; j++)
tempGraph[i][j] = graph[i][j];
cout << "Đường đi hoặc Chu trình Euler: ";
fleuryAlgorithm(timDinhBatDau());
}
Kết quả đầu ra
Đường đi hoặc Chu trình Euler: 1--0 0--2 2--1 1--3 3--0 0--4 4--3 3—2