Een minimale opspannende boom (MST) verbindt alle hoekpunten van een gewogen, samenhangende graaf met het minimale totale randgewicht en geen cycli. Kruskal en Prim zijn de twee klassieke hebzuchtige algoritmen.
Sorteer alle randen op gewicht; voeg de goedkoopste rand toe die geen cyclus vormt.
def kruskal(n, edges): # edges: (weight, u, v)
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path compression
x = parent[x]
return x
mst, total = [], 0
for w, u, v in sorted(edges): # cheapest first
ru, rv = find(u), find(v)
if ru != rv: # no cycle -> take it
parent[ru] = rv
mst.append((u, v, w)); total += w
return mst, total
Begin bij elk hoekpunt; voeg herhaaldelijk de goedkoopste rand toe die de huidige boom verlaat.
| Kruskal | Prim | |
|---|---|---|
| Aanpak | sorteer randen + union-find | groei vanuit een knoop + heap |
| Tijd | O(E log E) | O(E log V) |
| Beste voor | dunne grafen | dichte grafen |
Gebruik MST voor netwerkontwerp — kabels leggen, waterleidingen, clustering. Beide zijn hebzuchtig en hier aantoonbaar optimaal. Kruskal heeft union-find nodig om cycli efficiënt te vermijden.
MST minimaliseert de kosten van alles verbinden — rechtstreeks toepasbaar op infrastructuur en netwerkindeling.
Het is een duidelijk geval waar hebzucht aantoonbaar optimaal is, wat hebzuchtige-keuze-redenering versterkt.
Kruskal toont ook union-find, een structuur met brede algoritmische bereik.