×

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

Avatar of admin
admin 27 Views

Để khám phá và xây dựng các chu trình Euler trong đồ thị, thuật toán Hierholzer là một trong những phương pháp được sử dụng phổ biến và hiệu quả. Việc cài đặt thuật toán này trong lập trình đòi hỏi sự hiểu biết vững chắc về đồ thị và cấu trúc dữ liệu. Hãy cùng đi vào chi tiết về cách triển khai thuật toán này.

Khái niệm cơ bản

Thuật toán Hierholzer dùng để tìm chu trình Euler trong đồ thị. Một chu trình Euler là một chu trình đi qua mỗi cạnh của đồ thị đúng một lần. Điều kiện để tồn tại chu trình Euler trong đồ thị vô hướng là:

  1. Đồ thị phải liên thông.
  2. Mỗi đỉnh trong đồ thị phải có bậc chẵn.

Các bước thực hiện

  1. Kiểm tra điều kiện tồn tại chu trình Euler: Đầu tiên, cần kiểm tra xem đồ thị có phải là liên thông và mỗi đỉnh đều có bậc chẵn hay không. Nếu điều kiện này không được thỏa mãn, hàm sẽ trả về rằng chu trình Euler không tồn tại.

  2. Bắt đầu từ một đỉnh bất kỳ: Chọn một đỉnh bất kỳ có bậc khác 0.

  3. Xây dựng chu trình ban đầu: Sử dụng cơ chế duyệt để xây dựng một chu trình từ đỉnh đã chọn. Trong quá trình duyệt, loại bỏ các cạnh ra khỏi đồ thị để tránh lặp lại.

  4. Tiếp tục mở rộng chu trình: Nếu có cạnh nào chưa được duyệt, chọn một đỉnh nằm trên chu trình hiện tại và lặp lại quá trình để xây dựng chu trình con từ đỉnh đó. Gộp chu trình con này vào chu trình hiện tại.

  5. Hoàn thành chu trình Euler: Khi tất cả các cạnh đều đã được duyệt, chu trình hoàn thiện chính là chu trình Euler.

Ví dụ Cài đặt bằng Python

Dưới đây là một ví dụ về cách cài đặt thuật toán này trong Python:

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.graph = defaultdict(list)
        self.V = vertices

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

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

    def find_eulerian_cycle(self):
        u = 0
        for i in range(self.V):
            if len(self.graph[i]) > 0:
                u = i
                break
        
        curr_path = [u]
        cycle = []

        while curr_path:
            curr_vertex = curr_path[-1]

            if self.graph[curr_vertex]:
                next_vertex = self.graph[curr_vertex][0]
                curr_path.append(next_vertex)
                self.remove_edge(curr_vertex, next_vertex)
            else:
                cycle.append(curr_path.pop())

        return cycle

    def is_valid_graph(self):
        odd_degree_vertices = 0
        for i in range(self.V):
            if len(self.graph[i]) % 2 != 0:
                odd_degree_vertices += 1

        return odd_degree_vertices == 0

# Ví dụ sử dụng
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)
g.add_edge(3, 4)
g.add_edge(4, 0)

if g.is_valid_graph():
    cycle = g.find_eulerian_cycle()
    print("Chu trình Euler: ", cycle)
else:
    print("Đồ thị không có chu trình Euler")

Giải thích đoạn mã

  1. Kiểm tra tính hợp lệ của đồ thị: Hàm is_valid_graph kiểm tra nếu tất cả các đỉnh đều có bậc chẵn.
  2. Xây dựng đồ thị: Hàm add_edge và remove_edge giúp thêm và loại bỏ cạnh từ đồ thị tương ứng.
  3. Tìm chu trình Euler: Hàm find_eulerian_cycle thực hiện việc tìm kiếm chu trình Euler bằng cách duyệt từ đỉnh đầu tiên có cạnh kết nối, sử dụng phương pháp stack để quản lý các đỉnh hiện tại và chu trình.

Kết luận

Như vậy, thuật toán này cho phép tìm kiếm chu trình Euler trong đồ thị một cách hiệu quả. Việc cài đặt trong lập trình đòi hỏi sự cẩn thận trong việc quản lý các cạnh và đỉnh, bảo đảm không bỏ sót bất kỳ đỉnh hay cạnh nào. Hi vọng với bài viết này, bạn đã hiểu thêm về cách cài đặt và ứng dụng thực tiễn của thuật toán.

Comments

Bài viết liên quan