Pohon rentang minimum (MST) menghubungkan semua simpul dari graf berbobot yang terhubung dengan berat tepi total minimum dan tanpa siklus. Kruskal dan Prim adalah dua algoritma greedy klasik.
Kruskal (urutkan tepi, union-find)
Urutkan semua tepi berdasarkan bobot; tambahkan tepi termurah yang tidak membentuk siklus.
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