• Guten Start ins Wintersemester 2024/2025

Algorithmus von Boruvka

Unser Sponsor SAP 4 Students
Unser Sponsor
nachdem ich die Algorithmen von Kruskal und Prim mittlerweile ganz gut verstanden habe, hänge ich am Boruvka fest, weil ich dazu recht wenig Erklärungen gefunden habe 🙁...
Kann mir hier jemand erklären, wie die Teilbäume auf S. 135 in KE3 unten links gebildet werden? Oder einfach mit eigenen Worten kurz den Algorithmus beschreiben?
 
Dr Franke Ghostwriter
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.
 
Oben