Diskussion:Algorithmensammlung: Graphentheorie: Algorithmus von Kruskal

Interation

Die While Schleife iteriert über die Knoten. In einem Graphen können je nach Größe wesentlich mehr Kanten als Knoten vorhanden sein und man kann durchaus auch Graphen kreieren, die in diesem Fall zwei voneinander getrennte MSTs ausspucken würden.

Desweiteren machen die Zuweisungen nicht viel Sinn. filter() überschreibt nach jeder Iteration die Variablen, sodass eine Zuweisung in der Entscheidung keine Auswirkungen hat.

Desweiteren wird die abgearbeitete Kante einfach auf den Rückgabearray gepusht. Das sind zwar dann die Kürzesten, die allerdings ebenfalls nicht zusammenhängend sein müssen.

Ein Beispiel: Zwei Bereiche aus je 7 Knoten, die in ihren Bereichen alle untereinander mit Kanten verbunden sind, deren Gewicht < 10 ist. Eine Kante verbindet die "Bereiche" mit Wertigkeit 20 miteinander. Somit wären nach 14 Iterationen nur zwei einzelne Teilgraphen, allerdings kein MST entstanden.

--- Ich habe meiner Meinung nach die beschriebenen Fehler behoben. Es sollten jetzt immer korrekte minimale Spannbäume erzeugt werden. 141.30.123.16 09:14, 7. Nov. 2014 (CET)