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

Kruskal MST · Nhóm: Đồ thị

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

Mã Python

def kruskal(nodes, edges):
    edges.sort(key=lambda e: e[2])
    parent = {x: x for x in nodes}
    def find(x):
        while parent[x] != x:
            x = parent[x]
        return x
    total = 0
    for u, v, w in edges:
        if find(u) != find(v):
            parent[find(u)] = find(v)
            total += w
    return total

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