Minimale spenntrær

Det billigste nettet som henger sammen

Tenk deg at du skal legge fiber mellom seks hus i en grend. Du kjenner gravekostnaden for hver mulig kabelstrekning mellom to hus, og du vil at alle skal få nett, men du vil grave så få meter som mulig. Du trenger ikke en kabel mellom hvert par hus — du trenger bare at det finnes en vei fra hvert hus til hvert annet. Det er nettopp et minimalt spenntre (mst) vi er ute etter: et utvalg kanter som kobler sammen alle nodene i en vektet, sammenhengende graf, med minst mulig samlet vekt.

For å snakke presist om dette trenger vi spenntre-begrepet. Et spenntre er et utvalg kanter som binder sammen alle nodene uten å lage en eneste sykel. Hvorfor uten sykler? Fordi en sykel betyr at det finnes to veier mellom to hus, og da kan vi alltid fjerne den dyreste kanten i sykelen uten å miste sammenhengen — og spare penger. Et tre er nettopp en sammenhengende graf uten sykler, og over $V$ noder har et slikt tre alltid nøyaktig $V-1$ kanter. ƒet spenntre har v-1 kanter

I figuren over er den vektede grafen tegnet med alle mulige kanter, og de fem grønne kantene utgjør et minimalt spenntre med samlet vekt 15. Legg merke til at MST-et har akkurat $6-1=5$ kanter, og at de dyreste kantene (B-D med vekt 7, D-E med vekt 8) ikke er med.

Trygge kanter og snitt

Begge algoritmene vi skal se på bygger MST-et bit for bit. De starter med en tom mengde kanter $A$, og legger til én kant av gangen. Spørsmålet er hele tiden det samme: hvilken kant kan jeg trygt legge til nå, uten å male meg inn i et hjørne der det ikke lenger finnes noe minimalt spenntre som inneholder alle kantene mine?

En kant kalles trygg kant for $A$ hvis vi kan legge den til $A$ og fortsatt utvide til et MST. Det vakre er at det finnes en enkel oppskrift på å finne en trygg kant, og den hviler på begrepet snitt. Et snitt deler nodene i to grupper. En kant krysser snittet hvis de to endene ligger i hver sin gruppe. Vi sier at snittet respekterer $A$ hvis ingen kant i $A$ krysser det.

Snitt-egenskapen sier: hvis et snitt respekterer $A$, så er den letteste kanten som krysser snittet en trygg kant for $A$. ƒtrygg kant (snitt-egenskapen) Intuisjonen er en byttegang. Anta at det finnes et MST som ikke bruker den letteste kryssende kanten $e$. Det MST-et må likevel krysse snittet et sted, med en annen kant $e^{\prime }$ som er minst like tung. Bytt ut $e^{\prime }$ med $e$: du får fremdeles et spenntre, og det er ikke dyrere. Altså finnes det et MST som bruker $e$, og $e$ var trygg.

Denne ene egenskapen er motoren under alt som følger. Både Kruskal og Prim er bare to forskjellige måter å velge snitt på, slik at den letteste kryssende kanten er lett å finne.

Generic-MST: skjelettet

Før vi spesialiserer, er det nyttig å se det felles skjelettet. Vi holder en mengde kanter $A$ som hele tiden er en del av et eller annet MST, og gjentar: finn en trygg kant og legg den til, helt til $A$ har $V-1$ kanter.

GENERIC-MST(G):
  A = {}                       # tom kantmengde
  mens |A| < |V| - 1:
      finn en kant (u, v) som er trygg for A
      A = A + {(u, v)}
  returner A

Hele forskjellen mellom de konkrete algoritmene ligger i hvordan vi billig finner en trygg kant i løkka. Kruskal og Prim svarer ulikt.

Kruskal: sorter kantene, hopp over sykler

kruskal tar den enkleste tenkelige strategien: behandle kantene i økende vekt. For hver kant, legg den til hvis den kobler sammen to deler som ennå ikke henger sammen; hopp over den hvis begge endene allerede er i samme del, for da ville den laget en sykel.

KRUSKAL(G):
  A = {}
  for hver node v: MAKE-SET(v)
  sorter kantene etter vekt, lettest først
  for hver kant (u, v) i sortert rekkefølge:
      hvis FIND(u) != FIND(v):       # ulike komponenter?
          A = A + {(u, v)}
          UNION(u, v)
  returner A

Her gjemmer snittet seg i komponentstrukturen. Når vi vurderer den letteste gjenværende kanten $(u,v)$ og $u$ og $v$ ligger i hver sin komponent, kan vi tenke oss et snitt som skiller $u$-komponenten fra resten. Ingen lettere kant krysser det snittet, for vi har allerede sett alle lettere kanter. Altså er $(u,v)$ trygg.

På eksempelgrafen tar Kruskal kantene i denne rekkefølgen: E-F (1), A-D (2), B-E (3), A-B (4), C-F (5). Den hopper over B-C (6) fordi B og C nå allerede henger sammen, og den stopper når fem kanter er valgt. Resultatet er nøyaktig MST-et i figuren.

For at sykelsjekken FIND(u) != FIND(v) skal være rask, trenger vi en god datastruktur for «hvilke noder henger sammen». Det er en disjunkt-mengde-struktur (union-find).

Disjunkte mengder: skogen som holder rede på komponentene

En disjunkt-mengde-struktur (union-find) forvalter en samling disjunkte mengder. Den støtter tre operasjoner: MAKE-SET(v) lager en ny mengde med bare $v$, FIND(v) returnerer en representant for mengden $v$ ligger i, og UNION(u, v) slår sammen de to mengdene. To noder er i samme komponent nettopp når FIND gir samme representant.

Naivt implementert kan dette bli tregt, men to triks gjør det nesten gratis. Det første er rang-union: når to trær slås sammen, henges det lave under det høye, slik at trærne holder seg flate. Det andre er stikomprimering: under et FIND peker vi hver node vi passerer rett til rota, slik at neste oppslag går direkte. Med begge triks blir den amortiserte kostnaden per operasjon nesten konstant. ƒdisjunkte mengder (union-find)

Kruskals kjøretid domineres derfor av sorteringen, ikke av union-find-arbeidet. ƒkruskal Sorteringen av $E$ kanter koster $O(E\lg E)$, og siden $E<V^2$ er $\lg E=O(\lg V)$, så det skrives ofte som $O(E\lg V)$.

Prim: dyrk ett tre fra en startnode

prim velger snitt på en helt annen måte. I stedet for å la mange små trær flyte rundt, holder den ett sammenhengende tre som vokser. Snittet er alltid mellom nodene i treet og nodene utenfor. Den letteste kanten som krysser dette snittet — altså den letteste kanten med én ende i treet og én utenfor — er trygg, og blir neste kant vi legger til.

Figuren fanger Prim midt i arbeidet. Treet inneholder $\{A,B,D,E\}$ (de fylte nodene), og de stiplede kantene er frontkantene som krysser snittet ut mot C og F. Den letteste av dem er E-F med vekt 1, så den blir valgt neste. Hadde vi startet i A, ville Prim valgt kantene i rekkefølgen A-D (2), A-B (4), B-E (3), E-F (1), F-C (5) — samme MST, men funnet i en annen orden enn Kruskal.

For å finne den letteste frontkanten raskt, holder Prim en prioritetskø over nodene utenfor treet. Hver utenfor-node husker den letteste kanten som nettopp nå binder den til treet. Når en node tas inn, relakseres naboene: hvis en kant inn til en nabo er lettere enn det naboen husker fra før, oppdateres køens nøkkel.

PRIM(G, start):
  for hver node v: nøkkel[v] = uendelig, forelder[v] = ingen
  nøkkel[start] = 0
  Q = alle noder i en prioritetskø på nøkkel
  mens Q ikke er tom:
      u = EXTRACT-MIN(Q)
      for hver nabo v av u som fortsatt er i Q:
          hvis vekt(u, v) < nøkkel[v]:
              forelder[v] = u
              nøkkel[v] = vekt(u, v)     # DECREASE-KEY

Med en binærhaug koster hver av de $V$ uttrekkene $O(\lg V)$, og hver av de $E$ nøkkel-senkningene $O(\lg V)$. ƒprim med binærhaug Til sammen $O(E\lg V)$ — samme størrelsesorden som Kruskal.

Kruskal eller Prim?

Begge gir et korrekt MST, og begge lander på $O(E\lg V)$ med standard datastrukturer. Valget styres av grafen og hva du har for hånden. Kruskal er nesten triviell hvis kantene allerede er sortert, eller hvis grafen er tynn og du uansett vil ha en union-find. Prim skinner på tette grafer, særlig hvis prioritetskøen er en Fibonacci-haug, som presser nøkkel-senkningene ned og gir $O(E+V\lg V)$. Det viktigste er at de hviler på samme idé: en trygg kant er den letteste kanten over et snitt som respekterer det du har bygget så langt.