Prim oder Kruskal ausführen 01 Einen gewichteten Graphen bauen. Probieren Sie das Grid-Preset (rows 4, cols 5 — 20 Knoten, 31 Einheitskanten), einen Random-verbundenen Graphen oder Complete K₆. 02 Prim wählen und Source setzen , oder zu Kruskal wechseln, das keine Quelle braucht. 03 Die Tabelle lesen. Zuerst das Gesamtgewicht, dann gewählte Kanten, Komponenten und Ist-Wald; darunter steht eine Zeile pro gewählter Kante mit ihrem Gewicht. 04 Den anderen Algorithmus gegenprüfen — beide müssen sich beim Gesamtgewicht für denselben Graphen einig sein. 05 Den Lauf schrittweise verfolgen mit Play / Prev / Next; Prim hebt das wachsende Frontgebiet hervor, Kruskal die akzeptierten und abgelehnten Kanten.
Rechenbeispiele Werte wie vom Panel angezeigt:
Graph · Algorithmus
Anzeige
Grid 4 × 5, Prim von 1-1
Gesamtgewicht 19 ; gewählte Kanten 19 / 31 ; Komponenten 1 ; Ist Wald No
Grid 4 × 5, Kruskal
Gesamtgewicht 19 ; gewählte Kanten 19 / 31
Random verbunden (n 6, p 0.3, seed 20260730, max weight 9), Prim von A
Gesamtgewicht 16 ; gewählt A–B(3), A–C(4), C–E(2), A–D(6), D–F(1) ; gewählte Kanten 5 / 7
Derselbe Graph, Kruskal
Gesamtgewicht 16 ; dieselben fünf Kanten in Gewichtsreihenfolge: D–F(1), C–E(2), A–B(3), A–C(4), A–D(6)
Complete K₆, Prim
Gesamtgewicht 5 ; gewählte Kanten 5 / 15 ; Kanten A–B(1), A–F(1), A–E(1), A–D(1), A–C(1)
Der Grid-MST besteht aus 19 Einheitskanten für 20 Knoten — das theoretische Minimum — und beide Algorithmen erreichen es. Im Zufallsgraphen genügt eine Kante, um die Antwort von Hand zu prüfen: D–F wiegt 1 , das leichteste im Graphen, also muss jeder MST sie enthalten, und beide Läufe tun das.
Warum die beiden Listen abweichen Prim und Kruskal wählen Kanten in unterschiedlicher Reihenfolge und können bei Gleichständen verschiedene gültige Bäume wählen. Kruskal sortiert alle Kanten global, daher beginnt seine Tabelle mit der leichtesten Kante irgendwo; Prim betrachtet nur das Frontgebiet eines wachsenden Baums, daher beginnt seine Tabelle mit dem, was zuerst die Wurzel verlässt. Im Zufallsgraphen erzeugen beide dieselbe Menge — der minimale Spannbaum dort ist eindeutig —, aber die K₆-Liste (alle Gewichte 1) ist nur einer von vielen perfekten Bäumen: Vergleichen Sie bei wiederholten Gewichten das Gesamtgewicht und die Kantenzahl, nicht die Kantenlisten.
Grenzen
Ein unzusammenhängender Graph ergibt einen Wald. Die Zeile Ist-Wald wechselt auf Ja und die Komponentenzahl bleibt über 1; die Antwort ist dann ein minimaler Spannwald, ein Baum pro Komponente, kein einzelner Baum.
Nur ungerichtete Kanten. Prim behandelt einen gerichteten Graphen als ungerichtet und sagt das in einer Warnung; auch Kruskals Komponentenverschmelzung ist eine ungerichtete Idee. Keiner der Algorithmen löst die gerichtete minimale Arboreszenz. Was es nicht tut. Es berechnet keine kürzesten Wege von einer Wurzel, zählt keine alternativen Spannbäume und importiert keine Kantenliste aus einer Datei — nutzen Sie kürzeste Wege für Wurzelabstände, Kennzahlen & Zentralität für Strukturzahlen oder fügen Sie die Matrix in den Graph-Workbench ein bzw. senden Sie sie an die Matrix-Werkzeuge .
Die Tie-Break-Falle Bei Complete K₆ wiegt jede Kante 1 , also wiegt jeder Spannbaum 5 ; Prim antwortet zufällig mit einem Stern um A: A–B, A–F, A–E, A–D, A–C . Lesen Sie diese Liste als einen minimalen Baum, nicht als den minimalen Baum. Dieselbe Vorsicht gilt für gleichgewichtige Grids: Die Grid-Antwort 19 ist stabil, aber welche 19 Einheitskanten erscheinen, kann sich zwischen Prim und Kruskal unterscheiden, während beide korrekt bleiben.
Wobei es nützlich ist Eine Behauptung zur günstigsten Verkabelung prüfen Im Zufallsgraphen sind die beiden schwersten Kanten, E–F(8) und B–D(7) , beide ausgeschlossen, während A–D(6) akzeptiert wird. Prüfen Sie ein vorgeschlagenes Netz genauso: Wenn es E–F(8) bezahlt und die günstigere D–F(1) auslässt, ist es nicht minimal.
Die Schnitteigenschaft lehren Das Grid macht die Schnittbegründung sichtbar: Jede Einheitskante kreuzt einen Schnitt mit Gewicht 1, und beide Algorithmen akzeptieren 19 der 31 ohne einen einzigen Zyklus. Wechseln Sie zum Random-verbundenen Graphen und führen Sie beide aus; die Schritt-Wiedergabe zeigt, wie Kruskal E–F(8) überspringt, weil seine Endpunkte bereits verbunden sind.
Datenschutz Graphbearbeitung und beide MST-Läufe werden lokal in Ihrem Browser ausgeführt; nichts wird hochgeladen.
Referenzen
Wikipedia, Prim's algorithm , en.wikipedia.org (访问日期:2026-10-07)— Frontgebiet-Wachstum von einer Wurzel.
Wikipedia, Kruskal's algorithm , en.wikipedia.org (访问日期:2026-10-07)— Gewichtsreihenfolge mit Union-Find.
Wikipedia, Minimum spanning tree , en.wikipedia.org (访问日期:2026-10-07)— Schnitt- und Zykluseigenschaften, Eindeutigkeit bei verschiedenen Gewichten.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms , 4. Aufl., MIT Press, 2022, mitpress.mit.edu (访问日期:2026-10-07)— MST-Algorithmen und die Schnitteigenschaft.
Calculators in this hub
Hand-picked tools, one click away. The mini versions compute live and carry your values into the full calculator.
Sources & review
Updated 2026-10-07