Cây khung nhỏ nhất là gì: thuật toán Kruskal và Prim

Cây khung nhỏ nhất giải bài toán gì

Giả sử bạn phải nối nhiều tòa nhà bằng cáp, nhiều thị trấn bằng đường, hoặc nhiều máy chủ bằng liên kết mạng, và mỗi kết nối khả dĩ có một chi phí. Bạn muốn mọi nơi đều được kết nối (trực tiếp hoặc gián tiếp) với tổng chi phí thấp nhất. Các kết nối thừa tạo thành vòng không bao giờ cần thiết, nên đáp án là một cây: V nút được nối bằng đúng V − 1 cạnh. Cây đó chính là cây khung nhỏ nhất.

MST không phải là cây đường đi ngắn nhất. Nó tối thiểu hóa tổng trọng số của mọi cạnh, chứ không phải khoảng cách từ một nút xuất phát đến các nút khác.

Vì sao lựa chọn tham lam đúng: tính chất lát cắt (cut property)

Chia các nút thành hai nhóm bất kỳ. Trong các cạnh nối giữa hai nhóm, cạnh nhẹ nhất thuộc về một cây khung nhỏ nhất nào đó. Cả hai thuật toán dựa vào sự thật này:

Nếu mọi trọng số cạnh khác nhau, MST là duy nhất, nên cả hai thuật toán trả về cùng một cây. Khi có trọng số bằng nhau, có thể có nhiều MST với cùng tổng trọng số.

Ví dụ từng bước

Đồ thị vô hướng với 5 nút và các cạnh A–B 4, A–C 3, B–C 1, B–D 2, C–D 4, D–E 2, C–E 5.

Thuật toán Kruskal, các cạnh được sắp theo trọng số:

Thuật toán Prim từ A: cạnh rẻ nhất đi ra khỏi {A} là A–C (3); từ {A, C} là C–B (1); từ {A, B, C} là B–D (2); từ {A, B, C, D} là D–E (2). Cùng một cây, tổng trọng số 3 + 1 + 2 + 2 = 8.

Thuật toán Kruskal trong Python

Union-find giữ một con trỏ nút cha cho mỗi nút. find trả về đại diện của thành phần chứa một nút, và hai nút liên thông chính xác khi chúng có cùng đại diện.

def kruskal(nodes, edges):
    parent = {n: n for n in nodes}

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]   # path halving
            x = parent[x]
        return x

    tree, total = [], 0
    for w, u, v in sorted(edges):
        ru, rv = find(u), find(v)
        if ru != rv:                          # different components: no cycle
            parent[ru] = rv
            tree.append((u, v, w))
            total += w
    return tree, total

nodes = "ABCDE"
edges = [(4, "A", "B"), (3, "A", "C"), (1, "B", "C"), (2, "B", "D"),
         (4, "C", "D"), (2, "D", "E"), (5, "C", "E")]
print(kruskal(nodes, edges))
# ([('B', 'C', 1), ('B', 'D', 2), ('D', 'E', 2), ('A', 'C', 3)], 8)

Union-find đầy đủ còn dùng hợp theo hạng (rank) hoặc kích thước để giữ cây thấp. Riêng path halving đã nhanh trong thực tế. Bạn có thể dừng vòng lặp sớm khi cây đã có V − 1 cạnh.

Thuật toán Prim trong Python

Thuật toán Prim cần danh sách kề. Nó dùng xóa lười giống thuật toán Dijkstra: đẩy mọi cạnh đi ra khỏi cây, và bỏ qua các cạnh có đầu kia đã nằm trong cây.

import heapq
from collections import defaultdict

def prim(edges, start):
    graph = defaultdict(list)
    for w, u, v in edges:
        graph[u].append((w, u, v))
        graph[v].append((w, v, u))
    in_tree = {start}
    heap = list(graph[start])
    heapq.heapify(heap)
    tree, total = [], 0
    while heap:
        w, u, v = heapq.heappop(heap)
        if v in in_tree:
            continue
        in_tree.add(v)
        tree.append((u, v, w))
        total += w
        for edge in graph[v]:
            if edge[2] not in in_tree:
                heapq.heappush(heap, edge)
    return tree, total

print(prim(edges, "A"))
# ([('A', 'C', 3), ('C', 'B', 1), ('B', 'D', 2), ('D', 'E', 2)], 8)

Độ phức tạp thời gian và không gian

Vì E tối đa là V², log E tối đa là 2 log V, nên O(E log E) và O(E log V) cùng bậc.

Biến thể và lỗi thường gặp

• Đồ thị không liên thông: không có cây khung. Khi đó Kruskal trả về rừng khung nhỏ nhất (mỗi thành phần một cây); Prim từ một điểm xuất phát chỉ bao phủ thành phần của điểm đó. Hãy kiểm tra cây có V − 1 cạnh.
• Cây khung lớn nhất: sắp xếp cạnh theo thứ tự giảm dần (hoặc đổi dấu trọng số). Trọng số âm không ảnh hưởng đến cả hai thuật toán.
• Đồ thị có hướng cần thuật toán khác (arborescence nhỏ nhất, Chu-Liu/Edmonds); Kruskal và Prim không áp dụng được.
• Phân cụm: chạy Kruskal và dừng khi còn k thành phần. Kết quả là phân cụm liên kết đơn (single-linkage) thành k nhóm.
• Thuật toán Borůvka, từ năm 1926, thêm cùng lúc cạnh rẻ nhất từ mỗi thành phần và song song hóa tốt.

Khi nào dùng và ứng dụng thực tế

• Thiết kế mạng: cách rẻ nhất để nối các địa điểm bằng cáp, ống hoặc đường, khi bất kỳ bố cục liên thông nào cũng chấp nhận được.
• Thuật toán xấp xỉ: MST cho một hành trình dài không quá gấp đôi độ dài tối ưu của bài toán người bán hàng (traveling salesman) metric.
• Phân cụm và phân đoạn ảnh bằng cách cắt các cạnh nặng nhất của MST.
• Bài phỏng vấn: min cost to connect all points, connecting cities with minimum cost, optimize water distribution in a village.