mst-kruskal.md

MST-Kruskal

Kruskals algoritme legger til alle kanter i en graf i en sortert liste basert på kantvekt. Deretter legger den til kantene i lista til en MST så lenge de ikke skaper sykler.

Den formelle definisjonen av det generelle problemet

Tilleggskrav for korrekthet

Trinn for trinn

1. Legg til alle kanter i en liste basert på kantvekt
2. Start med invarianten, $T$ er et tomt MST
3. Legg til den billigste kanten i treet til $T$, som opprettholder invarianten (ikke skaper sykler)
4. Gjenta 3 til alle noder er dekket

Korrekthetsbevis

Styrker og svakheter sammenlignet med andre

Kjøretid og utregning

Kjøretiden til Kruskal er avhengig av hvilken underliggende datastruktur vi velger. Pensum bruker disjoint-set skog da den er asymptotisk den raskeste kjent.

Utdypende kjøretidsanalyse er ganske omfattende og finnes på s. 633 i boka.

Datastruktur	Tidskompleksitet
Disjoint-set skog	$O(E\lg V)$

Python kodeeksempel