Algorithmus von Borůvka

Animation

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|)$.

 $T\gets \emptyset$
 solange $|V|>0$
   $S\gets \emptyset$
   für alle $v\in V$
     $S\gets S$ $\cup$ leichteste Kante $\{u,v\}\in E$
   für alle $\{u,v\}\in S$
     kontrahiere $\{u,v\}$
   $T\gets T\cup S$
 return $T$

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.

 für alle $v\in V$ parallel
   ordne $|\Gamma (v)|{\tfrac {p}{2|E|}}$ Prozessoren Knoten $v$ zu
   wähle $(v,w)$ mit minimalem Gewicht $c(v,w)$ in $\Gamma (v)$
   gib originale Kante $(v,w)$ als Teil des Spannbaums aus (Kante vor allen Kontraktionen)
   setze $pred(v)\gets w$

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.

 für alle $v\in V$ parallel
   $w\gets pred(v)$
   falls $v<w$ und $pred(w)=v$
     $pred(v)\gets v$

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.

 solange $\exists v\in V:pred(pred(v))\neq pred(v)$
   für alle $v\in V$ parallel
     $pred(v)\gets pred(pred(v))$

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)$.

 $k\gets$ Anzahl der Komponenten (Sterne)
 $V'\gets \{1,\ldots ,k\}$
 wähle eine bijektive Abbildung $f:\{{\text{Sternwurzeln}}\}\to \{1,\ldots ,k\}$
 $E'\gets \{(f(pred(u)),f(pred(v)),c,e_{\text{old}}):(u,v,c,e_{\text{old}})\in E\land pred(u)\neq pred(v)\}$

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)$.

Literatur

• Borůvka, Otakar (1926). "O jistém problému minimálním (About a certain minimal problem)". Práce mor. přírodověd. spol. v Brně III (in Czech, German summary) 3: 37–58.
• Borůvka, Otakar (1926). "Příspěvek k řešení otázky ekonomické stavby elektrovodních sítí (Contribution to the solution of a problem of economical construction of electrical networks)". Elektronický Obzor (in Czech) 15: 153–154.
• Nešetřil, Jaroslav; Milková, Eva; Nešetřilová, Helena (2001). "Otakar Borůvka on minimum spanning tree problem: translation of both the 1926 papers, comments, history". Discrete Mathematics 233 (1–3): 3–36. doi:10.1016/S0012-365X(00)00224-7.
• Choquet, Gustave (1938). "Étude de certains réseaux de routes". Comptes-rendus de l’Académie des Sciences (in French) 206: 310–313.
• Florek, Kazimierz (1951). "Sur la liaison et la division des points d'un ensemble fini". Colloquium Mathematicum 2 (1951) (in French): 282–285.
• Sollin, M. (1965). "Le tracé de canalisation". Programming, Games, and Transportation Networks (in French).
• Eppstein, David (1999). "Spanning trees and spanners". In Sack, J.-R.; Urrutia, J. Handbook of Computational Geometry. Elsevier. pp. 425–461.
• Mareš, Martin (2004). "Two linear time algorithms for MST on minor closed graph classes". Archivum mathematicum 40 (3): 315–320.