6.3 Minimale spenntrær — Prim, Kruskal, Borůvka

Minimale spenntrær (MST) — Prim med prioritetskø, gjenkjenning av Kruskal/Borůvka, og hvorfor BFS/DFS *ikke* gir MST.

50 min

6 oppgaver

Minimale spenntrærPrimKruskalBorůvka

Din fremgang i kapitlet

0 / 6 oppgaver

Kapitlets plass i kurset

Bygger på

6.2Korteste vei — BFS, Dijkstra, DAG og reversert graf

Minimale spenntrær er med i 4 av 7 sett (57 %), og de kommer i to former:

- Sjanger F — matriseavkryssing, altså at du krysser av hvilke algoritmer som
faktisk finner et minimalt spenntre. Her er det ett fast svar som skiller:
BFS og DFS gjør det ikke. De finner et spenntre, ikke det minimale.
- Sjanger H — modellering i pseudokode, altså at du gjenkjenner problemet og
skriver algoritmen. Mønsteret er alltid: «koble alt sammen så billig som mulig».

Prioritet: kunne (nivå 2 av tre — «må sitte» er nivå 1, «kjenne til» er
nivå 3). Prim er den du skal kunne skrive; Kruskal og Borůvka skal du kunne
gjenkjenne og si hva de gjør.

Det er én oppfølgingsfelle du bør kjenne før du begynner, fordi den er dokumentert
i arkivet: når oppgaven først har bedt deg bygge det billigste nettet, spør den
gjerne videre om korteste vei mellom to punkter i det ferdige nettet. Der er
svaret ikke Dijkstra. Vi kommer tilbake til hvorfor i løkke 4.

Slik er kapitlet lagt opp (50 min): fire løkker med teori, gjennomkjørt
eksempel og oppgaver, og et pausepunkt etter løkke 3.

Forkunnskaper

- kap. 6.2 — prioritetskøen som verktøy, og
DecreaseKey. Prim er bygget nøyaktig som Dijkstra, men med én avgjørende
forskjell i hva som legges i køen.
- kap. 4.4 — min-heapen, som er prioritetskøen. RemoveMin
og DecreaseKey er $O(\log n)$ hver.
- kap. 5.2 — BFS og DFS. De brukes både som kontrast (de
finner ikke minimale spenntrær) og som verktøy i selve modelleringen.
- kap. 5.1 — grafnotasjonen og nabolistene.

Notasjons- og pseudokodeliste

Løkke 1 — å koble alt sammen så billig som mulig (ca. 12 min)

Sju gårder i en dal skal få fiber. Mellom noen av gårdene er det mulig å grave, og
hver mulig grøft har en pris i hundretusen kroner. Alle gårdene må ende opp
tilkoblet — men det er likegyldig hvordan de henger sammen, så lenge det går an
å komme fra hvilken som helst gård til hvilken som helst annen gjennom nettet.

Hva er den billigste måten?

To observasjoner løser halve problemet. For det første: løsningen kan aldri
inneholde en sykel. Har du en sykel, kan du fjerne den dyreste kanten i den, og
alt henger fortsatt sammen — bare billigere. For det andre: løsningen må ha
nøyaktig $|V| - 1$ kanter. Færre, og noe henger løst; flere, og du har en sykel.

En sammenhengende graf uten sykler er et tre. Vi leter altså etter et tre.

Spenntre

|V|

Minimalt spenntre (MST)

Det spenntreet som har lavest samlet kantvekt av alle spenntrær i grafen. Er alle kantvektene forskjellige, er det minimale spenntreet entydig — det finnes bare ett. Er noen vekter like, kan det finnes flere, men de har alle samme totalvekt. Merk hva som ikke er kravet: et minimalt spenntre gir ingen garanti om korteste vei mellom to bestemte noder. Det minimerer summen, ikke enkeltavstander.

📜Hvilke algoritmer finner et minimalt spenntre — og hvilke gjør det ikke

Dette er avkryssingen som går igjen, og den har ett fast mønster:

Algoritme	Finner MST?	Merknad
Prim	ja	vokser ett tre fra en startnode
Kruskal	ja	tar kanter i vektrekkefølge, hopper over dem som lager sykel
Borůvka	ja	hver komponent velger sin letteste utkant, i runder
BFS	nei	finner et spenntre, men ser ikke på vektene i det hele tatt
DFS	nei	samme sak — et spenntre, valgt vilkårlig
Dijkstra	nei	finner korteste veier fra én node, ikke billigste nett

De tre øverste er alle grådige: de tar den billigste lovlige kanten som er
tilgjengelig, og angrer aldri. At det faktisk gir et globalt minimum, er et
resultat du skal kjenne, ikke bevise.
De tre nederste er fellene. BFS og DFS produserer et spenntre som en
bieffekt av traverseringen — kantene de bruker, er de kantene de tilfeldigvis kom
til først. Dijkstra minimerer noe helt annet: avstanden fra én bestemt node til
alle andre. Et Dijkstra-tre og et minimalt spenntre er sjelden det samme treet.

📝Oppgave 1

(Innstegsoppgave, sjanger F — matriseavkryssing, altså at du kobler egenskap til
algoritme.) Sett kryss: finner algoritmen et minimalt spenntre?

a) Prim
b) Dybde-først-søk
c) Kruskal
d) Dijkstra
e) Borůvka

Løkke 2 — Prim: la treet vokse (ca. 14 min)

Prims algoritme er Dijkstra med én linje endret, og den linja er verdt å stoppe
opp ved.

I Dijkstra er nøkkelen til en node avstanden fra startnoden:
avstand[u] + vekt. I Prim er nøkkelen bare vekten på kanten inn til treet:
vekt. Prim bryr seg ikke om hvor langt det er tilbake til startnoden — den vil
bare koble den neste noden på billigst mulig vis.

Alt annet er likt: en prioritetskø over noder som ikke er i treet ennå, RemoveMin
for å velge den neste, og DecreaseKey når en billigere forbindelse dukker opp.

📜Pseudokode-kontrakt: `Prim`

Antagelser om representasjon.

G = (V, E)

er en urettet, vektet og
sammenhengende graf gitt som nabolister, der G.naboer(v) gir parene
(u, vekt). noekkel og fra er arrayer indeksert på node. Prioritetskøen PQ
er en binær min-heap ordnet på noekkel, med RemoveMin og DecreaseKey i

O(\log |V|)

Prebetingelse: grafen er sammenhengende (ellers finnes ikke noe spenntre —
da får du et minimalt spennskog per komponent).
Postbetingelse: kantene (fra[v], v) for alle v unntatt s utgjør et
minimalt spenntre.

Procedure Prim(G, s)
  Input:  urettet, sammenhengende, vektet graf G = (V, E) som nabolister;
          startnode s
  Output: for hver node v: kanten (fra[v], v) som knytter v til treet
  for hver v i V:
      noekkel[v] = uendelig
      fra[v] = ingen
  noekkel[s] = 0
  PQ = min-heap med alle noder i V, ordnet paa noekkel
  while PQ er ikke tom:
      u = PQ.RemoveMin()          // u tas inn i treet
      for hver (v, vekt) i G.naboer(u):
          if v er fortsatt i PQ and vekt < noekkel[v]:
              noekkel[v] = vekt
              fra[v] = u
              PQ.DecreaseKey(v, vekt)
  return fra

Grunnideen i én setning: den letteste kanten som går ut av treet, kan alltid
tas med — ethvert spenntre må krysse skillet mellom treet og resten et sted, og
det er billigst å gjøre det her.

Kjøretid: $O((|V| + |E|)\log |V|)$ . Tell operasjonene: $|V|$ kall på
RemoveMin à $O(\log |V|)$ , og til sammen $|E|$ gjennomganger av nabolister (hver
kant én gang fra hver ende i en urettet graf, altså $2|E|$ — samme orden) der hver
kan utløse en DecreaseKey à $O(\log |V|)$ .

På en komplett graf, der alle par er koblet, er
$|E| = |V|(|V|-1)/2$ , og kjøretiden blir $O(|V|^2 \log |V|)$ . Den formen skal du
kunne oppgi når oppgaven sier «alle punkter kan kobles til alle».

Den ene linja som skiller Prim fra Dijkstra er testen vekt < noekkel[v]. I
Dijkstra står det avstand[u] + vekt < avstand[v]. Bytter du dem om, løser du
feil problem — og det er ikke synlig i pseudokoden med mindre du ser etter.

✏️Eksempel 1: Prim på fibernettet

Gravekostnadene mellom de sju gårdene, i hundretusen kroner: $A$ – $B$ 4, $A$ – $C$ 8,
$B$ – $C$ 2, $B$ – $D$ 7, $C$ – $D$ 1, $C$ – $E$ 5, $D$ – $E$ 9, $D$ – $F$ 3, $E$ – $F$ 6,
$E$ – $G$ 11, $F$ – $G$ 10.

Finn det billigste nettet som kobler alle sju gårdene sammen, og oppgi
totalkostnaden. Start i $A$ .

Prioritetskøen inneholder alle noder som ennå ikke er i treet, med nøkkelen «vekten
på den letteste kjente kanten inn til treet». Kolonnen lengst til høyre viser køens
innhold som heap-array med indeks fra 0.

Steg	Node tatt inn i treet	Kant lagt til	Sum så langt	Oppdaterte nøkler (DecreaseKey)	Prioritetskø etter (heap-array)
1	A	— (startnode)	0	`B: ∞ -> 4` (via A), `C: ∞ -> 8` (via A)	`(4, B), (∞, G), (8, C), (∞, D), (∞, E), (∞, F)`
2	B	`A–B` (4)	4	`C: 8 -> 2` (via B), `D: ∞ -> 7` (via B)	`(2, C), (7, D), (∞, F), (∞, G), (∞, E)`
3	C	`B–C` (2)	6	`D: 7 -> 1` (via C), `E: ∞ -> 5` (via C)	`(1, D), (5, E), (∞, F), (∞, G)`
4	D	`C–D` (1)	7	`F: ∞ -> 3` (via D)	`(3, F), (∞, G), (5, E)`
5	F	`D–F` (3)	10	`G: ∞ -> 10` (via F)	`(5, E), (10, G)`
6	E	`C–E` (5)	15	ingen	`(10, G)`
7	G	`F–G` (10)	25	ingen	`tom`

Sluttilstand — dette er svaret du leverer:

Kanter i treet:  A-B (4), B-C (2), C-D (1), C-E (5), D-F (3), F-G (10)
Total kostnad:   25

Kontrollen: treet har 6 kanter, og

|V| - 1 = 7 - 1 = 6

. Stemmer.
Se på steg 2. Kanten

A

–

C

kostet 8, men i det

B

kom inn i treet, ble det
klart at

C

kunne nås for 2 via

B

. DecreaseKey senket nøkkelen fra 8 til 2, og
fra[C] ble

B

i stedet for

A

. Den dyre kanten

A

–

C

havnet aldri i treet.
Se på steg 5. Her tas

F

inn med kanten

D

–

F

(3), og først da blir

G

tilgjengelig i det hele tatt — for 10. Det er den nest dyreste kanten i hele

grafen, og den må likevel med: $G$ har bare to forbindelser, 10 og 11, og én av dem

må brukes for at $G$ skal henge sammen med resten.

Momentet: et minimalt spenntre er ikke et tre av billige kanter. Det er det

billigste treet — og noen ganger tvinger strukturen deg til å ta en dyr kant.
Fellenote. Fella her er å stoppe når «det ser sammenhengende ut». Tell
kantene: nøyaktig $|V| - 1$ , hverken flere eller færre.

📝Oppgave 2

Sjanger E

En urettet vektet graf har kantene $A$ – $B$ 1, $A$ – $C$ 4,
$B$ – $C$ 2, $B$ – $D$ 5, $C$ – $D$ 3, $C$ – $E$ 7, $D$ – $E$ 6.

a) Kjør Prim fra $A$ . Oppgi kantene i treet og totalvekten.
b) Hvor mange kanter skal treet ha, og stemmer det?
c) Hvilke to kanter ble aldri med, og hvorfor?

Løkke 3 — Kruskal: ta de billigste kantene først (ca. 12 min)

Kruskals algoritme angriper problemet fra motsatt kant. I stedet for å la ett tre
vokse, sorterer den alle kantene etter vekt og går gjennom dem fra billigst til
dyrest. Hver kant tas med, med mindre den ville laget en sykel.

Da trenger den ett hjelpemiddel: en måte å svare raskt på spørsmålet «henger disse
to nodene allerede sammen?». Det er union-find: hver node hører til en
komponent, Find(v) gir komponentens navn, og Union(u, v) slår to komponenter
sammen. Lager kanten en sykel? Nøyaktig når Find(u) og Find(v) gir samme svar.

Union-find

O(1)

📜Pseudokode-kontrakt: `Kruskal`

Antagelser om representasjon.

G = (V, E)

er en urettet, vektet graf, og
kantene kan listes som trippel (u, v, vekt). En union-find-struktur over

V

er
tilgjengelig med Find og Union.

Prebetingelse: ingen. Postbetingelse: T er et minimalt spenntre hvis
grafen er sammenhengende; ellers et minimalt spenntre per komponent.

Procedure Kruskal(G)
  Input:  urettet, vektet graf G = (V, E) som kantliste
  Output: kantmengden T i et minimalt spenntre
  sorter alle kanter i E stigende paa vekt
  lag en union-find-struktur der hver node er sin egen komponent
  T = tom mengde
  for hver kant (u, v, vekt) i sortert rekkefolge:
      if Find(u) er ulik Find(v):
          T.leggTil((u, v))
          Union(u, v)
          if |T| er lik |V| - 1:
              stopp
  return T

Grunnideen i én setning: den billigste kanten som forbinder to komponenter som
ennå ikke henger sammen, kan alltid tas med — det er samme grådighetsargument som
i Prim, bare anvendt på komponenter i stedet for på ett voksende tre.

Kjøretid: $O(|E| \log |E|)$ . Sorteringen av kantene dominerer:
$O(|E| \log |E|)$ . Løkka gjør $O(|E|)$ Find-par og høyst $|V| - 1$ Union-kall,
og de er så billige at de forsvinner i sammenligning. Siden
$|E| \le |V|^2$ , er $\log |E| \le 2\log |V|$ , så uttrykket kan også skrives
$O(|E| \log |V|)$ — begge former godtas.

Stopp-linja er verdt et delpoeng. Når $T$ har $|V| - 1$ kanter, er treet
ferdig, og resten av den sorterte lista kan hoppes over.

✏️Eksempel 2: Kruskal på det samme fibernettet

Kjør Kruskals algoritme på fibernettet fra eksempel 1, og sammenlign resultatet
med det Prim ga. Vis union-find-tilstanden underveis.

Kantene sorteres først etter vekt: $C$ – $D$ 1, $B$ – $C$ 2, $D$ – $F$ 3, $A$ – $B$ 4,
$C$ – $E$ 5, $E$ – $F$ 6, $B$ – $D$ 7, $A$ – $C$ 8, $D$ – $E$ 9, $F$ – $G$ 10, $E$ – $G$ 11.

Kolonnen «Komponenter etter» viser union-find-strukturen som en partisjon av
nodene. Find(u) og Find(v) gir navnet på komponenten hver node tilhører — her
representert ved den alfabetisk minste noden i komponenten.

Steg	Kant	Vekt	Find(u) / Find(v)	Beslutning	Komponenter etter	Sum
1	C–D	1	`C` / `D`	velg — ulike komponenter, slås sammen	`{A} {B} {C,D} {E} {F} {G}`	1
2	B–C	2	`B` / `C`	velg — ulike komponenter, slås sammen	`{A} {B,C,D} {E} {F} {G}`	3
3	D–F	3	`B` / `F`	velg — ulike komponenter, slås sammen	`{A} {B,C,D,F} {E} {G}`	6
4	A–B	4	`A` / `B`	velg — ulike komponenter, slås sammen	`{A,B,C,D,F} {E} {G}`	10
5	C–E	5	`A` / `E`	velg — ulike komponenter, slås sammen	`{A,B,C,D,E,F} {G}`	15
6	E–F	6	`A` / `A`	forkast — samme komponent, ville laget sykel	`{A,B,C,D,E,F} {G}`	15
7	B–D	7	`A` / `A`	forkast — samme komponent, ville laget sykel	`{A,B,C,D,E,F} {G}`	15
8	A–C	8	`A` / `A`	forkast — samme komponent, ville laget sykel	`{A,B,C,D,E,F} {G}`	15
9	D–E	9	`A` / `A`	forkast — samme komponent, ville laget sykel	`{A,B,C,D,E,F} {G}`	15
10	F–G	10	`A` / `G`	velg — ulike komponenter, slås sammen	`{A,B,C,D,E,F,G}`	25

Sluttilstand — dette er svaret du leverer:

Kanter i treet:  C-D (1), B-C (2), D-F (3), A-B (4), C-E (5), F-G (10)
Total kostnad:   25

Sammenlign med Prim. Prim ga kantene

A

–

B

B

–

C

C

–

D

C

–

E

D

–

F

F

–

G

. Det er nøyaktig de samme seks kantene, bare funnet i en annen
rekkefølge — og med samme totalkostnad 25.
Det er ingen tilfeldighet: alle kantvektene i denne grafen er forskjellige, og da
er det minimale spenntreet entydig. Enhver korrekt MST-algoritme må gi samme
svar.
Se på steg 6 til 9. Fire kanter på rad blir forkastet (

E

–

F

B

–

D

A

–

C

D

–

E

9). Alle fire har begge endepunktene i den samme komponenten
{A,B,C,D,E,F} — de ville laget en sykel. Det er nettopp den jobben Find gjør,

og den er hele grunnen til at Kruskal trenger union-find.

Se på steg 10. Kanten $F$ – $G$ (10) er dyr, men $G$ ligger fortsatt alene i sin

egen komponent, og kanten tas. Etterpå har $T$ seks kanter, altså $|V| - 1$ , og
algoritmen kan stoppe — den siste kanten $E$ – $G$ (11) trenger aldri å bli sett på.
Fellenote. Fella her er å ta med en kant uten å sjekke komponentene, typisk

den nest billigste kanten ut fra hver node. Da får du sykler, og treet blir
ugyldig. Kontrollen er alltid den samme: nøyaktig $|V| - 1$ kanter til slutt.

📝Oppgave 3

Sjanger E

Kjør Kruskals algoritme på grafen fra oppgave 2: $A$ – $B$ 1,
$A$ – $C$ 4, $B$ – $C$ 2, $B$ – $D$ 5, $C$ – $D$ 3, $C$ – $E$ 7, $D$ – $E$ 6.

a) Sett opp kantene i sortert rekkefølge.
b) Kjør algoritmen og vis hvilke kanter som velges og forkastes.
c) Sammenlign svaret med det Prim ga i oppgave 2. Hva forteller sammenligningen
deg?

— naturlig pausepunkt —

Du har nå begge algoritmene og forstår hvorfor de gir samme svar. Siste løkke
handler om det som faktisk står i eksamensoppgavene: å gjenkjenne at et problem
er et MST-problem, og å unngå den ene fellen som kommer rett etterpå.

Borůvkas algoritme

O(\log |V|)

Typiske feil

- Å tro at BFS eller DFS gir et minimalt spenntre. De gir et spenntre. De
leser ikke engang kantvektene. Dette er den faste avkryssingsfellen, og den er
verdt hele poenget på sjanger F.
- Å bruke Dijkstra i det ferdige spenntreet. Når oppgaven først har bedt deg
bygge det billigste nettet og deretter spør om korteste vei i det nettet, er
vektene byggekostnader, ikke avstander. Se løkke 4 — dette er dokumentert som en
feil som gir færre poeng.
- Å blande Prim og Dijkstra i pseudokoden. Nøkkelen i Prim er vekt; i
Dijkstra er den avstand[u] + vekt. Én linje, to helt forskjellige problemer.
- Å glemme sykelsjekken i Kruskal. Uten Find(u) er ulik Find(v) samler du
bare de billigste kantene, og resultatet har både sykler og løse noder.
- Å levere et tre med feil antall kanter. Et spenntre over $|V|$ noder har
nøyaktig $|V| - 1$ kanter. Denne kontrollen tar fem sekunder og fanger de fleste
håndkjøringsfeil.
- Å oppgi feil Prim-kjøretid for en komplett graf. Sier oppgaven at alle punkter
kan kobles til alle, er $|E| = |V|(|V|-1)/2$ , og kjøretiden blir
$O(|V|^2 \log |V|)$ — ikke $O((|V| + |E|)\log |V|)$ uten videre forklaring.

Og den gjennomgående: å ikke si hva størrelsene er. Skriv at $|V|$ er antall
gårder og $|E|$ antall mulige grøfter. Kjøretid uten definerte størrelser er felle
#10, og det trekkes eksplisitt for den.

Løkke 4 — modelleringen, og fellen som kommer rett etterpå (ca. 12 min)

På eksamen står det aldri «finn et minimalt spenntre». Det står noe slikt som
«kommunen skal legge fiber til alle gårdene så billig som mulig». Jobben din er å
kjenne igjen strukturen.

Mønsteret: når oppgaven ber deg koble alt sammen til lavest mulig samlet
kostnad, og det er likegyldig hvordan forbindelsene går, er svaret et minimalt
spenntre.

Og så kommer oppfølgingsspørsmålet, som er der halve poengsummen ligger: «etterpå
skal en tekniker kjøre fra gård $A$ til gård $G$ gjennom det nye nettet.
Hvilken vei?»

Her svarer mange Dijkstra, og det er feil av to grunner.

📜Korteste vei i et ferdig spenntre er BFS eller DFS — ikke Dijkstra

Når du først har bygget spenntreet, og skal finne veien mellom to noder i
treet, gjelder to ting:

1. Det finnes bare én vei. Et tre har ingen sykler, så mellom to noder finnes
nøyaktig én sti. Det er ingenting å minimere. En enkel traversering — BFS eller
DFS — finner den i $O(|V| + |E|)$ , og i et tre er $|E| = |V| - 1$ , så det er
$O(|V|)$ .

2. Vektene betyr noe annet nå. I det opprinnelige problemet var vekten
byggekostnad — hva det koster å grave grøfta. Å legge sammen byggekostnader
langs en rute gir ikke noe meningsfullt tall: teknikeren betaler ikke for grøfta på
nytt når han kjører gjennom den.

Å kjøre Dijkstra her er derfor ikke bare unødvendig dyrt
( $O((|V| + |E|)\log |V|)$ i stedet for $O(|V|)$ ) — det er å minimere en størrelse
som ikke gir mening i oppgaven. Sensorveiledningene omtaler dette som «ikke
veldefinert», og det gir færre poeng enn traverseringen.

Regelen å ta med seg: når du ser en vekt, spør alltid hva den måler. Er den
en kostnad ved å ha kanten, hører den hjemme i et MST. Er den en kostnad ved å
bruke kanten, hører den hjemme i et korteste-vei-problem.

✏️Eksempel 3: Eksamensnivå — bygg nettet, og finn veien i det

En kommune skal legge fiber mellom sju gårder. Alle mulige grøfter og prisene deres
er kjent (grafen fra eksempel 1).

a) Beskriv en algoritme som finner det billigste nettet som kobler alle gårdene
sammen. Oppgi kjøretid.

b) Etter at nettet er bygget, skal en tekniker kjøre fra gård $A$ til gård $G$
gjennom det nye nettet, og vil vite hvor mange strekk han må innom. Beskriv en
algoritme, og oppgi kjøretid.

a) Problemet navngitt. «Koble alt sammen til lavest samlet kostnad, uten krav
til hvordan» er definisjonen på et minimalt spenntre.

Antagelser om representasjon. Gårdene er nodene i en urettet, vektet,
sammenhengende graf $G = (V, E)$ gitt som nabolister; $|V| = 7$ gårder og $|E|$ er
antall mulige grøfter. Vekten på en kant er gravekostnaden.

Algoritmen: Prim med binær prioritetskø, som i pseudokode-kontrakten over.
Resultatet er de seks kantene $A$ – $B$ (4), $B$ – $C$ (2), $C$ – $D$ (1), $C$ – $E$ (5),
$D$ – $F$ (3) og $F$ – $G$ (10), med samlet kostnad 25.

Kjøretid: $O((|V| + |E|)\log |V|)$ , der $|V|$ er antall gårder og $|E|$ antall
mulige grøfter. Er alle par koblet — en komplett graf — er
$|E| = |V|(|V|-1)/2$ , og kjøretiden blir $O(|V|^2 \log |V|)$ .

Kruskal ( $O(|E| \log |E|)$ ) er like riktig og gir samme uttelling.

b) Problemet navngitt. Nå er grafen treet, ikke det opprinnelige nettet.
Mellom to noder i et tre finnes nøyaktig én sti, så det er ingenting å minimere —
det er en ren traverseringsoppgave.

Antagelser om representasjon. Spenntreet $T$ fra deloppgave a), lagret som
nabolister over de $|V| - 1$ kantene.

Algoritmen:

Procedure VeiITreet(T, a, b)
  Input:  spenntreet T som nabolister, to noder a og b
  Output: antall strekk paa veien fra a til b, og selve veien
  gjor en bredde-forst-traversering fra a i T,
      og noter forgjenger[v] for hver node som oppdages
  les veien baklengs fra b via forgjenger til du naar a
  return lengden paa veien, og veien selv

Kjøring på tallene. Bredde-først fra $A$ i spenntreet:

Steg	Tatt ut av køen	Nye noder oppdaget	Kø etter	avstand-tabell etter
1	A (avst. 0)	`B = 1`	`B`	`A=0, B=1, C=∞, D=∞, E=∞, F=∞, G=∞`
2	B (avst. 1)	`C = 2`	`C`	`A=0, B=1, C=2, D=∞, E=∞, F=∞, G=∞`
3	C (avst. 2)	`D = 3`, `E = 3`	`D, E`	`A=0, B=1, C=2, D=3, E=3, F=∞, G=∞`
4	D (avst. 3)	`F = 4`	`E, F`	`A=0, B=1, C=2, D=3, E=3, F=4, G=∞`
5	E (avst. 3)	ingen	`F`	`A=0, B=1, C=2, D=3, E=3, F=4, G=∞`
6	F (avst. 4)	`G = 5`	`G`	`A=0, B=1, C=2, D=3, E=3, F=4, G=5`
7	G (avst. 5)	ingen	`tom`	`A=0, B=1, C=2, D=3, E=3, F=4, G=5`

Antall strekk fra

A

til

G

er 5, og veien er
A - B - C - D - F - G.
Kjøretid:

O(|V| + |E_T|)

der

|E_T| = |V| - 1

, altså

O(|V|)

— lineært i
antall gårder.
Hvorfor ikke Dijkstra. To grunner, og begge er verdt å skrive:
1. Det finnes bare én vei mellom to noder i et tre. Det er ingenting å
minimere, så en traversering holder — og den er

O(|V|)

mot Dijkstras

O((|V| + |E|)\log |V|)

2. Vektene måler noe annet. De er gravekostnader, ikke reiseavstander. Å
summere dem langs teknikerens rute gir ikke et meningsfullt tall.

Poengtrapp-notat. Deloppgave a) gir uttelling for å navngi MST og velge en
korrekt algoritme med riktig kjøretid — det er hovedmomentet, og det gir mest.

Deloppgave b) skiller: BFS eller DFS i treet er toppsvaret; Dijkstra i treet er

korrekt i den forstand at det finner en vei, men både tregere og basert på en
størrelse oppgaven ikke ba om, og det gir mindre.

📝Oppgave 4

Sjanger H

Et vannverk skal legge rør mellom tolv
tanker. Hver mulig rørstrekning har en anleggskostnad. Alle tankene må henge
sammen.

a) Hvilket problem er dette, og hvilken algoritme velger du?
b) Hvor mange rørstrekninger vil løsningen inneholde?
c) En kollega foreslår å kjøre Dijkstra fra tank 1 og bruke kantene i
resultatet. Hva blir galt?

📝Oppgave 5

Sjanger C

Marker sant eller usant, og begrunn hvert svar med én setning.

a) Et minimalt spenntre inneholder alltid den letteste kanten i grafen.
b) Et minimalt spenntre inneholder aldri den tyngste kanten i grafen.
c) Hvis alle kantvekter er forskjellige, er det minimale spenntreet entydig.
d) Kruskals kjøretid domineres av sorteringen av kantene.
e) Prim og Kruskal kan gi trær med ulik totalvekt på samme graf.

📝Oppgave 6

Sjanger H, krevende

Et selskap har allerede lagt kabel mellom noen av $n$
lokasjoner. Nå skal de koble sammen resten, så billig som mulig. De eksisterende
kablene er gratis å bruke; de nye har en kjent gravekostnad hver.

a) Hvordan modellerer du de eksisterende kablene?
b) Skriv algoritmen, og oppgi kjøretiden.
c) Hva blir svaret hvis de eksisterende kablene allerede kobler alle
lokasjonene sammen?

Begrepsbank

Begrepsbanken er flashcard-/repetisjonsstoff — den gjentar det du nettopp har
lest. Hopp trygt over ved førstegangslesing; tidsanslaget for kapitlet gjelder
kjernestoffet.

Prim

O((|V| + |E|)\log |V|)

Kruskal

O(|E| \log |E|)

BFS og DFS gir IKKE minimalt spenntre

Begge produserer et spenntre som en bieffekt av traverseringen, men de leser ikke kantvektene i det hele tatt. Dette er den faste avkryssingsfellen på sjanger F. Kontrollen er enkel: en algoritme som aldri ser på vektene, kan umulig minimere noe som avhenger av dem.

Antall kanter i et spenntre

|T| = |V| - 1

Prim mot Dijkstra — den ene linja

Prim: if vekt < noekkel[v] — nøkkelen er vekten på kanten inn til treet. Dijkstra: if avstand[u] + vekt < avstand[v] — nøkkelen er avstanden fra startnoden. Alt annet i de to algoritmene er likt. Bytter du om testen, løser du feil problem, og det er ikke synlig i pseudokoden med mindre du ser etter.

Korteste vei i et ferdig spenntre

O(|V|)

Entydig minimalt spenntre

Er alle kantvektene forskjellige, finnes det bare ett minimalt spenntre, og alle korrekte algoritmer gir samme svar. Er noen vekter like, kan det finnes flere minimale spenntrær — men de har alle nøyaktig samme totalvekt, så svaret på «hva koster det» er uansett entydig.

Grådig algoritme

En algoritme som tar det beste lokale valget i hvert steg og aldri angrer. Prim, Kruskal, Borůvka og Huffman er alle grådige. For MST er grådighet beviselig optimalt — den letteste kanten ut av en delvis bygget struktur kan alltid tas med. At det holder, er et resultat du skal kjenne, ikke bevise.

Prims kjøretid på en komplett graf

|E| = |V|(|V|-1)/2

Kanter med vekt 0

Modelleringsknepet for «denne forbindelsen finnes allerede og er gratis»: gi kanten vekt 0. Enhver MST-algoritme tar da kanten med hvis den kan, siden ingen kant er lettere. Etterpå leser du av hvilke kanter i treet som har positiv vekt — det er dem som faktisk må bygges.

Mønstergjenkjenning: når er svaret MST?

A

Hva vekten måler

Spørsmålet som avgjør hvilket problem du står overfor: er vekten en kostnad ved å ha kanten, eller ved å bruke den? Byggekostnad og anleggspris hører hjemme i et minimalt spenntre. Reisetid og avstand hører hjemme i et korteste-vei-problem. Å summere byggekostnader langs en rute er den dokumenterte fellen i oppfølgingsspørsmålet.

Repetisjon — kapitlet på ett kort

Dette kapitlet er skrevet av Anthropics toppmodeller (Claude Opus og Claude Fable) og er foreløpig ikke manuelt gjennomgått — kvalitetskontrollen gjøres av uavhengige KI-agenter, og innmeldte feil rettes fortløpende. Funnet en feil? Meld fra, så retter vi den. Les mer om hvordan innholdet lages.

Skolesaga er en uavhengig læringsressurs og er ikke tilknyttet eller godkjent av Universitetet i Oslo. Dette er ikke offisielt studiemateriell. Les mer.