Diskussion:Algorithmus von Borůvka
Anzahl der Teilgerüste
BearbeitenMeiner Meinung nach verringert sich die Anzahl der Teilgerüste bei Hinzufügen einer Kante lediglich um 1, denn aus zwei Teilgerüsten wird eines (nicht aus jeweils zwei Teilgerüsten eines). Die Auswahl der beiden Teilgerüste ist nicht beliebig, sondern es muss tatsächlich die Kante mit dem geringsten Gewicht unter allen Kanten zwischen Teilgerüsten gewählt werden (wie auch beim Algorithmus von Kruskal), andernfalls wird möglicherweise nicht der minimale Spannbaum gefunden. -- Carsten Milkau 16:34, 2. Sep. 2008 (CEST)
Habe den Artikel geändert, um klarzustellen warum sich die Anzahl der Teilgerüste halbiert. -- Carsten Milkau (Diskussion) 18:27, 30. Aug. 2016 (CEST) Carsten Milkau (Diskussion) 18:27, 30. Aug. 2016 (CEST)
Komplexität und Sortieren
BearbeitenIm Artikel stand bisher, dass man die Kanten in O(|E| log |V|) sortieren "muss". Es ist überhaupt nicht klar, dass man das "muss". Außerdem ist O keine untere Schranke...
Tatsächlich kann man in jeder Iteration das Minimum der aus einer Komponente/Gerüst ausgehenden Kanten bestimmen (in Summe über den ganzen Graphen O(|E|)) und erreicht so (zugegebenermaßen) ebenfalls die O(|E| log |V|). Interessanterweise kann man aber durch Durchführen von nur O(loglog|V|) Borůvka-Phasen und anschließender Ausführung des Prim-Algorithmus (mit Fibonacci-Heaps) auf dem so kontrahierten Graphen eine Gesamtlaufzeit von O(|E| loglog|V|) erreichen. Dann ist das "Vorab-Sortieren" definitiv nicht optimal! (Bereits zehn Jahre vor Entdeckung der Fibonacci-Heaps hatte Andrew Yao 1974 gezeigt, dass loglog möglich ist durch eine Abwandlung von "Sollins" (Borůvkas) Algorithmus.)
Ich werde den Artikel dementsprechend ändern. Dieser Eintrag soll als Erklärung für den Edit dienen, wenn Fragen aufkommen.