Tool guide

Minimaler Spannbaum: Prim und Kruskal im Vergleich

Das Panel Spannbaum beantwortet die Frage der günstigsten Verkabelung: jeden Knoten verbunden halten und das kleinstmögliche Gesamtgewicht der Kanten zahlen. Prim lässt einen Baum von einer Wurzel aus wachsen; Kruskal durchläuft Kanten in Gewichtsreihenfolge und verschmilzt Komponenten. Beide melden das Gesamtgewicht, die gewählten Kanten von der Kantenzahl des Graphen, die Anzahl der Komponenten und ob das Ergebnis ein Wald ist — diese letzte Zeile wechselt auf Ja, wenn der Eingabegraph unzusammenhängend ist. Der Graph stammt aus dem gemeinsamen Graph-Workbench.

Updated 4 sources4 min read