How it works?

Behalten Sie einen booleschen Wert inTree für jeden Knoten bei. Beginnen Sie mit nur Knoten 0 im Baum. Die Grenze ist jede Kante mit genau einem Endpunkt innerhalb des Baums, genannt eine Schnittkante (crossing edge).

Schritt-für-Schritt-Prozess:

1. Wählen Sie unter allen Schnittkanten diejenige mit dem kleinsten Gewicht aus.
2. Fügen Sie den äußeren Endpunkt dem Baum hinzu und addieren Sie sein Gewicht zur Gesamtsumme.
3. Wiederholen Sie dies, bis der Baum alle n Knoten enthält (das benötigt n - 1 Kanten).

Wenn zu irgendeinem Zeitpunkt keine Schnittkante existiert, aber noch Knoten außerhalb verbleiben, ist der Graph nicht zusammenhängend.

Beispiel mit Kanten [0,1,1, 1,2,2, 2,3,3, 0,3,4]: von 0 nehmen Sie 0-1(1), dann 1-2(2), dann 2-3(3); Gesamtsumme 6.