Mô phỏng thuật toán Cây khung nhỏ nhất (Prim)

Prim's MST · Nhóm: Đồ thị

Cây khung nhỏ nhất (Prim) (Prim's MST), nhóm Đồ thị.

Mã Python

def prim(adj, start):
    in_tree = {start}
    total = 0
    edges = []
    while len(in_tree) < n:
        best = None
        for u in in_tree:
            for v, w in adj[u]:
                if v not in in_tree and w < best_w:
                    best, best_w = (u, v), w
        in_tree.add(best[1])
        total += best_w
        edges.append(best)
    return edges, total

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.