Thuật toán Prim

Thuật toán Prim 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 người Mỹ Robert Prim và được công bố lần đầu tiên vào năm 1957.

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

Thuật toán Prim bắt đầu bằng cách chọn một đỉnh bất kỳ trong đồ thị làm đỉnh bắt đầu, và đưa đỉnh này vào tập các đỉnh đã xét. Sau đó, thuật toán duyệt qua tất cả các cạnh nối đỉnh đã xét với đỉnh chưa xét và chọn cạnh có trọng số nhỏ nhất để thêm đỉnh mới vào tập các đỉnh đã xét. Thuật toán tiếp tục duyệt qua các cạnh và thêm đỉnh mới cho đến khi tất cả các đỉnh trong đồ thị đều đã được đưa vào tập các đỉnh đã xét hoặc không còn cạnh nối đỉnh đã xét với đỉnh chưa xét.

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

import heapq

def prim(graph, start):
    mst = []
    visited = set([start])
    edges = [
        (cost, start, to)
        for to, cost in graph[start].items()
    ]
    heapq.heapify(edges)

    while edges:
        cost, frm, to = heapq.heappop(edges)
        if to not in visited:
            visited.add(to)
            mst.append((cost, frm, to))

            for to_next, cost in graph[to].items():
                if to_next not in visited:
                    heapq.heappush(edges, (cost, to, to_next))

    return mst

Các tham số

Thuật toán Prim cần hai tham số sau:

• Đồ thị có trọng số: đây là đồ thị mà thuật toán sẽ tìm cây khung nhỏ nhất trên.
• Đỉnh bắt đầu: đỉnh mà thuật toán bắt đầu tìm cây khung nhỏ nhất từ.

Thuật toán Prim là một trong những thuật toán quan trọng trong lý thuyết đồ thị và được sử dụng rộng rãi trong các ứng dụng thực tế như hệ thống điều khiển và quản lý mạng.

Để sử dụng thuật toán Prim, bạn cần biết cách biểu diễn đồ thị và trọng số cạnh dưới dạng dữ liệu. Bạn cũng cần chọn đỉnh bắt đầu để tìm cây khung nhỏ nhất từ đó.