Der Algorithmus von Kruskal ist ein Greedy-Algorithmus der Graphentheorie zur Berechnung minimaler Spannbäume von ungerichteten Graphen. Der Graph muss dazu 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 (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 (englisch)
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 für jede Zusammenhangskomponente des Graphen einen minimalen Spannbaum. Diese Bäume bilden einen minimalen aufspannenden Wald.
Idee Der Algorithmus von Kruskal nutzt die Kreiseigenschaft minimaler Spannbäume (, MST). Dazu werden die Kanten in der ersten Phase aufsteigend nach ihrem Gewicht sortiert. In der zweiten Phase wird über die sortierten Kanten iteriert. Wenn eine Kante zwei Knoten verbindet, die noch nicht durch einen Pfad vorheriger Kanten verbunden sind, wird diese Kante zum MST hinzugenommen.
Beispiel 200px|klasse=skin-invert-imageDies ist der Graph, zu dem nach dem Algorithmus von Kruskal ein minimaler Spannbaum berechnet wird. Die Zahlen bei den einzelnen Kanten geben das jeweilige Kantengewicht an. Zu Beginn ist noch keine Kante ausgewählt.200px|klasse=skin-invert-imageDie Kanten AD und CE sind die kürzesten (noch nicht ausgewählten) Kanten des Graphen. Beide können ausgewählt werden. Hier wird zufällig AD ausgewählt. (Dass diese keinen Kreis bildet, ist im ersten Schritt selbstverständlich.)200px|klasse=skin-invert-imageNun ist CE die kürzeste, noch nicht ausgewählte Kante. Da sie mit AD keinen Kreis bildet, wird sie nun ausgewählt.200px|klasse=skin-invert-imageDie nächste Kante ist DF mit Länge 6. Sie bildet mit den schon gewählten Kanten keinen Kreis und wird deshalb ausgewählt.200px|klasse=skin-invert-imageJetzt könnten die Kanten AB und BE, jeweils mit Länge 7, ausgewählt werden. Es wird zufällig AB gewählt. Die Kante BD wird rot markiert, da sie mit den bis jetzt gewählten Kanten einen Kreis bilden würde und somit im weiteren Verlauf des Algorithmus nicht mehr berücksichtigt werden muss.200px|klasse=skin-invert-imageBE ist nun mit Länge 7 die kürzeste der noch nicht ausgewählten Kanten und da sie mit den bisher gewählten keinen Kreis bildet, wird sie ausgewählt. Analog zur Kante BD im letzten Schritt werden jetzt die Kanten BC, DE und FE rot markiert.200px|klasse=skin-invert-imageAls letzte wird die Kante EG mit Länge 9 ausgewählt, da alle kürzeren bzw. gleich langen Kanten entweder schon ausgewählt sind oder einen Kreis bilden würden. Die Kante FG wird rot markiert. Da nun alle nicht ausgewählten Kanten einen Kreis bilden würden (sie sind rot markiert) ist der Algorithmus am Ende angelangt und der grüne Graph ist ein minimaler Spannbaum des zugrundeliegenden Graphen.
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 . bezeichnet die Menge der Knoten (vertices), die Menge der Kanten (edges). Die Gewichtsfunktion ordnet jeder Kante ein Kantengewicht zu.
Output Der Algorithmus liefert einen minimalen Spannbaum mit .
Pseudocode 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 . mini|160x160px|Ein Beispiel für den Algorithmus von Kruskal basierend auf dem Euklidischen Abstand. G = (V,E,w): ein zusammenhängender, ungerichteter, kantengewichteter Graph kruskal(G) 1 2 3 Sortiere die Kanten in L aufsteigend nach ihrem Kantengewicht. 4 solange 5 wähle eine Kante mit kleinstem Kantengewicht 6 entferne die Kante aus 7 wenn der Graph keinen Kreis enthält 8 dann 9 M = (V,E') ist ein minimaler Spannbaum von G.
Derselbe Algorithmus lässt sich analog für einen maximalen Spannbaum anwenden. Sei etwa ein zusammenhängender kantengewichteter Graph. Dann gibt man mit , und im Algorithmus von Kruskal ein. Als Ausgabe erhält man schließlich einen minimalen Spannbaum von und somit einen maximalen von .
Zum Testen, ob Knoten und in unterschiedlichen Teilbäumen sind, kann eine Union-Find-Struktur verwendet werden. Dann ergibt sich eine Laufzeit von . Dabei ist die Zeit, die zum Sortieren der Kantengewichte benötigt wird und das Inverse der Ackermannfunktion. Für realistische Eingaben ist immer kleiner oder gleich
Programmierung Das folgende Beispiel in der Programmiersprache C++ zeigt die Implementierung eines ungerichteten Graphen mit einem Array von Kanten. Der ungerichtete Graph wird als Klasse UndirectedGraph deklariert. Bei der Ausführung des Programms wird die Methode main verwendet, die die Kanten und Kantengewichte eines minimalen Spannbaums auf der Konsole ausgibt. Die Funktion unionSubsets verwendet union by rank, um zwei Teilmengen von Kanten des Graphen zu vereinigen. #include <iostream> #include <sstream> using namespace std;
// Deklariert den Datentyp für die Knoten des Graphen struct Node { int index; string value; Node* next;
// Deklariert den Datentyp für die Kanten des Graphen struct Edge { int startIndex; int endIndex; int weight;
// Deklariert die Klasse für den ungerichteten Graphen class UndirectedGraph { public: int numberOfVertices; Edge* edges; // Pointer auf das Array für die Kanten
// Deklariert die Klasse für Teilmengen (Teilbäume) der Kantenmenge des ungerichteten Graphen class subset { public: int parent; // Index der Wurzel int rank; // Rang der Teilmenge
// Diese rekursive Funktion gibt den Index der Wurzel der Teilmenge (Teilbaum) mit dem Index i zurück int find(subset subsets[], int i) { // Setzt Index der Wurzel auf den Index der Wurzel der Teilmenge mit dem Index i if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent); // Rekursiver Aufruf der Funktion
return subsets[i].parent; }
// Diese Methode bildet die Vereinigungsmenge der zwei Teilmengen (Teilbäume) mit den Indexen index1 und index2 void unionSubsets(subset subsets[], int index1, int index2) { int newIndex1 = find(subsets, index1); // Index der Teilmenge mit dem Index index1 int newIndex2 = find(subsets, index2); // Index der Teilmenge mit dem Index index2 // Hängt den Teilbaum mit dem niedrigeren Rang unter die Wurzel des Baums mit dem höheren Rang if (subsets[newIndex1].rank < subsets[newIndex2].rank)
subsets[newIndex1].parent = newIndex2;
else if (subsets[newIndex1].rank > subsets[newIndex2].rank)
subsets[newIndex2].parent = newIndex1;
else // Wenn die Teilbäume denselben Rang haben, wird der Rang des einen Baums erhöht und der andere Baum unter die Wurzel des anderen Baums gehängt
subsets[newIndex2].parent = newIndex1; subsets[newIndex1].rank++;
// Diese Funktion vergleicht die Gewichte der Kanten edge1 und edge2 int compare(const void* edge1, const void* edge2) { return ((Edge*)edge1)->weight > ((Edge*)edge2)->weight; // Gibt 1 zurück, wenn der Vergleich true ergibt. Gibt 0 zurück, wenn der Vergleich false ergibt. }
// Diese Funktion verwendet den Algorithmus von Kruskal und gibt den minimalen Spannbaum zurück Edge* getMSTByKruskal(UndirectedGraph* graph) { Edge* edges = graph->edges; // Pointer auf das Array für die Kanten int numberOfVertices = graph->numberOfVertices; // Variable für die Anzahl der Knoten int numberOfEdges = sizeof(edges); // Variable für die Anzahl der Kanten
Edge* minimalSpanningTree = new Edge[numberOfVertices]; // Deklariert ein Array für die Kanten, das als Ergebnis der Methode zurückgegeben wird int currentIndex = 0; // Aktueller Kantenindex int nextIndex = 0; // Kantenindex für die nächste Iteration qsort(edges, numberOfEdges, sizeof(edges), compare); // Sortiert das Array edges der Kanten mit der C++-Standardfunktion qsort (Sortierverfahren Quicksort) und der oben definierten Vergleichsfunktion compare
subset* subsets = new subset[numberOfVertices]; // Deklariert ein Array für die Teilmengen der Kantenmenge for (int i = 0; i < numberOfVertices; i++) // for-Schleife, die Teilmengen mit einzelnen Kanten erzeugt
subsets[i].parent = i; subsets[i].rank = 0;
while (currentIndex < numberOfVertices - 1 && nextIndex < numberOfEdges) // So lange der aktuelle Kantenindex kleiner als die Anzahl der Knoten minus 1 ist
Edge nextEdge = edges[nextIndex++]; // Weist die verbleibende Kante mit dem kleinsten Kantengewicht zu und erhöht den Kantenindex für die nächste Iteration um 1 int index1 = find(subsets, nextEdge.startIndex); // Index der Wurzel der Teilmenge mit dem Index nextEdge.startIndex int index2 = find(subsets, nextEdge.endIndex); // Index der Wurzel der Teilmenge mit dem Index nextEdge.endIndex if (index1 != index2) // Wenn die Kante keinen Zyklus erzeugt
minimalSpanningTree[currentIndex++] = nextEdge; // Fügt die Kante dem minimalen Spannbaum hinzu unionSubsets(subsets, index1, index2); // Methodenaufruf, der die Vereinigungsmenge der zwei Mengen mit den Indexen index1 und index2 bildet
return minimalSpanningTree; }
// Gibt die Kanten, die Gewichte und das gesamte Kantengewicht des minimalen Spannbaums auf der Konsole aus string MSTtoString(Edge* minimalSpanningTree) { stringstream text; int weight = 0; for (int i = 0; i < sizeof(minimalSpanningTree) - 1; i++)
Edge edge = minimalSpanningTree[i]; text << "(" << edge.startIndex << ", " << edge.endIndex << "), Gewicht: " << edge.weight << endl; weight += edge.weight;
text << "Kantengewicht des minimalen Spannbaums: " << weight << endl; return text.str(); // Typumwandlung von stringstream nach string }
// Hauptfunktion die das Programm ausführt int main() { // Deklariert und initialisiert ein Array mit 5 Kanten Edge* edges = new Edge; edges.startIndex = 0; edges.endIndex = 1; edges.weight = 10; edges.startIndex = 0; edges.endIndex = 2; edges.weight = 6; edges.startIndex = 0; edges.endIndex = 3; edges.weight = 5; edges.startIndex = 1; edges.endIndex = 3; edges.weight = 15; edges.startIndex = 2; edges.endIndex = 3; edges.weight = 4;
// Erzeugt den ungerichteten Graphen mit den gegebenen Kanten UndirectedGraph* undirectedGraph = new UndirectedGraph; undirectedGraph->edges = edges; undirectedGraph->numberOfVertices = 4; Edge* minimalSpanningTree = getMSTByKruskal(undirectedGraph); // Aufruf der Methode, die einen Pointer auf das Array von Kanten zurückgibt cout << MSTtoString(minimalSpanningTree); // Aufruf der Methode, die das Ergebnis auf der Konsole ausgibt }
Varianten Paralleles Sortieren Das Sortieren der ersten Phase kann parallelisiert werden. In der zweiten Phase ist es für die Korrektheit jedoch wichtig, dass die Kanten nacheinander abgearbeitet werden. Mit Prozessoren kann in linearer Zeit parallel sortiert werden. Dadurch sinkt die Gesamtlaufzeit auf .
Filter-Kruskal