Kruskals Algorithmus

algorithm Kruskal (G,w):=
$\ulcorner$ 
		 sortiere die Kanten nach aufsteigendem Gewicht in   eine Liste L;
		 initialisiere $F=\{T_i, i=1,\ldots, n\}$ Wald (n=|V|) mit $T_i=\{v_i\};$ 
		 		 co G=(V,E), $V=\{v_1, \ldots, v_n\}$ oc
		 co implementiere Ti's als in-Trees mit den  jeweiligen Wurzeln als
		 		 Repräsentanten; allgemein: Unio-Find-Problem oc
		 MSB:=$\emptyset$;		 for i:=1 to length(L) do
		 		 $\{v,w\}:=L_i$;		 		 x:= Baum $\in F$, der v enthält; co  x:=   Find(v) oc
		 		 y:= Baum $\in F$, der w enthält; co  y:=   Find(w) oc
		 		 if $x \neq y$ then
		 		 co v und w in verschiedenen Bäumen oc
		 		 		 MSB:=MSB $\cup\ \{\{v,w\}\}$;		 		 		 if $\vert x\vert \leq \vert y\vert$ then   
		 		 		 		 co Baum x enthält $\leq$ Knoten als Baum y oc
		 		 		 		 co y:=   Union(x,y) oc
		 		 		 else
		 		 		 		 vereinige x und y, mit y neues Kind der Wurzel von x;
		 		 		 fi
		 		 fi
		 od
$\llcorner$

Korrektheit: Falls die Gewichte eindeutig sind (w() injektiv), folgt die Korrektheit direkt aus der ``blauen`` und ``roten`` Regel. Ansonsten Induktion über die Anzahl der Knoten (|V|):

Ind. Anfang: |V| klein:$\surd$

Sei $r\in \mathbbm{R}$, $E_r:=\{e\in E; w(e)<r\}$.
Es genügt zu zeigen:
Sei $r\in \mathbbm{R}$, sei $T_1,\cdots, T_k$ ein minimaler Spannwald (d.h. Spannwald minimalen Gewichtes) für $G_r:=\{V,E_r\}$ (d.h.betrachte nur Kanten mit Gewicht >r). Sei T ein MSB von G, dann:

Hilfsbehauptung: Die Knotenmenge eines jeden T_i im T induziert einen zusammenhängenden Teilbaum.

Beweis der Hilfsbehauptung: Sei T_i=:(V_i,E_i) und sei $e\in V_i \times V_i$. Falls $e\in T_i$, dann ist nichts zu zeigen. Für den Fall $e\not\in T_i$ betrachte den Fundamentalkreis C, den e in T_i erzeugt. Gewicht aller Kanten auf $C-\{e\} <r$ . Falls die beiden Endpunkte von e in T durch einen Pfad verbunden sind, der eine Kante $e'\in E-E_r$ enthält, dann liefert die ``rote`` Regel, daß T nicht minimal ist.
$\Rightarrow$ Die beiden Endpunkte und e sind in T durch einem Pfad aus lauter Kanten mit Gewicht <r verbunden. $\Diamond$



Zeitkomplexität: (mit n=|V|, m=|E|)

$$m\log{m}=\mathcal{O}(m\log{n})$$ Sortieren

$$\mathcal{O}(m) \mathcal{O}(m\log n)$$

$$\mathcal{O}(n)$$

Beweis: s.o. $\Diamond$



Beispiel für Kruskals Algorithmus: