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

Thuật toán Hopcroft-Karp là một phương pháp hiệu quả để tìm kiếm ghép đôi cực đại trong đồ thị hai phía. Đây là một trong những thuật toán được áp dụng rộng rãi trong lý thuyết đồ thị và lập trình ứng dụng. Trong bài viết này, chúng ta sẽ tìm hiểu cách cài đặt thuật toán này bằng ngôn ngữ lập trình cụ thể.

Khái niệm cơ bản về đồ thị hai phía

Đồ thị hai phía (bipartite graph) là một loại đồ thị mà tập hợp đỉnh có thể chia thành hai tập con độc lập, sao cho không có hai đỉnh nào trong cùng một tập con có cạnh nối với nhau. Ghép đôi (matching) trong đồ thị là một tập hợp các cạnh sao cho mỗi đỉnh chỉ thuộc về một cạnh. Ghép đôi cực đại (maximum matching) là ghép đôi có số lượng cạnh lớn nhất có thể.

Nguyên lý của thuật toán Hopcroft-Karp

Thuật toán Hopcroft-Karp thực hiện việc tìm kiếm ghép đôi cực đại bằng cách lặp đi lặp lại hai bước chính:

1. Tìm kiếm đường tăng (augmenting path): Sử dụng thuật toán BFS (tìm kiếm theo chiều rộng) để tìm kiếm tất cả các đường tăng có độ dài ngắn nhất.
2. Tăng mức ghép đôi: Sử dụng thuật toán DFS (tìm kiếm theo chiều sâu) để tăng kích thước ghép đôi bằng cách thêm các cạnh của các đường tăng tìm được vào ghép đôi hiện tại.

Cài đặt thuật toán Hopcroft-Karp bằng Python

Để cài đặt thuật toán này, chúng ta cần hai hàm chính: hàm BFS và hàm DFS.

from collections import deque

def bfs():
    queue = deque()
    for u in range(1, n + 1):
        if pair_u[u] == 0:
            dist[u] = 0
            queue.append(u)
        else:
            dist[u] = float('inf')
    dist[0] = float('inf')
    
    while queue:
        u = queue.popleft()
        if dist[u] < dist[0]:
            for v in adj[u]:
                if dist[pair_v[v]] == float('inf'):
                    dist[pair_v[v]] = dist[u] + 1
                    queue.append(pair_v[v])
    return dist[0] != float('inf')

def dfs(u):
    if u != 0:
        for v in adj[u]:
            if dist[pair_v[v]] == dist[u] + 1:
                if dfs(pair_v[v]):
                    pair_v[v] = u
                    pair_u[u] = v
                    return True
        dist[u] = float('inf')
        return False
    return True

def hopcroft_karp():
    matching = 0
    while bfs():
        for u in range(1, n + 1):
            if pair_u[u] == 0 and dfs(u):
                matching += 1
    return matching

# Khởi tạo đồ thị
n = 4  # Số lượng đỉnh trong tập U
m = 4  # Số lượng đỉnh trong tập V
adj = {
    1: [1, 2],
    2: [1, 3],
    3: [2],
    4: [2, 4]
}
pair_u = [0] * (n + 1)
pair_v = [0] * (m + 1)
dist = [0] * (n + 1)

# Thực thi thuật toán
print("Maximum matching is:", hopcroft_karp())

Giải thích mã lệnh:

• Khởi tạo:

  • pair_u và pair_v là mảng lưu trữ ghép đôi hiện tại cho các đỉnh trong tập U và V.
  • dist là mảng lưu trữ khoảng cách từ các đỉnh tới đỉnh tự do trong Bước BFS.

• Hàm BFS:

  • Khởi tạo khoảng cách của các đỉnh tự do là 0 và tất cả các đỉnh còn lại là vô cùng.
  • Thực hiện duyệt đồ thị từ các đỉnh tự do.

• Hàm DFS:

  • Từ các đỉnh tự do, dfs thực hiện tìm kiếm đường tăng và cập nhật ghép đôi.

• Hàm hopcroft_karp:

  • Lặp lại hai bước BFS và DFS cho tới khi không còn đường tăng nào.

Thuật toán Hopcroft-Karp giúp tìm kiếm ghép đôi cực đại trong đồ thị hai phía một cách hiệu quả, với độ phức tạp thời gian là (O(\sqrt{V}E)). Điều này làm cho nó trở nên lý tưởng cho nhiều ứng dụng thực tiễn trong tin học và toán học.