Der schnellste minimale Spannbaum-Algorithmus

Question

http://en.wikipedia.org/wiki/Minimum_spanning_tree

Ich möchte meinen Minimum-Spanning-Tree-Algorithmus mit den Besten der Besten vergleichen. Weiß jemand, wo ich eine C++-Implementierung dieser Algorithmen finden kann? Ich habe gegoogelt, aber nichts gefunden. Wenn diese Algorithmen die besten sind, muss es doch irgendwo eine C++-Implementierung geben?

Der schnellste minimale Spannbaum Algorithmus wurde bisher entwickelt von David Karger, Philip Klein und Robert Tarjan entwickelt, die einen zeitlinearen randomisierten Algorithmus basierend auf einer Kombination von Borvkas Algorithmus und dem Reverse-Delete-Algorithmus[2][3]. Der schnellste nicht-randomisierte Algorithmus, von Bernard Chazelle, basiert auf dem Soft Heap, einer approximativen Prioritäts Warteschlange.[4][5] Seine Laufzeit beträgt O(m [ ] Kanten, n die Anzahl der Scheitelpunkte und die klassische funktionale Umkehrung der Ackermann-Funktion ist. Die Funktion wächst extrem langsam, so dass dass sie für alle praktischen Zwecke als eine Konstante betrachtet werden kann, die nicht größer als als 4 angesehen werden kann; daher ist der Algorithmus von Chazelle benötigt also nahezu lineare Zeit. [ ] die Kantengewichte ganze Zahlen sind mit einer gebundener Bitlänge sind, dann sind deterministische Algorithmen mit linearer Laufzeit bekannt Laufzeit bekannt.[6] Ob es eine einen deterministischen Algorithmus mit linearer Laufzeit für allgemeine Gewichte gibt, ist noch eine offene Frage. Allerdings haben Seth Petie und Vijaya Ramachandran haben jedoch einen nachweislich optimalen deterministischen Minimum-Spanning-Tree-Algorithmus gefunden, der Komplexität des Algorithmus ist unbekannt ist.[7]

Ich teste bereits gegen die Graph-Algorithmen von Boost C++.

Answer 1

Wenn es auf der Wikipedia-Seite heißt "der schnellste minimale Spannbaum-Algorithmus", dann ist damit der Algorithmus mit den niedrigsten asymptotischen Grenzen gemeint - in diesem Fall O(m (m,n)), wobei m, n und definiert sind wie in dem von Ihnen eingefügten Zitat. Vereinfacht ausgedrückt bedeutet dies, dass für sehr große Eingabewerte die benötigte Zeit immer durch C*m*(m,n) für einen bestimmten Wert von C begrenzt ist. Beachten Sie jedoch, dass C sehr groß sein kann, d.h. dieser Algorithmus kann bei kleineren Eingabewerten langsamer sein als andere, obwohl er bei sehr großen Eingabewerten schneller ist als andere.

Wenn man die asymptotischen Schranken zweier Algorithmen vergleicht, muss man nicht "testen", welcher schneller ist - man beweist einfach die asymptotischen Schranken der beiden Algorithmen und sieht, welcher niedriger ist. ("Asymptotisch" bezieht sich auf das Verhalten, wenn die Eingabegröße gegen unendlich geht - und es ist schwierig, Tests mit unendlich großen Eingabewerten durchzuführen.)

Beachten Sie jedoch, dass es Fälle gibt, in denen Sie no den asymptotisch schnellsten Algorithmus verwenden. Wenn das "C" sehr groß ist, sollten Sie besser einen einfacheren Algorithmus für kleinere Datenwerte verwenden.

Ich vermute, dass Ihr Algorithmus zwar die C-, nicht aber die asymptotischen Schranken verbessert. Aber wenn ich damit falsch liege, sollten Sie ihn bei ACM einreichen!

Für weitere Informationen siehe: http://en.wikipedia.org/wiki/Big_O_notation

Answer 2

"Über Sortierung, Haufen und Minimum Spanning Trees", Gonzalo Navarro und Rodrigo Paredes

präsentiert einige der "Besten der Besten" bei Kernspeicher und externem Speichermessungen und gibt Hinweise auf ältere Implementierungen.

Sie melden die Anzahl der E/As und die CPU-Zeit in Abhängigkeit von Graphengröße, und beschreiben ihre Testfälle gut, so können Sie im Prinzip die Tests durchführen und mit ihren veröffentlichten Graphen vergleichen. Sie könnten ihre Prim2 Referenz (Code von Peter Sanders, der viele seiner seiner schnellen Codes frei zur Verfügung stellt), um die Ihre eigenen Messungen.