Et minimalt spanningstre (MST) forbinder alle hjørnepunkter i en vektet, sammenhengende graf med minimum total kantvekt og ingen sykler. Kruskal og Prim er de to klassiske grådige algoritmer.
Sorter alle kanter etter vekt; legg til den billigste kanten som ikke danner en syklus.
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
Start fra et hvilket som helst hjørnepunkt; legg gjentatte ganger til den billigste kanten som forlater det nåværende treet.
| Kruskal | Prim | |
|---|---|---|
| Tilnærming | sorter kanter + union-find | voks fra en node + heap |
| Tid | O(E log E) | O(E log V) |
| Best for | sparsomme grafer | tette grafer |
Bruk MST for nettverksdesign — legging av kabler, vannrør, clustering. Begge er grådige og beviselig optimale her. Kruskal trenger union-find for å unngå sykler effektivt.
MST minimerer kostnadene ved å koble sammen alt — direkte anvendelig på infrastruktur og nettverkslayout.
Det er et rent tilfelle der grådighet beviselig er optimalt, noe som styrker grådige-valgs-resonnering.
Kruskal viser også union-find, en struktur med bred algoritmisk rekkevidde.