Was ein minimaler Spannbaum ist
Ein Spannbaum verbindet alle Knoten eines zusammenhängenden, ungerichteten Graphen so, dass kein Kreis entsteht. Bei n Knoten besteht er immer aus genau n − 1 Kanten. Unter allen möglichen Spannbäumen hat der minimale das kleinste Gesamtgewicht. Typische Anwendungen sind die Planung von Kabel-, Rohr- oder Straßennetzen mit möglichst geringen Baukosten und Verfahren der Clusteranalyse.
Joseph Kruskal beschrieb 1956 ein einfaches Vorgehen: Alle Kanten werden nach Gewicht aufsteigend sortiert und der Reihe nach geprüft. Eine Kante wird übernommen, wenn sie zwei Teile verbindet, die bisher getrennt waren. Würde sie einen Kreis schließen, wird sie verworfen. Der Rechner verwaltet die Teile mit einer Union-Find-Struktur, die diese Prüfung sehr schnell erledigt.
Wählen Sie die Variante „maximal“, sortiert der Rechner absteigend und findet den Spannbaum mit dem größten Gesamtgewicht. Das ist nützlich, wenn Gewichte etwas Positives darstellen, etwa die Kapazität oder Zuverlässigkeit einer Verbindung, und das stärkste Gerüst gesucht ist.
Hinweise zu Ergebnis und Eingabe
Ist der Graph nicht zusammenhängend, kann es keinen Spannbaum über alle Knoten geben. Der Rechner berechnet dann für jeden Teil einen eigenen Baum, zusammen ein sogenannter Spannwald, und zeigt die Zahl der getrennten Teile an. Prüfen Sie in diesem Fall, ob eine Verbindung in Ihrer Liste fehlt.
Haben mehrere Kanten dasselbe Gewicht, kann es mehrere minimale Spannbäume geben. Das Gesamtgewicht ist bei allen gleich, nur die gewählten Kanten können sich unterscheiden. Der Rechner entscheidet bei Gleichstand nach der Reihenfolge Ihrer Eingabe. Sind alle Gewichte verschieden, ist der minimale Spannbaum eindeutig.
Neben Kruskal gibt es den Algorithmus von Prim, der von einem Startknoten aus wächst und immer die günstigste Kante zum bereits verbundenen Teil hinzunimmt. Beide liefern dasselbe Gesamtgewicht. Kruskal eignet sich besonders für dünn besetzte Graphen, Prim für dichte Graphen mit vielen Kanten.
Ein minimaler Spannbaum ist nicht dasselbe wie ein System kürzester Wege. Der Weg zwischen zwei Knoten im Spannbaum kann deutlich länger sein als der kürzeste Weg im ursprünglichen Graphen. Für Wegfragen ist der Dijkstra-Rechner das passende Werkzeug.
Tipps und typische Fehler
Netze günstig planen.
- Kanten: n − 1.
- Kreise: Vermeiden.
- Gleichstand: Mehrere Lösungen.
- Zusammenhang: Prüfen.
Mehr zum Thema Zahlensysteme, Logik und Prüfziffern
Häufige Fragen
Wie viele Kanten hat ein Spannbaum?
Bei n Knoten genau n − 1 Kanten. Mit 6 Knoten sind es also 5 Kanten.
Sind negative Gewichte erlaubt?
Ja. Anders als bei Dijkstra stören negative Gewichte bei Kruskal nicht, weil nur die Reihenfolge der Kanten zählt.
Was passiert mit Schleifen von einem Knoten zu sich selbst?
Eine solche Kante würde sofort einen Kreis bilden. Der Rechner verwirft sie und zählt sie zu den verworfenen Kanten.
Ist der minimale Spannbaum eindeutig?
Ja, wenn alle Kantengewichte verschieden sind.
Wofür braucht man einen Spannbaum?
Etwa für günstige Leitungsnetze oder Clusterverfahren.
- minimaler Spannbaum
- Kruskal Algorithmus
- Spannbaum berechnen
- MST berechnen
- Minimum Spanning Tree
- Kruskal online
Alle Berechnungen erfolgen direkt in Ihrem Browser, Ihre Eingaben werden nicht übertragen oder gespeichert. Die Ergebnisse sind Orientierungswerte ohne Gewähr und ersetzen keine steuerliche, rechtliche oder finanzielle Beratung. Die Erklärtexte auf dieser Seite wurden mit KI erstellt. Letzte inhaltliche Änderung dieser Seite: . Mehr dazu: So entstehen und prüfen wir die Rechner.