Startseite▸Netzwerke & Graphentheorie▸Minimaler Spannbaum

🌲 Minimaler Spannbaum

Sehen Sie zu, wie sich Kruskals und Prims MST-Algorithmen Schritt für Schritt auf einem gewichteten Zufallsgraphen animieren. Wechseln Sie zwischen den Algorithmen, sehen Sie Kantenkosten auf den Bögen und vergleichen Sie, wie jeder Ansatz den optimalen Spannbaum aufbaut.

Netzwerke & Graphentheorie3DEinfach60 FPS

Simulation des minimalen Spannbaums, die Kruskals und Prims Algorithmen Schritt für Schritt auf einem zufälligen gewichteten Graphen animiert. Kruskals Algorithmus sortiert alle Kanten nach Gewicht und verwendet eine Union-Find-Struktur (DSU), um gierig die günstigste Kante hinzuzufügen, die keinen Zyklus erzeugt. Prims Algorithmus lässt den Baum von einem Startknoten aus wachsen und fügt stets die günstigste Kante hinzu, die den aktuellen Baum mit einem unbesuchten Knoten verbindet. Kantenkosten werden auf jedem Bogen angezeigt.

Über diese Simulation

Diese Simulation animiert zwei klassische gierige Algorithmen — Kruskals und Prims —, die den minimalen Spannbaum (MST) eines gewichteten Graphen berechnen: die Teilmenge der Kanten, die jeden Knoten verbindet und dabei das Gesamtkantengewicht so gering wie möglich hält. Knoten sind über die Zeichenfläche verteilt und mit ihren nächsten Nachbarn verbunden, wobei jede Kante ein numerisches Gewicht trägt. Zuzusehen, wie der Baum Kante für Kante wächst, zeigt, wie sehr unterschiedliche Strategien zur selben optimalen Struktur gelangen — ein Ergebnis, das durch die Schnitteigenschaft von Spannbäumen garantiert wird.

🔬 Was gezeigt wird

Ein zufälliger gewichteter Graph mit 8–40 Knoten, von denen jeder mit ungefähr seinen vier nächsten Nachbarn verbunden ist, mit Gewichten, die aus dem Bildschirmabstand abgeleitet werden. Kruskals Algorithmus sortiert alle Kanten nach Gewicht und fügt die günstigste hinzu, die keinen Zyklus bildet, wobei eine Union-Find-Struktur (disjunkte Mengen) zur Zykluserkennung dient. Prims Algorithmus lässt stattdessen einen einzigen Baum ab Knoten 0 wachsen und fügt wiederholt die günstigste Kante hinzu, die einen unbesuchten Knoten erreicht. Beide enden mit genau N−1 Kanten und demselben minimalen Gesamtgewicht.

🎮 Bedienung

Wechseln Sie zwischen Kruskal und Prim und stellen Sie dann die Knotenanzahl mit dem Knoten-Schieberegler ein (8–40). Wählen Sie die Wiedergabegeschwindigkeit Langsam, Normal oder Schnell. Drücken Sie Abspielen, um kontinuierlich zu animieren, oder Schritt, um jeweils eine Entscheidung weiterzugehen, und beobachten Sie Kandidaten- (gelb), akzeptierte (grün) und abgelehnte (rot) Kanten. Neuer Graph erzeugt ein neues Layout. Das Seitenpanel zeigt Knotenanzahl, Gesamtkanten, MST-Kanten und laufendes MST-Gewicht an.

💡 Wussten Sie schon?

Beide Algorithmen sind nachweislich optimal, doch Kruskals wurde 1956 veröffentlicht, während Prims aus dem Jahr 1957 stammt (und erstmals 1930 von Jarník beschrieben wurde). Bei einem Graphen mit eindeutigen Kantengewichten ist der minimale Spannbaum eindeutig, sodass Kruskal und Prim trotz völlig unterschiedlicher Erkundungsreihenfolge stets auf dieselbe Kantenmenge konvergieren.

Häufig gestellte Fragen

Was ist ein minimaler Spannbaum?

Ein Spannbaum ist eine Menge von Kanten, die jeden Knoten eines Graphen verbindet, ohne einen Zyklus zu bilden, wobei für N Knoten immer genau N−1 Kanten verwendet werden. Der minimale Spannbaum ist der Spannbaum, dessen Kantengewichte in der Summe den kleinstmöglichen Gesamtwert ergeben. Er wird häufig verwendet, um kostengünstige Netzwerke wie Verkabelungen, Pipelines und Straßenverbindungen zu entwerfen.

Wie unterscheiden sich Kruskals und Prims Algorithmen?

Kruskals Algorithmus ist kantenzentriert: Er sortiert alle Kanten nach Gewicht und fügt gierig die jeweils günstigste Kante hinzu, solange sie keinen Zyklus erzeugt, wobei eine Union-Find-Struktur zur Prüfung der Konnektivität verwendet wird. Prims Algorithmus ist knotenzentriert: Er startet bei einem Knoten und erweitert den bestehenden Baum stets um die günstigste Kante zu einem unbesuchten Knoten. Sie untersuchen die Kanten in unterschiedlicher Reihenfolge, liefern aber dasselbe optimale Gewicht.

Was bedeuten die Farben und Beschriftungen?

Jede Kante ist mit ihrem ganzzahligen Gewicht beschriftet, das aus dem Abstand zwischen ihren beiden Knoten berechnet wird. Blasse Kanten sind unverarbeitet, gelbe Kanten sind aktuelle Kandidaten, grüne Kanten wurden in den Baum aufgenommen und rote Kanten wurden abgelehnt, weil sie einen Zyklus erzeugt hätten. Im Prim-Modus sind gefüllte grüne Knoten bereits Teil des wachsenden Baums.

Warum werden im Kruskal-Modus manche Kanten abgelehnt?

Kruskal betrachtet Kanten vom günstigsten zum teuersten, doch das Hinzufügen einer Kante zwischen zwei bereits verbundenen Knoten würde einen Zyklus erzeugen, statt den Baum zu erweitern. Die Union-Find-Struktur erkennt dies in nahezu konstanter Zeit, sodass eine solche Kante als abgelehnt (rot) markiert und übersprungen wird, damit das Ergebnis ein gültiger Baum bleibt.

Liefern die beiden Algorithmen garantiert dasselbe Ergebnis?

Beide erzeugen immer einen minimalen Spannbaum, sodass das Gesamtgewicht identisch ist. Wenn alle Kantengewichte unterschiedlich sind, ist der MST selbst eindeutig, sodass Kruskal und Prim genau dieselben Kanten auswählen. Bei gleichen Gewichten können die gewählten Kanten leicht abweichen, das minimale Gesamtgewicht bleibt jedoch stets gleich.

⚙ Unter der Haube

Schritt-für-Schritt-Animation von Kruskals und Prims MST-Algorithmen auf einem gewichteten Graphen. Wechseln Sie zwischen ihnen und sehen Sie zu, wie jeder den optimalen Spannbaum aufbaut.

Canvas 2DKruskalPrimMSTUnion-Find

3D · Three.js / WebGL-Renderer · Ziel: 60 FPS · läuft vollständig clientseitig, keine Installation nötig