Borůvka's Algorithmus ist ein Algorithmus, für einen minimalen Überspannen-Baum in einem Graphen zu finden, für den alle Rand-Gewichte verschieden sind.

Es wurde zuerst 1926 von Otakar Borůvka als eine Methode veröffentlicht, ein effizientes Elektrizitätsnetz für Mähren zu bauen.

Der Algorithmus wurde von Choquet 1938 wieder entdeckt; wieder durch Florek, Łukasiewicz, Perkal, Steinhaus und Zubrzycki 1951; und wieder durch Sollin

1965. Weil Sollin der einzige Computerwissenschaftler in dieser Liste war, die in einem englischen Sprechen-Land lebt, wird dieser Algorithmus oft den Algorithmus von Sollin besonders in der parallelen Rechenliteratur genannt.

Der Algorithmus beginnt durch das erste Überprüfen jedes Scheitelpunkts und Hinzufügen des preiswertesten Randes von diesem Scheitelpunkt bis einen anderen im Graphen ohne Rücksicht auf bereits zusätzliche Ränder und setzt fort, sich diesen Gruppierungen bei einer ähnlichen Weise anzuschließen, bis ein Baum, der alle Scheitelpunkte abmisst, vollendet wird.

Pseudocode

Wenn er

jeden Scheitelpunkt oder Satz von verbundenen Scheitelpunkten ein "Bestandteil" benennt, ist der Pseudocode für den Borůvka's Algorithmus:

1 Beginnen mit einem verbundenen Graphen G, Ränder von verschiedenen Gewichten und einen leeren Satz von Rändern T enthaltend

2, Während die Scheitelpunkte von durch T verbundenem G zusammenhanglos sind:

3 Beginnen mit einem leeren Satz von Rändern E

4 Für jeden Bestandteil:

5 Beginnen mit einem leeren Satz von Rändern S

6 Für jeden Scheitelpunkt im Bestandteil:

7 Fügen den preiswertesten Rand vom Scheitelpunkt im Bestandteil zu einem anderen Scheitelpunkt in einem zusammenhanglosen Bestandteil zu S Hinzu

8 Fügen den preiswertesten Rand in S zu E Hinzu

9 Fügen den resultierenden Satz von Rändern E zu T Hinzu.

10 ist Der resultierende Satz von Rändern T der minimale Überspannen-Baum von G.

Wie man

zeigen kann, nimmt Borůvka's Algorithmus O (loggen Sie V) Wiederholungen der Außenschleife, bis es endet, und deshalb rechtzeitig O (Elog V) zu laufen, wo E die Zahl von Rändern, und V ist, sind die Zahl von Scheitelpunkten in G. In planaren Graphen, und mehr allgemein in Familien von Graphen hat unter dem Graphen geringe Operationen geschlossen, es kann gemacht werden, in der geradlinigen Zeit, durch das Entfernen von allen außer dem preiswertesten Rand zwischen jedem Paar von Bestandteilen nach jeder Bühne des Algorithmus zu laufen.

Andere Algorithmen für dieses Problem schließen den Algorithmus von Prim (wirklich entdeckt durch Vojtěch Jarník) und den Algorithmus von Kruskal ein. Schnellere Algorithmen können durch das Kombinieren des Algorithmus von Prim mit Borůvka's erhalten werden. Ein schnellerer randomized minimaler Überspannen-Baumalgorithmus gestützt teilweise auf dem Borůvka's Algorithmus wegen Kargers, Kleins und Tarjans läuft in der erwarteten Zeit. Der am besten bekannte (deterministische) minimale Überspannen-Baumalgorithmus durch Bernard Chazelle basiert auch teilweise auf Borůvka's und führt in O (E α (V)) Zeit, wo α das Gegenteil der Funktion von Ackermann ist. Diese randomized und deterministische Algorithmen verbinden Schritte des Borůvka's Algorithmus, die Anzahl von Bestandteilen vermindernd, die mit Schritten eines verschiedenen Typs verbunden werden müssen, die die Anzahl von Rändern zwischen Paaren von Bestandteilen vermindern.

Referenzen