Minimale spenntrær

Gitt en sammenhengende, vektet og urettet graf: hvilken minste kantmengde holder alt sammen til lavest pris? Svaret er et minimalt spenntre (MST) — et tre som spenner alle nodene med minst mulig total kantvekt. MST er skoleeksempelet på at grådighet faktisk gir et globalt optimum, og hele beviset hviler på ett presist begrep: trygge kanter.

Disjunkte mengder (union-find)

Disjunkte mengder vedlikeholder en partisjon av elementer under to operasjoner: Find-Set(x) returnerer representanten for mengden $x$ ligger i, og Union(x, y) slår sammen to mengder. Skogimplementasjonen lar hvert element peke mot en forelder; representanten er rota. To triks gjør operasjonene nesten konstante i amortisert tid:

• Union ved rang — heng det lavere treet under det høyere, så trærne holder seg grunne.
• Stikomprimering — pek hver besøkt node rett på rota under Find-Set.

Med begge er $m$ operasjoner $O(m\,\alpha(n))$, der $\alpha$ er den (nesten konstante) inverse Ackermann-funksjonen. For oss er poenget at union-find lar Kruskal raskt svare på «ligger disse to nodene allerede i samme komponent?».

Spenntre og MST

Et spenntre av en sammenhengende graf er et asyklisk delsett av kantene som kobler alle noder; det har alltid nøyaktig $|V| - 1$ kanter. Et minimalt spenntre er et spenntre med minst mulig sum av kantvekter. Det trenger ikke være entydig — med like vekter kan flere MST eksistere — men den minimale totalvekten er det.

Generic-MST og trygge kanter

Begge algoritmene vi skal se er instanser av ett grådig skjelett. Vi holder på en delmengde $A$ av kanter som er en del av et MST, og legger til én trygg kant av gangen til $A$ er et helt spenntre.

Hva gjør en kant trygg? Et snitt $(S, V \setminus S)$ deler nodene i to. En kant krysser snittet om endepunktene ligger på hver sin side. Et snitt respekterer $A$ om ingen kant i $A$ krysser det. Da gjelder:

Beviset er et klassisk utbyttingsargument: ta et MST $T$ som inneholder $A$. Inneholder $T$ allerede $(u,v)$, er vi ferdige. Ellers lager $(u,v)$ en sykel sammen med stien i $T$; den stien må krysse snittet via en annen kant $(x,y)$ med $w(x,y) \ge w(u,v)$. Bytt $(x,y)$ mot $(u,v)$: resultatet er fortsatt et spenntre, med vekt som ikke er større — altså også et MST som inneholder $A \cup \{(u,v)\}$. Dette er det sentrale beviset i hele kapittelet.

Kruskals algoritme

Kruskal er Generic-MST med ett bestemt valg av snitt: sorter alle kantene etter vekt, og legg til hver kant som forbinder to ulike komponenter. En kant som ville koblet to noder i samme komponent forkastes — den ville lagd en sykel. Union-find er nettopp det som svarer på komponent-spørsmålet raskt.

def kruskal(V, edges):
  parent = {v: v for v in V}
  def find(x):
      while parent[x] != x:
          x = parent[x]
      return x
  tree = []
  for u, v, w in sorted(edges, key=lambda e: e[2]):
      if find(u) != find(v):
          parent[find(u)] = find(v)
          tree.append((u, v, w))
  return tree

Kruskal bruker $O(E \lg V)$ tid: sorteringen dominerer, og union-find-arbeidet er nesten lineært. Den sorterte rekkefølgen gjør hvert grådige valg trygt — hver godtatt kant er den letteste som krysser snittet mellom dens to komponenter og resten.

Prims algoritme

Prim velger et annet snitt: la $A$ alltid være ett sammenhengende tre som vokser ut fra en startnode. I hvert steg legger vi til den letteste kanten som forlater treet. En min-prioritetskø (en haug) over nodene utenfor treet, nøklet på letteste kjente kant inn til treet, gir nettopp denne kanten i logaritmisk tid. Prioritetskøen er hele motoren: med binær haug blir Prim $O(E \lg V)$, og med Fibonacci-haug $O(E + V \lg V)$.

Sjekk deg selv