Minimal aufspannende Bäume

Minimal spannende Bäume (engl. Minimum Spanning Tree, MST) sind in der Graphentheorie von fundamentaler Bedeutung. Wenn man einen einfachen, zusammenhängenden Graph $G = (V,E)$ gegeben hat, der zudem eine Gewichtsfunktion $c : E \to \mathbb{R}^+$ besitzt, so lautet das Problem: Finde einen Baum $T = (V, E')$ derart, dass $E' \subseteq E$ und

\begin{gather*} \sum_{e' \in E'} c(e') \end{gather*}

minimal ist.

Der Algorithmus von Kruskal

Das Problem ist in $\mathcal{P}$ und daher "effizient" lösbar. Der berühmteste Algorithmus zur Lösung des Problems ist ohne Zweifel der Algorithmus von Kruskal. Er sortiert zunächst die Kanten bezüglich des Gewichts in nicht absteigender Reihenfolge. Nun werden sukzessive die Kanten betrachtet. Dabei wird geprüft ob die Kante einen Zyklus in dem Baum induziert. Ist das nicht der Fall, so wird die Kante zu $E'$ hinzugefügt, andernfalls wird sie übersprungen.

Es handelt sich bei diesem Algorithmus um einen Greedy Algorithmus, da er gierig vorgeht, und zunächst versucht so leichte Kanten wie möglich zu dem Baum hinzuzufügen. Dass der Algorithmus immer eine optimale Lösung liefert lässt sich dadurch beweisen, dass die Menge aller möglichen Wälder in einem Graph eine Matroidstruktur ist. Da ein Greedy Algorithmus auf einem Matroid immer optimale Resultate liefert, ist Kruskal ein optimaler Algorithmus zur Berechnung eines minimalen Spannbaumes.

Das Sortieren der Kanten ist auf triviale Weise mit einem beliebigem guten Sortierverfahren in $\mathcal{O}(n\log n)$ Zeit möglich. Das Überprüfen ob eine Kante einen Kreis induziert lässt sich sehr schön mit einer UNION FIND Datenstruktur lösen. Diese Mengenverwaltungsstruktur lässt sich sehr effizient implementieren. Dabei wird für jeden Knoten zunächst eine Menge erzeugt. Wird nun eine Kante betrachtet, so wird überprüft ob die inzidenten Knoten dieser Kante in verschiedenen Mengen liegen. Ist das der Fall, so erzeugt die Kante keinen Kreis, andernfalls würde sie es. Wurde die Kante in den Baum aufgenommen, so werden die Mengen der inzidenten Knoten mittels einer UNION Operation vereinigt.

Das Applet

Das folgende Applet ist eine Visualisierung des Algorithmus von Kruskal. Dabei operiert er auf einer UNION FIND Datenstruktur die Weighted Union und Find mit Pfadkompression unterstützt. Die Laufzeit des Algorithmus für einen Graph $G = (V,E)$ ist damit in $\mathcal{O}(|E| \cdot \alpha(|E|, |V|))$, wobei $\alpha(x,y)$ die inverse Ackermannfunktion ist.

Die blaue Kante visualisiert die aktuell vom Algorithmus betrachtete Kante. Eine grüne Kante wurde in den Baum eingefügt, während eine rote nicht eingefügt wurde. Der Button "Next" führt den nächsten Schritt im Algorithmus durch.

Hinweis: Damit das Applet funktioniert, muss JRE 1.5 oder höher installiert sein.

Dein Browser kann leider keine Applets darstellen

Quellcode

Für die Leute die es interessiert, ist hier der Quellcode für das komplette Applet:

Internetverweise

Website by: Thomas Pajor, Augartenstr. 56, 76137 Karlsruhe - www.darkviper.de - with help from: flowhase