მინიმალური spanning tree (MST) აერთებს შეწონილი, დაკავშირებული გრაფის ყველა წვეროს მინიმალური მთლიანი კიდის წონით და ციკლების გარეშე. Kruskal და Prim ორი კლასიკური ალუბლის ალგორითმია.
Kruskal (დალაგეთ კიდეები, union-find)
დალაგეთ ყველა კიდე წონის მიხედვით; დაამატეთ ყველაზე იაფი კიდე, რომელიც ციკლს არ ქმნის.
python
():
parent = ((n))
():
parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
x
mst, total = [],
w, u, v (edges):
ru, rv = find(u), find(v)
ru != rv:
parent[ru] = rv
mst.append((u, v, w)); total += w
mst, total