Wichtiger Hinweis zum Inhalt des Online-LexikonsBei den auf dieser Seite aufgeführten Texten/Artikeln/Inhalten handelt es sich ausschließlich um fremde Inhalte, die sich die Aschendorff Verlag GmbH & Co. KG ausdrücklich nicht zu Eigen macht. Diese fremden Inhalte, die keiner regelmäßigen Überprüfung unterliegen, sind ausnahmslos solche der freien Enzyklopädie Wikipedia, für die keinerlei Verantwortung übernommen wird.

---

Lizenzbestimmungen Der Text/Artikel/Inhalt auf dieser Seite innerhalb der Rubrik "Online Lexikon" basiert, soweit nicht anders angegeben, auf dem Artikel Algorithmus von Kruskal aus der freien Enzyklopädie Wikipedia. Die Inhalte stehen unter der GNU Lizenz für freie Dokumentation. Eine Liste der Autoren ist dort abrufbar.

Algorithmus von Kruskal

Der Algorithmus von Kruskal ist ein Algorithmus der Graphentheorie zur Berechnung minimaler_Spannbäume von ungerichteten_Graphen. Der Graph muss dazu zusätzlich zusammenhängend, kantengewichtet und endlich sein.

Der Algorithmus stammt von Joseph Kruskal, der ihn 1956 in der Zeitschrift ?Proceedings of the American Mathematical Society? veröffentlichte. Er beschrieb ihn dort wie folgt:
:Führe den folgenden Schritt so oft wie möglich aus: Wähle unter den noch nicht ausgewählten Kanten von $G$ (dem Graphen) die kürzeste Kante, die mit den schon gewählten Kanten keinen Kreis bildet.Joseph Kruskal: On the shortest spanning subtree and the traveling salesman problem. In: Proceedings of the American Mathematical Society. 7 (1956), S. 48?50

Die kürzeste Kante bezeichnet dabei jeweils die Kante mit dem kleinsten Kantengewicht. Nach Abschluss des Algorithmus bilden die ausgewählten Kanten einen minimalen Spannbaum des Graphen.

Wendet man den Algorithmus auf unzusammenhängende Graphen an, so berechnet er einen minimalen Wald, also minimal spannende Bäume für jede Zusammenhangskomponente des Graphen.

Beispiel

Formalisierter Algorithmus

Die Grundidee ist, die Kanten in Reihenfolge aufsteigender Kantengewichte zu durchlaufen und jede Kante zur Lösung hinzuzufügen, die mit allen zuvor gewählten Kanten keinen Kreis bildet. Es werden somit sukzessiv sogenannte Komponenten zum minimalen_Spannbaum verbunden.

Input

Als Eingabe dient ein zusammenhängender kantenbewerteter Graph $G\; =\; (V,\backslash ,E,\backslash ,w)$. $V$ bezeichnet die Menge der Ecken (vertices), $E$ die Menge der Kanten (edges). Die Gewichtsfunktion $w:\; E\; \backslash rightarrow\; \backslash mathbb\{N\}$ordnet jeder Kante ein Kantengewicht zu.

Output

Der Algorithmus liefert einen minimalen Spannbaum $M\; =\; (V,\backslash ,E\text{'})$ mit $E\text{'}\; \backslash subseteq\; E$.

Algorithmus

Der Algorithmus von Kruskal arbeitet nicht deterministisch, d.h. er liefert unter Umständen beim wiederholten Ausführen unterschiedliche Ergebnisse. Alle diese Ergebnisse sind minimale Spannbäume von $G$.


$G\; =\; (V,E,w)$: ein zusammenhängender, ungerichteter, kantengewichteter Graph

kruskal(G)
1 Sortiere die Kanten von $G$ aufsteigend nach ihrem Kantengewicht.
2 $E\text{'}\; \backslash leftarrow\; \backslash emptyset$
3 $L\; \backslash leftarrow\; E$
4 solange $L\; \backslash neq\; \backslash emptyset$
5 wähle eine Kante $e\; \backslash in\; L$ mit kleinstem Kantengewicht
6 entferne die Kante $e$ aus $L$
7 wenn der Graph $(V,E\text{'}\; \backslash cup\; \backslash lbrace\; e\; \backslash rbrace)$ keinen Kreis enthält
8 dann $E\text{'}\; \backslash leftarrow\; E\text{'}\; \backslash cup\; \backslash lbrace\; e\; \backslash rbrace$
9 $M=(V,E\text{'})$ ist ein minimaler Spannbaum von $G$.


Derselbe Algorithmus lässt sich analog für einen maximalen Spannbaum anwenden. Sei $G=(V,E,w)$ etwa ein zusammenhängender kantengewichteter Graph. Dann geben wir $G\text{'}=(V,E,w\text{'})$ mit $w\text{'}(e)\; =\; s\; -\; w(e)$, $s\; \backslash in\; \backslash mathbb\{N\}$ und $\backslash forall\; e\; \backslash in\; E\; \backslash ,\; :\; s\; >\; w(e)$ im Algorithmus von Kruskal ein. Als Ausgabe erhalten wir schließlich einen minimalen Spannbaum von $G\text{'}$ und somit einen maximalen von $G$.

Korrektheitsbeweis

Sei $G\; =\; (V,E,w)$ ein zusammenhängender kantengewichteter Graph und $M\; =\; (V,E\text{'})$ die Ausgabe des Algorithmus von Kruskal. Um nun die Korrektheit des Algorithmus zu beweisen, müssen wir folgendes zeigen:
# der Algorithmus terminiert (er enthält keine Endlosschleife).
# $M$ ist ein minimaler Spannbaum von $G$, also:
## $M$ ist spannender Untergraph von $G$.
## $M$ enthält keinen Kreis.
## $M$ ist zusammenhängend.
## $M$ ist bezüglich $G$ minimal.

Im Nachstehenden geben wir nun Beweisideen, die die Gültigkeit der einzelnen Aussagen darlegen:
;Terminierung : Durch Zeile 6 entfernen wir in jedem Schleifendurchlauf genau ein Element aus $L$. Außerdem wird $L$ durch keine weitere Operation verändert. Aus $L$ werden wegen Zeile 4 nur solange Elemente entfernt, bis $L\; =\; \backslash emptyset$. Da zu Beginn im Algorithmus $L\; =\; E$ gesetzt wurde und $E$ nach Definition nur endlich ist, wird auch die Schleife nur endlich oft durchlaufen. Wir folgern daraus, dass Kruskals Algorithmus terminiert.
;M ist spannender Untergraph von G : Da die Menge der Knoten nach Definition des Algorithmus bei $M$ und $G$ gleich ist und wegen Zeile 8 offensichtlich $E\text{'}\; \backslash subseteq\; E$ gilt, ist $M$ spannender Untergraph von $G$.
;M enthält keinen Kreis : Dass $M$ keinen Kreis beinhalten kann, ist durch Zeile 7 trivial.
;M ist zusammenhängend : Wir zeigen nun indirekt, dass $M$ zusammenhängend ist. Sei $M$ also nicht zusammenhängend. Dann gibt es in $M$ zwei Knoten $x$ und $y$, die nicht durch einen Weg verbunden sind. Da aber $x$ und $y$ in $G$ durch einen Weg verbunden sind, existiert eine Kante $k$ in $G$, welche nicht in $M$ vorhanden ist. Der Algorithmus betrachtet in Zeile 7 garantiert jede Kante aus $G$ und damit auch $k$. Der Graph $(V,E\text{'}\; \backslash cup\; \backslash lbrace\; k\; \backslash rbrace)$ in Zeile 7 muss kreisfrei sein, da es zwischen $x$ und $y$ in $M=(V,E\text{'})$ keinen Weg gibt. Mit Zeile 8 wird $k$ dann in $M$ eingefügt. Dies widerspricht allerdings der Tatsache, dass $k$ nicht in $M$ enthalten ist. Somit ist unsere Annahme hinfällig und $M$ doch zusammmenhängend.
;M ist bezüglich G minimal : Dies ergibt sich aus dem allgemeineren Satz, dass jeder Greedy-Algorithmus (wie der Kruskal-Algorithmus einer ist) auf einem Matroid (wie das System der Bäume in einem zusammenhängenden Graph eines ist) eine Lösung minimalen Gewichts findet. In diesem Spezialfall lautet der BeweisHubertus Th. Jongen: Optimierung B. Skript zur Vorlesung, Aachen: Verlag der Augustinus-Buchhandlung, ISBN 3-925038-19-1:
: Bei nur einer Kante kann nichts schiefgehen, die kleinste Kantenzahl, bei der der Algorithmus scheitern kann, muss also größer als 1 sein. Angenommen, bei dieser kleinsten Kantenzahl erzeuge der Algorithmus den Baum $M$, aber $M\text{'}$ sei ein Spannbaum geringeren Gewichts als $M$. Beide Spannbäume enthalten gleich viele Kanten. Sortiert man alle Kanten so, dass leichtere vor schwereren liegen, dann gibt es einen minimalen Index $i$, für den die $i$-te Kante aus $M$ schwerer ist als die $i$-te Kante aus $M\text{'}$. Wir betrachten den Teilbaum $M\_0=\backslash \{e\_1,\backslash ldots,e\_i\backslash \}$, den der Algorithmus nach Hinzunahme der ersten $i$ Kanten erzeugt hat. Dann gibt es unter den ersten $i$ Kanten aus $M\text{'}$ eine, gegen die $e\_i$ ausgetauscht werden kann, so dass sich ein neuer Baum $M\_1=\backslash \{e\_1,\backslash ldots,e\_\{i-1\},f\backslash \}$ ergibt. $f$ ist entweder die $i$-te Kante aus $M\text{'}$ und damit leichter als $e\_i$, oder $f$ ist die $j$-te Kante aus $M\text{'}$ (mit

Zeitkomplexität

Im folgenden sei $m$ die Anzahl der Kanten und $n$ die Anzahl der Knoten. Die Sortieren der Kanten nach ihrem Gewicht und beträgt daher $O(m\; \backslash log(m))$, was der Größenordnung $O(m\; \backslash log(n))$ entspricht, da der Graph zusammenhängend ist und somit $n-1\; \backslash leq\; m\; \backslash leq\; \backslash frac\{n(n-1)\}\{2\}$ gilt. Insbesondere bei Graphen mit vielen Kanten ist insofern der Algorithmus von Prim effizienter.

Der Algorithmus von Kruskal arbeitet schneller, wenn die Kanten bereits vorsortiert sind. Um dann in konstanter Zeit zu ermitteln, ob eine Kante zwei Komponenten verbindet, wird zu jedem Knoten ein Verweis auf seine Komponente gespeichert. Die Vereinigung von Komponenten ist amortisiert in $O(log(n))$ möglich. Dazu wird zu jeder Komponente ihre Größe gespeichert, so dass bei einer Vereinigung immer die kleinere Komponente der größeren hinzugefügt werden kann. Insgesamt kann somit jeder Knoten höchstens $log(n)$-mal in eine andere Komponente verschoben werden.

Sonstiges

Der Algorithmus diente Kruskal ursprünglich als Hilfsmittel für einen vereinfachten Beweis, dass ein Graph mit paarweise verschiedenen Kantengewichten einen eindeutigen minimalen Spannbaum besitzt.

Weblinks

• Vollständiger Beweis zur Korrektheit des Algorithmus von Kruskal, Ronny Harbich, 2006
• Interaktives Java-Applet zur Demonstration
• Weiteres Java-Applet

Quellen und Bemerkungen

       VIDEO-NEWS UND ANGEBOTE