Algorithmus von Boruvka

Der EIntrag ist schon recht alt. Aber falls mal einer hier suchen sollte:

1. Für jeden einzelnen Knoten die Kante mit dem geringsten Gewicht wählen.
2. Es entstehen Zusammenhangskomponenten -> kann ja sein, dass zwei Knoten die gleiche kleinste Kante haben, dann sind sie quasi von der Außenwelt abgeschlossen.
3. Die einzelnen Zusammenhangskomponenten über die gebliebenen Kanten mit dem geringsten Gewicht so verbinden, dass es KEINE Kreise gibt.