Warum ein vollständiger Graph — sind Anwendungen nicht oft dünn?

Der **vollständige euklidische** Graph ist ein anschauliches Modell: theoretisch darf jedes Paar verbunden werden, und der MST wählt **n−1** der billigsten Verbindungen ohne Kreis. In realen Netzen gibt es weniger Kanten; dieselben Algorithmen gelten dort ebenfalls, der dichte Fall zeigt aber gut die Sortierung bei **Kruskal** und die Kandidatenwahl bei **Prim**.

Ändert sich der MST, wenn man bei Prim die Wurzel wechselt?

Bei **nicht eindeutigen** Gewichten kann es **mehrere** verschiedene Kantenmengen mit demselben Minimalgewicht geben. Dann können verschiedene Wurzeln (und eine andere Reihenfolge) **verschiedene** MST als Kantenmengen liefern, das **Gesamtgewicht** bleibt aber dasselbe — es wird mit **Kruskal** abgeglichen.

Was bedeutet die rote gestrichelte Linie im Kruskal-Modus?

Das ist die aktuelle Kante aus der sortierten Liste, die man **nicht** aufnehmen darf: beide Enden liegen schon in **einer** Union-Find-Komponente, das Hinzufügen würde einen **Kreis** schließen — der Algorithmus **überspringt** sie.

Minimaler Spannbaum (Prim und Kruskal)

Zufällige Punkte in der Ebene, vollständiger Graph mit euklidischen Gewichten: Prim schrittweise von der Wurzel oder Kruskal mit Union-Find; Vergleich der Gesamtgewichte.

Zum Modell

Ein minimaler Spannbaum verbindet alle Knoten ohne Kreis und mit kleinster Gewichtssumme. n pseudozufällige Punkte in der Ebene (reproduzierbar über die Saat der Anordnung). Der Graph gilt als vollständig: das Kantengewicht ist der euklidische Abstand, jeder Spannbaum hat n−1 Kanten. Prim startet von einer gewählten Wurzel und fügt in jedem Schritt die minimale Kante über den Schnitt „schon im Baum / außen“ hinzu (gierig gemäß der Schnitteigenschaft). Kruskal sortiert alle Kanten nach Gewicht (bei Gleichheit lexikographisch nach Endpunkten, damit es deterministisch bleibt) und durchläuft die Liste mit Union-Find: eine Kante wird angenommen, wenn sie verschiedene Komponenten verbindet, und abgelehnt (rot gestrichelte Hervorhebung), wenn sie einen Kreis schließen würde. Die Gesamtgewichte des MST stimmen bei beiden Verfahren überein.

Für wen: Diskrete Mathematik und Algorithmen: gieriger Aufbau eines MST, Schnitt- und Kreiseigenschaft, Union-Find.

Wichtige Begriffe

minimaler spannbaum (mst)
algorithmus von prim
algorithmus von kruskal
schnitteigenschaft
kreiseigenschaft
union-find (disjunkte mengen)
vollständiger graph
euklidische gewichte

So funktioniert es

Vollständiger Graph aus n Punkten in der Ebene mit Gewichten aus euklidischen Abständen: Prim wächst den Spannbaum von der Wurzel mit der minimalen Kante über den Schnitt; Kruskal geht die Kanten nach steigendem Gewicht durch und Union-Find verwirft eine Kante, wenn sie einen Kreis schließen würde; das Gesamtgewicht des MST stimmt bei beiden überein.

Häufige Fragen

Warum ein vollständiger Graph — sind Anwendungen nicht oft dünn?: Der vollständige euklidische Graph ist ein anschauliches Modell: theoretisch darf jedes Paar verbunden werden, und der MST wählt n−1 der billigsten Verbindungen ohne Kreis. In realen Netzen gibt es weniger Kanten; dieselben Algorithmen gelten dort ebenfalls, der dichte Fall zeigt aber gut die Sortierung bei Kruskal und die Kandidatenwahl bei Prim.
Ändert sich der MST, wenn man bei Prim die Wurzel wechselt?: Bei nicht eindeutigen Gewichten kann es mehrere verschiedene Kantenmengen mit demselben Minimalgewicht geben. Dann können verschiedene Wurzeln (und eine andere Reihenfolge) verschiedene MST als Kantenmengen liefern, das Gesamtgewicht bleibt aber dasselbe — es wird mit Kruskal abgeglichen.
Was bedeutet die rote gestrichelte Linie im Kruskal-Modus?: Das ist die aktuelle Kante aus der sortierten Liste, die man nicht aufnehmen darf: beide Enden liegen schon in einer Union-Find-Komponente, das Hinzufügen würde einen Kreis schließen — der Algorithmus überspringt sie.

Machen Sie mit verwandten Themen in dieser Kategorie weiter — oder alle 48 in „Ingenieurwesen“.

Ganze Kategorie →

NeuSchule

Labyrinthe und A*

Simulation starten

Ideale Labyrinthe auf dem Gitter 40×28: rekursiver Rückverfolger, Wilson, Eller oder zufälliger Prim; Lösung mit A* (Manhattan, 4-Nachbarschaft). Wände nachzeichnen und Start sowie Ziel versetzen.

NeuSchule

A* und Dijkstra (Gitter)

Simulation starten

Gitter 40×28: A*, Dijkstra oder gierige Suche; Heuristiken, 4- und 8-Nachbarschaft, Wände und teure Zellen; Färbung der offenen und geschlossenen Menge.

NeuSchule

Endlicher Automat

Simulation starten

Moore-Automat für eine Ampel: Zyklus Grün–Gelb–Rot nach Zeitgeber oder manueller Schritt; Zustandsgraph.

NeuSchule

RRT-Pfadplaner (Gitter)

Simulation starten

Dieselbe Wandkarte 40×28: zufällige Proben, nächster Knoten, Schritt mit Kollisionsprüfung, Verschiebung der Stichprobe zum Ziel; Taste zum Vergleich mit A*.

NeuSchule

Inverse Kinematik eines Zweigelenkarms

Simulation starten

Ebener Arm aus zwei Gliedern: Ziel auf der Fläche, zwei Lösungen — Ellbogen oben und Ellbogen unten, Winkel θ₁ und θ₂.

NeuSchule

Balkenbiegung: Einheitslastverfahren

Simulation starten

Gelenkig gelagerter Euler-Bernoulli-Balken mit Kraft P und Streckenlast w: analytische Durchbiegung gegen das Integral der virtuellen Arbeit ∫Mm/EI dx.

Minimaler Spannbaum (Prim und Kruskal)

Zum Modell

So funktioniert es

Häufige Fragen

Ähnliche Simulationen

Labyrinthe und A*

A* und Dijkstra (Gitter)

Endlicher Automat

RRT-Pfadplaner (Gitter)

Inverse Kinematik eines Zweigelenkarms

Balkenbiegung: Einheitslastverfahren

Minimaler Spannbaum (Prim und Kruskal)

Zum Modell

So funktioniert es

Häufige Fragen