Thuật toán Fleury

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.

Ta phải 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 là không phải cầu, 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 khá phức tạp, ta không thể dùng bất kỳ đỉnh nào làm điểm bắt đầu. 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, khi có một đỉnh bậc lẻ, ta phải chọn đỉnh đó trước.

Thuật toán

findStartVert(graph)
Đầu vào: Đồ thị cho trước.
Đầu ra: Tìm đỉnh bắt đầu để chạy thuật toán.
Bắt đầu
  với mọi đỉnh i trong đồ thị, thực hiện
    deg := 0
    với mọi đỉnh j kề với i, thực hiện
      deg := deg + 1
    kết thúc
    nếu deg là lẻ thì
      trả về i
  kết thúc
  khi tất cả bậc đều chẵn trả về 0
Kết thúc

dfs(prev, start, visited)
Đầu vào: Đỉnh trước và đỉnh bắt đầu để thực hiện DFS, và danh sách visited.
Đầu ra: Đếm số nút sau DFS.
Bắt đầu
  count := 1
  visited[start] := true
  với mọi đỉnh u trong đồ thị, thực hiện
    nếu prev không phải u thì
      nếu u chưa được thăm thì
        nếu start và u kết nối thì
          count := count + dfs(start, u, visited)
        kết thúc nếu
      kết thúc nếu
    kết thúc nếu
  kết thúc
  trả về count
Kết thúc

isBridge(u, v)
Đầu vào: Đỉnh bắt đầu và đỉnh kết thúc.
Đầu ra: True khi u và v tạo thành một cầu.
Bắt đầu
  deg := 0
  với mọi đỉnh i kề với v, thực hiện
    deg := deg + 1
  kết thúc
  nếu deg > 1 thì
    trả về false
  trả về true
Kết thúc

fleuryAlgorithm(start)
Đầu vào: Đỉnh bắt đầu.
Đầu ra: Hiển thị đường đi hoặc chu trình Euler.
Bắt đầu
  edge := lấy số cạnh trong đồ thị
  // nó sẽ không khởi tạo lại trong các lần gọi đệ quy sau
  v_count = số nút
  // giá trị này cũng không khởi tạo lại trong đệ quy sau
  với mọi đỉnh v kề với start, thực hiện
    tạo mảng visited và điền giá trị false
    nếu isBridge(start, v) thì giảm v_count đi 1
    cnt = dfs(start, v, visited)
    nếu hiệu giữa cnt và v_count <= 2 thì
      in cạnh (start → v)
      nếu isBridge(v, start) thì giảm v_count đi 1
      xóa cạnh từ start và v
      giảm edge đi 1
      fleuryAlgorithm(v)
    kết thúc nếu
  kết thúc
Kết thúc

Ví dụ (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++; // tăng bậc khi tìm thấy cạnh kết nối
    }
    if(deg % 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 bậc chẵn, bắt đầu từ 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; // cạnh không tạo cầu
  }
  return true; // cạnh tạo thành cầu
}

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; // xóa cạnh khỏi đồ thị
        edge--;
        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 << "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