BWL-Lexikon.de
  • Home
  • Grundlagen
    • Aufbau eines Betriebs
    • Definitionen
    • Organisation
    • Personalwirtschaft
    • Planung und Entscheidung
    • Produktionsfaktoren
    • Unternehmensführung
  • BWL
    • Rechtsformen
    • Rechnungswesen
      • Finanzbuchhaltung
      • Kostenarten
      • Jahresabschluss
    • Marketing
    • Logistik
      • Logistik Kennzahlen
      • Beschaffung
      • Lagerverfahren
      • Materialarten
    • Kennzahlen
      • Bilanzkennzahlen
      • Produktivitätskennzahlen
      • Rentabilitätskennzahlen
      • Kennzahlen der GuV
  • VWL
    • Makroökonomie
    • Mikroökonomie
  • Fehler gefunden?

Du bist hier: Startseite » Alle Lektionen » Aufbau eines Betriebs » Planung und Entscheidung » Operations Research » Kruskal Algorithmus

Kruskal Algorithmus

Enthält: Beispiele · Definition · Grafiken · Übungsfragen

Der Kruskal Algorithmus dient der Ermittlung des minimalen Spannbaums eines zusammenhängenden und gewichteten Graphen.

Wir zeigen dir in diesem Kapitel, warum der Kruskal Algorithmus wichtig ist, welche Probleme damit gelöst werden können und wie du ihn anwenden kannst. Nachdem du dir dieses Wissen angeeignet hast, kannst du dein Wissen anhand unserer Übungsaufgaben überprüfen.

Inhalt dieser Lektion

  • Warum ist der Kruskal Algorithmus wichtig?
  • Was versteht man unter dem Kruskal Algorithmus?
  • Beispiel: Anwendung des Kruskal Algorithmus
  • Übungsfragen

Warum ist der Kruskal Algorithmus wichtig?

Im Operations Research eines Unternehmens geht es oft darum, auftretende Probleme optimal zu lösen. Hierbei kann der Kruskal Algorithmus helfen – insbesondere dann, wenn es um die Ermittlung des kostengünstigsten Wegs innerhalb eines Graphen geht, der alle Knoten des Graphen miteinander verbindet.

Dies ist beispielsweise dann wichtig, wenn eine optimale Verbindung zwischen verschiedenen Stationen gefunden werden muss, beispielsweise beim Ausbau eines Schienennetzes.

Was versteht man unter dem Kruskal Algorithmus?

Der Kruskal Algorithmus gehört zur Gruppe der Greedy Algorithmen. Er kann bei zusammenhängenden, gewichteten Graphen angewendet werden, um den minimalen Spannbaum zu ermitteln. Der minimale Spannbaum beschreibt den Teilgraph, der die Kanten beinhaltet, die die kostengünstigste Verbindung aller Knoten innerhalb des Graphen beschreibt.

Ein weiterer Algorithmus, der ebenfalls zur Findung des minimalen Spannbaums eines Graphen dient, ist der Prim Algorithmus. Allerdings funktionieren beide Algorithmen unterschiedlich. Während beim Prim Algorithmus mit einem Knoten gestartet wird und immer die günstigste Kante hinzugefügt wird, beginnt der Kruskal Algorithmus mit allen Knoten ohne Kanten. Nacheinander werden dann die global günstigsten Kanten hinzugefügt.

Beispiel: Anwendung des Kruskal Algorithmus

Um die Funktionsweise des Kruskal Algorithmus zu verstehen, schauen wir uns ein Beispiel an.

Beispiel
Gegeben sei der folgende Graph:

Kruskal Algorithmus - Anwendungsbeispiel: Gegebener Graph
Kruskal Algorithmus – Anwendungsbeispiel: Gegebener Graph

Um den minimalen Spannbaum des Graphen zu finden, nutzten wir den Kruskal Algorithmus.

Hierbei werden zuerst alle im Graph enthaltenen Kanten aufsteigend nach ihrem Gewicht sortiert:

KanteKosten
CE4
AD5
DG7
BE8
AB9
EG11
BC11
DF12
BD13
FG17
DE25

Anschließend wird ein neuer Graph erstellt, der zunächst nur die Knoten des ursprünglichen Graphen ohne die jeweiligen Kanten enthält.

Kruskal Algorithmus - Anwendungsbeispiel: Graph ohne Kanten
Kruskal Algorithmus – Anwendungsbeispiel: Graph ohne Kanten

Anschließend werden die Kanten in der vorher sortierten Reihenfolge eingefügt, beginnend mit der Kante, die das geringste Kantengewicht besitzt. In unserem Beispiel ist das die Kante CE mit einem Kantengewicht von 4.

Diese fügen wir also als erstes in unseren neuen Graphen ein:

Kruskal Algorithmus - Anwendungsbeispiel: Kante mit dem geringsten Wert
Kruskal Algorithmus – Anwendungsbeispiel: Kante mit dem geringsten Wert

Nach der Kante CE betrachten wir nun die nächst kürzere Kante. Das ist Kante AD mit einem Kantengewicht von 5.

Auch diese Kante fügen wir in unseren neuen Graphen ein:

Kruskal Algorithmus - Anwendungsbeispiel: Kante mit dem nächstgeringeren Wert
Kruskal Algorithmus – Anwendungsbeispiel: Kante mit dem nächstgeringeren Wert

Diesen Vorgang wiederholen wir nun für die nächsten Kanten aus unserer vorherigen Sortierung. Sind wir bei Kante EG angekommen, stellen wir fest, dass EG und BC das gleiche Kantengewicht besitzen.

Grundsätzlich kann sich nun eine der Kanten ausgesucht werden. Zu beachten ist dabei, dass im Zuge des Kruskal Algorithmus nur Kanten berücksichtigt werden, die keine Kreise bilden.

Fügen wir die Kante EG ein, so sehen wir, dass ein Kreis im Graphen entstehen würde. Das gleiche passiert, wenn wir die Kante BC einfügen würden. Demnach werden beide Kanten übersprungen und nicht in unseren neuen Graphen eingefügt.

Kruskal Algorithmus: Anwendungsbeispiel: Kanten ausschließen
Kruskal Algorithmus: Anwendungsbeispiel: Kanten ausschließen

Als nächste Kante betrachten wir DF mit dem Kantengewicht 12. Das Einfügen dieser Kante führt nicht zu einer Kreisbildung, weshalb wir sie in unseren Graphen einfügen können.

Mit dem Einfügen der Kante DF können wir erkennen, dass nun alle Knoten miteinander verbunden sind. Wir haben also den minimalen Spannbaum des Graphen gefunden. Alle weiteren Kanten würden zu Kreisen im Graphen führen, weshalb wir sie vernachlässigen können.

Unser neuer Graph ist nun fertig:

Kruskal Algorithmus - Anwendungsbeispiel: Finaler Graph
Kruskal Algorithmus – Anwendungsbeispiel: Finaler Graph

Übungsfragen

#1. Was versteht man unter dem Kruskal Algorithmus?

#2. Wie wird der Kruskal Algorithmus angewendet?

#3. “Der Kruskal Algorithmus dient der Findung des minimalen Spannbaums eines zusammenhängenden, gewichteten Graphen” - diese Aussage ist:

#4. “Beim Kruskal Algorithmus werden Kanten, die Kreise innerhalb des Graphen bilden nicht berücksichtigt.” - Diese Aussage ist:

#5. “Der Kruskal Algorithmus kann nur in ungewichteten Graphen angewendet werden.” - diese Aussage ist:

Fertig

Ergebnis

Könnte dich auch interessieren:

Prim Algorithmus - Anwendungsbeispiel: Finaler Graph

Prim Algorithmus

Der Prim Algorithmus wird genutzt, um den minimalen Spannbaum eines Graphen zu finden. Er kann in Graphen genutzt werden, die … weiterlesen >>

Bellman Ford Algorithmus - Anwendungsbeispiel: Gegebener Graph

Bellman Ford Algorithmus

Um den kürzesten Weg in einem gewichteten Graphen zu ermitteln, kann der Bellman Ford Algorithmus eingesetzt werden. Auch bei Graphen, … weiterlesen >>

Dijkstra Algorithmus - Anwendungsbeispiel

Dijkstra Algorithmus

Der Dijkstra Algorithmus gehört zur Gruppe der Greedy Algorithmen. Er dient der Berechnung des kürzesten Pfades in einem Graphen von … weiterlesen >>

Inzidenzmatrix bei ungerichteten Graphen

Inzidenzmatrix

In der Inzidenzmatrix werden die Beziehungen der Knoten und der Kanten eines Graphen abgebildet. In diesem Kapitel zeigen wir dir, … weiterlesen >>

Graphentheorie

Graphentheorie

Die Graphentheorie als mathematische Methode befasst sich mit der Untersuchung von Graphen als Darstellung von einer Vielzahl von Problemen. Insbesondere … weiterlesen >>

Nichts passendes dabei?

Erkunde andere Fachbereiche oder benutze die Suchfunktion. Falls Du keine Antwort auf Deine Frage findest, schick uns gerne eine Nachricht, wir versuchen dann passenden Content für Dich zu schaffen.

Zur Übersicht
Oder lieber die Suche benutzen?
  • Eselsbrücke
  • |
  • Buchungssatz
  • |
  • Formeln
  • |
  • Beispiele
  • |
  • Grafiken
  • |
  • Definition
  • |
  • Übungsfragen
  • © BWL-Lexikon.de
  • Datenschutz
  • Impressum
  • Cookie Einstellungen
Fehler gefunden?

Danke, dass du dir die Zeit nimmst, uns dein Feedback zu geben. Bitte beschreibe so genau wie möglich wo du einen Fehler gefunden hast.