Cài đặt thuật toán Fleury trong lập trình

Thuật toán Fleury là một phương pháp hữu hiệu để tìm chu trình Euler hoặc đường đi Euler trong đồ thị. Chu trình Euler là chu trình trong đồ thị đi qua mỗi cạnh đúng một lần, còn đường đi Euler là đường đi qua mỗi cạnh đúng một lần nhưng có thể không bắt đầu và kết thúc tại cùng một đỉnh. Dưới đây là cách thức cài đặt thuật toán Fleury trong lập trình để giải quyết vấn đề này.

Tổng quan về thuật toán

Thuật toán Fleury làm việc dựa trên nguyên tắc chọn các cạnh trong đồ thị sao cho việc xoá cạnh không làm tăng số lượng thành phần liên thông. Nguyên lý chính của thuật toán là bỏ qua các cạnh cầu (bridges) nếu còn có lựa chọn khác. Điều này giúp đảm bảo rằng đồ thị vẫn sẽ liên thông và có đường đi hoặc chu trình Euler.

Các bước cài đặt thuật toán

1. Chuẩn bị đồ thị: Đồ thị cần được biểu diễn dưới dạng danh sách kề hoặc ma trận kề. Đảm bảo rằng đồ thị đã nhập liệu đầy đủ các đỉnh và cạnh.

2. Kiểm tra đỉnh lẻ: Đầu tiên, kiểm tra xem có đúng 0 hoặc 2 đỉnh có bậc lẻ hay không.

   • Nếu không đúng, không thể có đường đi hoặc chu trình Euler.
   • Nếu có hai đỉnh có bậc lẻ, bắt đầu từ một trong hai đỉnh đó để tạo ra đường đi Euler.
   • Nếu không có đỉnh lẻ, bắt đầu từ bất kỳ đỉnh nào để tạo ra chu trình Euler.

3. Chọn cạnh hợp lệ:

   • Tại mỗi bước, chọn một cạnh từ đỉnh hiện tại sao cho cạnh đó hoặc không là cầu hoặc là lựa chọn duy nhất còn lại.
   • Sử dụng thuật toán DFS hoặc BFS để kiểm tra xem cạnh đó có là cầu hay không.

4. Cập nhật đồ thị: Sau khi chọn cạnh, loại bỏ cạnh đó khỏi đồ thị và di chuyển đến đỉnh tiếp theo.

5. Tiếp tục bước 3 cho đến khi hoàn thành: Lặp lại quá trình này cho đến khi không còn cạnh nào trong đồ thị.

Cài đặt thuật toán trong Python

Dưới đây là bản cài đặt của thuật toán Fleury trong Python:

class Graph:
    def __init__(self, vertices):
        self.graph = {i: [] for i in range(vertices)}
        self.V = vertices

    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

    def rmv_edge(self, u, v):
        self.graph[u].remove(v)
        self.graph[v].remove(u)

    def DFS_count(self, v, visited):
        count = 1
        visited[v] = True
        for i in self.graph[v]:
            if not visited[i]:
                count += self.DFS_count(i, visited)
        return count

    def is_valid_next_edge(self, u, v):
        if len(self.graph[u]) == 1:
            return True

        visited = [False] * self.V
        count1 = self.DFS_count(u, visited)

        self.rmv_edge(u, v)
        visited = [False] * self.V
        count2 = self.DFS_count(u, visited)
        self.add_edge(u, v)

        return False if count1 > count2 else True

    def print_euler_util(self, u):
        for v in self.graph[u][:]:
            if self.is_valid_next_edge(u, v):
                print(f"{u}-{v} ", end="")
                self.rmv_edge(u, v)
                self.print_euler_util(v)

    def print_euler_tour(self):
        u = 0
        for i in range(self.V):
            if len(self.graph[i]) % 2 != 0:
                u = i
                break
        self.print_euler_util(u)

        
# Example usage:
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 3)
g.add_edge(3, 4)
g.add_edge(3, 0)
g.add_edge(3, 2)
g.add_edge(4, 0)

g.print_euler_tour()

Giải thích cài đặt

1. Class Graph: Được sử dụng để biểu diễn đồ thị với hàm khởi tạo nhận số lượng đỉnh.
2. add_edge và rmv_edge: Thêm và xoá cạnh giữa hai đỉnh.
3. DFS_count: Đếm số lượng đỉnh trong đồ thị liên thông bằng DFS.
4. is_valid_next_edge: Kiểm tra xem cạnh có là cầu hay không.
5. print_euler_util: In ra các cạnh của đường đi hoặc chu trình Euler.
6. print_euler_tour: Hàm chính để bắt đầu tìm chu trình hoặc đường đi Euler.

Bằng cách sử dụng thuật toán này, ta có thể xác định một cách hiệu quả đường đi hoặc chu trình Euler trong đồ thị, điều này rất hữu dụng trong nhiều ứng dụng thực tế như lập lịch, quản lý tài nguyên.