Minimaler Spannbaum
Kostengünstige Verbindungen mit Kruskal finden und Union–Find-Entscheidungen nachvollziehen.
Über dieses Tool
Knoten ohne Zyklen mit möglichst kleinem Gesamtgewicht verbinden. Pro Zeile eine ungerichtete Kante: A B 4. A allein ergänzt einen isolierten Knoten. Leerzeilen und mit # beginnende Zeilen werden ignoriert. IDs: 1–24 ASCII-Buchstaben, Ziffern, Unterstriche, Punkte oder Bindestriche. Gewichte mit Dezimalpunkt und optionalem Exponenten; negative Werte und Null sind erlaubt. Grenzen: 24 Knoten, 80 verschiedene Kanten, 12.000 Zeichen, Gewichte von −1e9 bis 1e9. A B 4 und B A 4 zählen einmal; unterschiedliche Gewichte zwischen denselben Knoten bleiben parallele Kanten.
Berechnen liefert sofort das Ergebnis, Schritt untersucht eine Kante. Optionale Animation mit 0–2000 ms, anfangs 350. Pause/Fortsetzen behält den Lauf; Berechnen kann ihn abschließen. Zurücksetzen oder geänderte Eingaben verwerfen den Lauf. Graph- und Verzögerungsentwürfe bleiben lokal gespeichert, auch unfertige oder ungültige Eingaben. Reload stellt sie ohne Berechnung wieder her; der Fortschritt wird nicht gespeichert.
Kruskal untersucht Kanten nach aufsteigendem Gewicht. Union–Find nimmt eine Kante nur auf, wenn ihre Endpunkte zu verschiedenen Komponenten gehören; andernfalls entstünde ein Zyklus. Vereinigung nach Rang und Pfadhalbierung beschleunigen die Gruppensuche. Bei gleichem Gewicht entscheiden die sortierten, groß-/kleinschreibungssensitiven Knoten-IDs. Andere minimale Bäume können ebenso gültig sein. Sortieren kostet O(E log E), Union–Find amortisiert nahezu konstant. Für die Lehransicht werden alle Kanten untersucht, auch nach Fertigstellung des Baums.
Das ursprüngliche Netzwerk hat Gesamtgewicht 13: B–C 1, B–D 2, E–F 2, A–C 3, C–E 5. Bei getrennten Eingaben entsteht je Komponente ein minimaler Baum, einschließlich isolierter Knoten: ein minimaler Spannwald. Kein Kürzeste-Wege- oder Routenplaner. Selbstkanten werden immer verworfen. Geometrische Kantenlänge und Gewicht sind unabhängig.
Sechs Knotenfarben unterstützen die Gruppenerkennung und wiederholen sich bei mehr Komponenten; genaue Mitglieder stehen in der Tabelle. Gewählte Kanten sind grün, verworfene rot gestrichelt, die aktuelle Kante dicker. Tabellen zeigen gewählte Kanten, genaue Gruppenmitglieder und untersuchte Entscheidungen. Lange IDs verwenden Tabellennummern im Graphen; über 16 Knoten scrollt er lokal. Dichte Kanten können sich überlagern. Gleitkommaarithmetik; angezeigte Gewichte haben höchstens 12 signifikante Stellen.