• :00Tage
  • :00Std
  • :00Min
  • 00Sek
Ein neues Zeitalter des Lernens steht bevorKostenlos anmelden
Login Anmelden

Select your language

Suggested languages for you:
StudySmarter - Die all-in-one Lernapp.
4.8 • +11k Ratings
Mehr als 5 Millionen Downloads
Free
|
|

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.Wie funktioniert der Algorithmus von Kruskal?Joseph Bernard Kruskal (* 1929…

Von Expert*innen geprüfte Inhalte
Kostenlose StudySmarter App mit über 20 Millionen Studierenden
Mockup Schule

Entdecke über 200 Millionen kostenlose Materialien in unserer App

Kruskal Algorithmus

Illustration

Lerne mit deinen Freunden und bleibe auf dem richtigen Kurs mit deinen persönlichen Lernstatistiken

Jetzt kostenlos anmelden

Nie wieder prokastinieren mit unseren Lernerinnerungen.

Jetzt kostenlos anmelden
Illustration

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.

Kruskals Algorithmus ist ein "greedy" Algorithmus, der den minimalen Spannbaum eines verbundenen, gewichteten, ungerichteten Graphen effizient berechnet und dabei in jedem Schritt die gierige/beste Wahl trifft, in der Hoffnung, eine globale Lösung zu finden.

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.

Wenn Du mehr über die Spannbäume wissen möchtest, dann ließ Dir doch den Artikel "Prim Algorithmus" durch!

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(); }}
 Output:
 Der minimaler Spannbaum:
Kante-0 Start: 1 Ziel: 2 Gewicht: 1
Kante-1 Start: 1 Ziel: 3 Gewicht: 2
Kante-2 Start: 3 Ziel: 4 Gewicht: 2
Kante-3 Start: 0 Ziel: 2 Gewicht: 3
Kante-4 Start: 4 Ziel: 5 Gewicht: 6

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 DurchlaufBeschreibung

1. Ausgangsgraph

2. Die Kante mit dem niedrigsten Gewicht wird aus der Prioritätswarteschlange genommen. Dies ist eine Kante(1,2) mit w(1,2) = 10, die aus der Warteschlange entfernt wird.
3. Die nächstkleinere Kante ist (3,4) mit w(3,4) = 15. Sie verbindet zwei Knoten unterschiedlicher Komponenten und ist daher auch im minimalen Spannbaum enthalten.
4.Dann wird die Kante (2,3) mit w(2,3) = 20 ausgewählt.
5. Schließlich wird die Kante (0,1) hinzugefügt. Damit sind alle Knoten verbunden und somit der minimale Spannbaum erstellt.

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|).

Kruskal Algorithmus – Das Wichtigste

  • Kruskal-Algorithmus Definition: Kruskals Algorithmus ist ein "greedy" Algorithmus, der den minimalen Spannbaum eines verbundenen gewichteten ungerichteten Graphen effizient berechnet.
  • Kruskal-Algorithmus - minimaler Spannbaum : Der Kruskal-Algorithmus arbeitet mit einer sortierten Liste von Kanten. Jede Kante von dieser Liste wird betrachtet und entweder verworfen oder für die Konstruktion des entsprechenden minimalen Spannbaums ausgewählt.
  • Kruskal-Algorithmus Laufzeit: Der Graph G ist zusammenhängend, hat also mindestens n-1 Kanten.

    Daher ist die Gesamtkomplexität von Kruskal-Algorithmus O(|E| • log|E|).


Nachweise

  1. algorithms.discrete.ma.tim.de: Der Algorithmus von Kruskal. (31.10.2022)
  2. cermat.org: Der Algorithmus von Kruskal. (31.10.2022)
  3. g-ymnasium.de: Die Algorithmen von Prim und Kruskal. (31.10.2022)

Häufig gestellte Fragen zum Thema Kruskal Algorithmus

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

Kruskals Algorithmus ist ein "greedy" Algorithmus, der den minimalen Spannbaum eines verbundenen gewichteten ungerichteten Graphen effizient berechnet (in jedem Schritt die gierige/beste Wahl trifft, in der Hoffnung, eine globale Lösung zu finden). 

Finales Kruskal Algorithmus Quiz

Kruskal Algorithmus Quiz - Teste dein Wissen

Frage

Ist Kruskal-Algorithmus Greedy-Algorithmus?

Antwort anzeigen

Antwort

Das Prinzip, auf dem das Verfahren beruht, nennt sich sogenanntes Greedy-Prinzip.

Frage anzeigen

Frage

Wahr oder Falsch

Nach dem Do-it-yourself-Motto suchen Greedy-Algorithmen immer nach der lokal optimalen Variante und nehmen daraus das Ziel, auch global für beste Ergebnisse.

Antwort anzeigen

Antwort

Wahr

Frage anzeigen

Frage

Ergänze

 Es basiert auf der Arbeit von Vojtech (1)         , der bereits 1930 die Grundlagen für die Algorithmen von (2)            und Kruskal legte. Dies gibt einen minimalen (3)             zurück.

Antwort anzeigen

Antwort

(1) Jarnik

(2) Prim

(3) Spannbaum

Frage anzeigen

Frage

Wie funktioniert der Algorithmus von Kruskal?

Antwort anzeigen

Antwort

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).

Frage anzeigen

Frage

Wahr oder Falsch

Kruskals Algorithmus ist ein "greedy" Algorithmus, der den minimalen Spannbaum eines verbundenen gewichteten ungerichteten Graphen effizient berechnet

Antwort anzeigen

Antwort

 Wahr

Frage anzeigen

Frage

Ergänze

Der Kruskal-Algorithmus arbeitet mit einer sortierten (1)         von Kanten. Es besteht aus allen Kanten, die im ursprünglichen (2)           enthalten sind.

Antwort anzeigen

Antwort

(1) Liste

(2)Graphen

Frage anzeigen

Frage

Wahr oder Falsch

Beim Kruskal-Algorithmus aus den Teilbäumen wird dann sequentiell ein maximaler Spannbaum aufgebaut. 

Antwort anzeigen

Antwort

Falsch

Frage anzeigen

Frage

Wie wird der Kruskal-Algorithmus initialisiert?

Antwort anzeigen

Antwort

Der Algorithmus wird mit einem Wald initialisiert, der aus Bäumen mit einem einzigen Knoten besteht. 

Frage anzeigen

Frage

Ergänze

Kruskals Algorithmus nimmt als (1)          einen Graphen G mit einer entsprechenden Gewichtsfunktion w. (2)            ist der minimale Spannbaum T von G. 

Antwort anzeigen

Antwort

(1) Input

(2) Output

Frage anzeigen

Frage

Welche Funktion hat diese Code-Teil:

 " System.out.println("Minimaler Spannbaum: ");
printGraph(mst);
  "

Antwort anzeigen

Antwort

Gibt minimaller Spannbaum auf dem Konsole aus!

Frage anzeigen

Frage

Gesamtkomplexität von Kruskal-Algorithmus?

Antwort anzeigen

Antwort

Gesamtkomplexität von Kruskal-Algorithmus ist O( |E| • log|E| ) .

Frage anzeigen

Frage

Wahr oder Falsch

Der Graph G ist zusammenhängend, wenn der also mindestens n (n-1) Kanten hat.

Antwort anzeigen

Antwort

Falsch

Frage anzeigen

Frage

Ergänze

Der Algorithmus von (1)          liefert, ebenso wie der (2)           - Algorithmus, durch ein gieriges Verfahren einen minimalen Spannbaum eines bewerteten ungerichteten Graphen. 

Antwort anzeigen

Antwort

(1)Kruskal

(2) Prim

Frage anzeigen

Frage

Wahr oder Falsch

Der Algorithmus von Kruskal bestimmt einen minimal aufspannenden Baum mit Zeitkomplexität  O(|V2 | * log |V |). 

Antwort anzeigen

Antwort

Falsch

Frage anzeigen

Frage

Ergänze

Normalerweise kann zur Sortierung der Kanten des Graphen jeder (1)           verwendet werden. Die (2)           des Algorithmus ist hierbei entscheidend. 

Antwort anzeigen

Antwort

(1) Sortieralgorithmus

(2) Laufzeit

Frage anzeigen

60%

der Nutzer schaffen das Kruskal Algorithmus Quiz nicht! Kannst du es schaffen?

Quiz starten

Wie möchtest du den Inhalt lernen?

Karteikarten erstellen
Inhalte meiner Freund:innen lernen
Ein Quiz machen

94% der StudySmarter Nutzer erzielen bessere Noten.

Jetzt anmelden

94% der StudySmarter Nutzer erzielen bessere Noten.

Jetzt anmelden

Wie möchtest du den Inhalt lernen?

Karteikarten erstellen
Inhalte meiner Freund:innen lernen
Ein Quiz machen

Kostenloser informatik Spickzettel

Alles was du zu . wissen musst. Perfekt zusammengefasst, sodass du es dir leicht merken kannst!

Jetzt anmelden

Finde passende Lernmaterialien für deine Fächer

Alles was du für deinen Lernerfolg brauchst - in einer App!

Lernplan

Sei rechtzeitig vorbereitet für deine Prüfungen.

Quizzes

Teste dein Wissen mit spielerischen Quizzes.

Karteikarten

Erstelle und finde Karteikarten in Rekordzeit.

Notizen

Erstelle die schönsten Notizen schneller als je zuvor.

Lern-Sets

Hab all deine Lermaterialien an einem Ort.

Dokumente

Lade unzählige Dokumente hoch und habe sie immer dabei.

Lern Statistiken

Kenne deine Schwächen und Stärken.

Wöchentliche

Ziele Setze dir individuelle Ziele und sammle Punkte.

Smart Reminders

Nie wieder prokrastinieren mit unseren Lernerinnerungen.

Trophäen

Sammle Punkte und erreiche neue Levels beim Lernen.

Magic Marker

Lass dir Karteikarten automatisch erstellen.

Smartes Formatieren

Erstelle die schönsten Lernmaterialien mit unseren Vorlagen.

Melde dich an für Notizen & Bearbeitung. 100% for free.

Fang an mit StudySmarter zu lernen, die einzige Lernapp, die du brauchst.

Jetzt kostenlos anmelden
Illustration