Algorithmus von Borůvka
# Algorithmus von Borůvka

Der Algorithmus von Borůvka gilt als erster Algorithmus zum Auffinden minimaler Spannbäume in ungerichteten Graphen. Er wurde 1926 von dem tschechischen Mathematiker Otakar Borůvka beschrieben. Die beiden bekannteren Algorithmen zur Lösung dieses Problems sind der Algorithmus von Prim und der Algorithmus von Kruskal. In der Erstveröffentlichung dieser beiden Algorithmen wird Borůvka jeweils erwähnt.

## Grundprinzip und Komplexität

Der Algorithmus von Borůvka nutzt die Schnitteigenschaft minimaler Spannbäume. In jeder Runde wird die leichteste ausgehende Kante jedes Knoten ausgewählt und der Graph entlang dieser Kanten kontrahiert. Die beiden zu einer kontrahierten Kante inzidenten Knoten verschmelzen dabei zu einem Knoten. Der minimale Spannbaum besteht aus genau den kontrahierten Kanten. Bei geschickter Implementierung benötigt jede Runde Zeit in $O(|E|)$. Da die Anzahl der verbleibenden Komponenten in jeder Runde mindestens halbiert wird, ergibt sich eine sequentielle Laufzeit in $O(|E|\log |V|)$.

## Parallele Implementierung

Im Folgenden sei $p$ die Anzahl der Prozessoren. Der Algorithmus nutzt die Repräsentation des Graphen durch ein Adjazenzarray. Dabei sei $\Gamma (v)$ die Menge der Nachbarn von $v$ und entsprechend $|\Gamma (v)|$ deren Anzahl. Mit $c(v,w)$ wird das Gewicht der Kante von $v$ nach $w$ bezeichnet. Jede ungerichtete Kante wird durch zwei gegenteilig gerichtete Kanten dargestellt.

Für jeden Knoten sucht eine Teilmenge der Prozessoren parallel nach der leichtesten ausgehenden Kante.

Die Zuordnung der Prozessoren kann dabei mithilfe einer parallelen Präfixsumme geschehen, sodass $|\Gamma (v)|$ in konstanter Zeit berechnet werden kann. Das $w$ lässt sich dann durch eine Minimumsreduktion zwischen den beteiligten Prozessoren bestimmen. Diese kann in Zeit $O\left({\tfrac {|E|}{p}}+\log p\right)$ durchgeführt werden.

Betrachte nun den gerichteten Graphen $(V,\{(v,pred(v)):v\in V\})$. Der Graph hat Ausgangsgrad $1$. In jeder Komponente $C$ dieses Graphen gibt es also $|C|$ Kanten und damit handelt es sich um einen Baum mit genau einer zusätzlichen Kante. Außerdem gibt es genau einen $2$-Kreis entlang der ursprünglich leichtesten Kante $(u,w)$ und alle weiteren Kanten in $C$ sind zu $u$ oder $w$ hin gerichtet. Wir bezeichnen diese Struktur als Pseudobaum. In Zeit $O\left({\tfrac {|V|}{p}}\right)$ lassen sich alle Pseudobäume in gewurzelte Bäume umwandeln, also Bäume mit einer eindeutigen Wurzel auf die alle Kanten hinzulaufen. Dabei wird ein Vergleich der Knoten-Nummern ($v<w$) zur Brechung der Symmetrie der parallelen Kanten genutzt.

In einem weiteren Schritt mit Laufzeit $O\left({\tfrac {|V|}{p}}~\log |V|\right)$ können diese gewurzelten Bäume dann in gewurzelte Sterne umgewandelt werden. Dies sind spezielle Bäume der Höhe $1$, das heißt alle Kanten zeigen direkt auf die eindeutige Wurzel.

Die gewurzelten Sterne können nun kontrahiert werden, indem deren Wurzeln die neue Knotenmenge bilden. Dies benötigt Zeit in $O\left({\tfrac {|E|}{p}}+\log p\right)$.

Man erhält einen Graphen $G'=(V',E')$. Die Knoten von $G'$ sind dabei genau die Sternwurzeln, die von der bijektiven Abbildung $f$ in $\{1,\ldots ,k\}$ umbenannt wurden. Dabei enthält $E'$ eventuell parallele Kanten, von denen nur noch jeweils die leichteste benötigt wird. Der Graph $G'$ muss jetzt für den Rekursionsschritt noch in Adjazenzarrayrepräsentation gebracht werden. Dies kann in erwarteter Zeit $O\left({\tfrac {|E|}{p}}+\log p\right)$ erfolgen.

Zusammengefasst ergibt sich eine erwartete Gesamtlaufzeit von $O\left({\tfrac {|E|}{p}}+\log p\right)$ pro Runde und damit von insgesamt $O\left({\tfrac {|E|}{p}}\log |V|+\log ^{2}|V|\right)$.

