Kruskal Algorithmus

Gegeben sind Städte auf einer Landkarte. Benötigt wird ein Leitungsnetz, das alle Städte miteinander verbindet und mit minimalen Leitungslängen verwaltet werden kann.

Hast Du schon herausgefunden, wie Du ein solches Problem lösen kannst?

Das Problem lässt sich zum Beispiel auch mit Backtracking lösen, dafür gibt es aber effektivere Methoden. Eine davon ist der Kruskal-Algorithmus.

Kruskal Algorithmus Definition

Wie funktioniert der Algorithmus von Kruskal?

Joseph Bernard Kruskal (* 1929 in New York) veröffentlichte 1956 in einer Zeitschrift einen Algorithmus zum Auffinden der kürzesten Verbindung von einem Knoten zu allen Knoten in einem Graphen (Single-Source Shortest Path Problem).

Dieser basiert auf der Arbeit von Vojtech Jarnik, der bereits 1930 die Grundlagen für die Algorithmen von Prim und Kruskal legte. Beide Algorithmen geben einen minimalen Spannbaum zurück.

Das Prinzip, auf dem das Verfahren beruht, nennt sich sogenanntes Greedy-Prinzip: Greedy-Algorithmen suchen immer nach der lokal optimalen Variante und nehmen daraus das Ziel, auch global für beste Ergebnisse.

Die Idee von Kruskals Algorithmus ist ganz einfach:

• Betrachte jeweils eine Verbindung in der Reihenfolge der Länge (kürzeste zuerst).
• Eine Kante gehört zur Lösung, wenn sie zwei noch nicht verbundene Knoten verbindet, ansonsten wird die Verbindung ignoriert.
• Wiederhole dies, bis Du n-1 Verbindungen für die Lösung findest.

Kruskal Algorithmus minimaler Spannbaum

Der Kruskal-Algorithmus arbeitet mit einer sortierten Liste von Kanten. Sie besteht aus allen Kanten, die im ursprünglichen Graphen enthalten sind. Eine gute Datenstruktur zum Speichern dieser Kanten ist eine Prioritätswarteschlange, die die Kanten entsprechend ihrer Gewichtung organisiert.

Jede Kante von dieser Liste wird betrachtet und entweder verworfen oder für die Konstruktion des entsprechenden minimalen Spannbaums ausgewählt. Aus den Teilbäumen wird dann sequentiell ein minimaler Spannbaum aufgebaut.

Kruskal Algorithmus Vorgehensweise

Die Vorgehensweise ist in den folgenden Zeilen beschrieben:

1. Der Algorithmus beginnt mit einer leeren Menge von Kanten. Jeder Knoten im Diagramm wird als separate Komponente angezeigt.

2. Die Kanten des Graphen werden entsprechend ihrer Kantengewichte in einer Prioritätsschlange sortiert.

3. Aus dieser Priority-Queue wird nun die Kante mit dem geringsten Gewicht gezogen.

4. Hier wird geprüft, ob die durch diese Kante verbundenen Knoten in unterschiedlichen Komponenten liegen.

   • Wenn ja: Verbindung aus der Warteschlange entfernen, entsprechende Komponenten zusammenfügen und Verbindung zur Ergebnisliste hinzufügen.

   • Falls nein: Entferne nur Kanten aus der Warteschlange.

5. Wenn die Prioritätswarteschlange nicht leer ist, gehe zu 3.

6. Ende.

Kruskal-Algorithmus Anwendung

Der Algorithmus wird mit einem Wald initialisiert, der aus Bäumen mit einem einzigen Knoten besteht. Kanten werden entsprechend ihrer Gewichtung in Warteschlangen einsortiert.

Bei jeder Iteration werden Kanten aus der Warteschlange entfernt. Wenn die Endpunkte einer Kante zu verschiedenen Bäumen gehören, werden sie über Kanten hinweg verbunden.

Dies wird wiederholt, bis alle Knoten zu demselben Baum gehören oder die Warteschlange keine Kanten mehr hat.

Wie schaut das alles im Pseudocode aus?

Kruskals Algorithmus nimmt als Input einen Graphen G mit einer entsprechenden Gewichtsfunktion w. Output ist der minimale Spannbaum T von G.

BEGIN

  T ← ∅

  queue ← sortiere Kanten E nach l.

  FOREACH v in G.V

    make-tree(v);

  WHILE queue ≠ ∅ AND trees-count > 1 DO

    {u, v} ← queue.extractMin()

    IF !(T ∪ {{u, v}} enthält Kreis)

      T.add({u, v})

      merge(tree-of(u), tree-of(v))    

END

Kruskal Algorithmus Java

Hier ist ein kleines Beispiel für Kruskals Algorithmus in Java-Code:

Kruskal-Algorithmus – Minimum Spanning Tree (MST) – Vollständige Java-Implementierung.

Das Folgende wird als Ausgangsgraph angegeben:

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

public class KrushkalMST {
    static class Edge {
        int source;
        int destination;
        int weight;

        public Edge(int source, int destination, int weight) {
            this.source = source;
            this.destination = destination;
            this.weight = weight;

        }

    }

    static class Graph {
        int vertices;
        ArrayList allEdges = new ArrayList<>();
                 
                Graph(int vertices) {
                         this.vertices = vertices;

        }

        public void addEgde(int source, int destination, int weight) {
            Edge edge = new Edge(source, destination, weight);
            allEdges.add(edge); //Zu den Gesamtkanten hinzufügen

        }
      public void kruskalMST(){
       PriorityQueue pq = new PriorityQueue<>(allEdges.size(), Comparator.comparingInt(o -> o.weight));
      //Füge alle Kanten zur Prioritätswarteschlange hinzu, 
     //Sortiere die Kanten nach Gewichtungen  
      for (int i = 0; i <allEdges.size(); i++){ 
         pq.add(allEdges.get(i));      } //Erstellen eines übergeordneten Arrays []     int [] parent = new int[vertices]; //makeset    makeSet(parent);        ArrayList mst = new ArrayList<>();  // vertices - 1 edges   int index = 0;   while (inddex<vertices-1){        Edge edge = pq.remove();  //Überprüfe, ob durch Hinzufügen dieser Kante ein Kreis erstellt wird        int x_set = find(parent, edge.source);       int y_set = find(parent,edge.ddestination);       if()x_set==y_set){ //ignorieren, wenn ein Kreis erstellt       }else{ //Füge es im Endergebnis hinzu           mst.add(edge);           index++;           union(parent,x_set,y_set);        }  } //Drücken MST   System.out.println("Minimaler Spannbaum: ");   printGraph(mst); }public void makeSet(int [] parent){    //Make set- Erstellen eines neuen Elements mit einem Übergeordneten Array      for(int i=0;i<vertices;i++){         parent[i]=i;       }   }     public int find(int [] parent, int vertex){            if(parent[vertex]!=vertex)                return find(parent, parent[vertex]);;            return vertex;        }public void union(int [] parent, int   x, int y){            int x_set_parent = find(parent, x);            int y_set_parent = find(parent, y);            //Mache x als übergeordnetes Element von y            parent[y_set_parent] = x_set_parent;        }     public void printGraph(ArrayList edgeList){     for(int i=0;i<edgeList.size();i++){            Edge edge = edgeList.get(i);     System.out.println("Kante-" + i + "Start: " + edge.source + " Ziel: " + edge.destination + " Gewicht: " + edge.weigth);      }   }}public static void main(String[] args) {            int vertices = 6;            Graph graph = new Graph(vertices);            graph.addEgde(0, 1, 4);            graph.addEgde(0, 2, 3);            graph.addEgde(1, 2, 1);            graph.addEgde(1, 3, 2);            graph.addEgde(2, 3, 4);            graph.addEgde(3, 4, 2);            graph.addEgde(4, 5, 6);            graph.kruskalMST();    }}

Nach dem Ausführen des Kruskal-Algorithmus bekommt man die folgende MST:

Kruskal Algorithmus Beispiel

Das folgende Beispiel soll den Ablauf des Algorithmus verdeutlichen. Basierend auf dem folgenden Diagramm wird ein minimaler Spannbaum erstellt. Kanten und Knoten des minimalen Spannbaums sind rot hinterlegt.

Kruskal Algorithmus Laufzeit

Die Ausführungszeit des Algorithmus hängt stark von Schritt 3 ab. Im Allgemeinen kann jeder Sortieralgorithmus verwendet werden, um die Kanten des Graphen zu sortieren. Wichtig ist hier die Laufzeit des Algorithmus.

Unter Verwendung der Prioritätswarteschlange als Datenstruktur in Schritt 3 ist das Finden und Entfernen der kleinsten Kante in e O(log |E|) Schritten möglich. Die ersten n Komponenten der Partition können in insgesamt O(n • log n) Schritten kombiniert werden. Der Graph G ist zusammenhängend, hat also mindestens n-1 Kanten.

Daher ist die Gesamtkomplexität O(|E| • log|E|).