Thuật toán Kruskal

Thuật toán Kruskal là một thuật toán tìm cây khung nhỏ nhất trong đồ thị có trọng số. Thuật toán này được đặt tên theo nhà toán học Joseph Kruskal và được công bố lần đầu tiên vào năm 1956.

Các bước của thuật toán

Thuật toán Kruskal bắt đầu bằng cách sắp xếp tất cả các cạnh của đồ thị theo thứ tự tăng dần theo trọng số. Sau đó, thuật toán duyệt qua từng cạnh của đồ thị và thêm cạnh đó vào cây khung nếu cạnh đó không tạo thành chu trình với các cạnh đã được thêm vào cây khung trước đó. Thuật toán tiếp tục thêm cạnh cho đến khi tất cả các đỉnh trong đồ thị đều đã được đưa vào cây khung hoặc không còn cạnh để thêm vào cây khung nữa.

Dưới đây là đoạn mã Python mẫu cho thuật toán Kruskal:

def kruskal(graph):
    parent = dict()
    rank = dict()

    def make_set(vertex):
        parent[vertex] = vertex
        rank[vertex] = 0

    def find(vertex):
        if parent[vertex] != vertex:
            parent[vertex] = find(parent[vertex])
        return parent[vertex]

    def union(vertex1, vertex2):
        root1 = find(vertex1)
        root2 = find(vertex2)
        if root1 != root2:
            if rank[root1] > rank[root2]:
                parent[root2] = root1
            else:
                parent[root1] = root2
                if rank[root1] == rank[root2]: rank[root2] += 1

    for vertex in graph['vertices']:
        make_set(vertex)

    minimum_spanning_tree = set()
    edges = list(graph['edges'])
    edges.sort()
    for edge in edges:
        weight, vertex1, vertex2 = edge
        if find(vertex1) != find(vertex2):
            union(vertex1, vertex2)
            minimum_spanning_tree.add(edge)

    return minimum_spanning_tree

Các tham số

Thuật toán Kruskal cần một tham số duy nhất là đồ thị có trọng số. Đồ thị này có thể được biểu diễn dưới dạng một danh sách các cạnh, trong đó mỗi cạnh được biểu diễn bởi một bộ ba (trọng số, đỉnh bắt đầu, đỉnh kết thúc).