Algorithmus von Borůvka

Zweck und Grundidee

Der Algorithmus von Borůvka findet minimale Spannbäume in ungerichteten Graphen. Ein minimaler Spannbaum verbindet alle Knoten eines zusammenhängenden gewichteten Graphen mit Kanten minimalen Gesamtgewichts und ohne Zyklen. Der Algorithmus wurde 1926 von Otakar Borůvka beschrieben und gilt als erster Algorithmus für dieses Problem.

Er arbeitet in Runden: Für jeden Knoten wird eine leichteste ausgehende Kante gewählt. Diese Kanten werden in den Spannbaum aufgenommen; anschließend werden ihre Endknoten zu neuen Knoten zusammengezogen, also kontrahiert. Die Auswahl ist durch die Schnitteigenschaft minimaler Spannbäume begründet. Die Menge aller im Verlauf kontrahierten Kanten bildet den minimalen Spannbaum.

Ablauf und sequentielle Laufzeit

Zu Beginn ist die Spannbaum-Kantenmenge T leer. Solange mehr als ein Knoten vorhanden ist, wird eine Menge S gebildet: Für jeden Knoten v kommt seine leichteste inzidente Kante {u,v} in S. Danach werden alle Kanten aus S kontrahiert und S wird zu T hinzugefügt. Am Ende wird T zurückgegeben.

Bei einer geeigneten Implementierung benötigt eine Runde Zeit O(|E|), wobei |E| die Zahl der Kanten ist. In jeder Runde wird die Zahl der verbleibenden Komponenten mindestens halbiert. Daher beträgt die sequentielle Laufzeit O(|E| log |V|), wobei |V| die Zahl der Knoten ist.

Auswahl der Kanten im Parallelverfahren

Für die parallele Variante ist p die Anzahl der Prozessoren. Der Graph liegt als Adjazenzarray vor. Γ(v) bezeichnet die Nachbarmenge von v, |Γ(v)| ihre Größe und c(v,w) das Gewicht der Kante von v nach w. Jede ungerichtete Kante wird durch zwei entgegengesetzt gerichtete Kanten dargestellt.

Jedem Knoten v werden |Γ(v)|·p/(2|E|) Prozessoren zugeordnet. Diese suchen gemeinsam die Kante (v,w) mit minimalem Gewicht c(v,w) unter allen Nachbarn w in Γ(v). Die ursprüngliche Kante wird als Teil des Spannbaums ausgegeben, also die Kante vor allen Kontraktionen, und pred(v) wird auf w gesetzt. Eine parallele Präfixsumme ermöglicht die Prozessorzuordnung; die Minimumsreduktion zur Bestimmung von w benötigt O(|E|/p + log p) Zeit.

Pseudobäume und Sternbildung

Aus den Zeigern pred(v) entsteht der gerichtete Graph (V,{(v,pred(v)):v∈V}). Jeder Knoten hat Ausgangsgrad 1. Jede seiner Komponenten C enthält |C| Kanten und ist damit ein Baum mit genau einer zusätzlichen Kante. Sie besitzt genau einen 2-Kreis entlang einer ursprünglich leichtesten Kante (u,w); alle übrigen Kanten zeigen zu u oder w. Diese Struktur heißt Pseudobaum.

Die Pseudobäume werden in O(|V|/p) Zeit zu gewurzelten Bäumen gemacht. Beim 2-Kreis bricht ein Vergleich der Knotennummern die Symmetrie: Gilt v<w und pred(w)=v, wird pred(v)=v gesetzt. Danach zeigt v auf sich selbst und ist die Wurzel.

Durch wiederholtes Ersetzen pred(v)←pred(pred(v)) werden die gewurzelten Bäume in gewurzelte Sterne umgewandelt. Ein gewurzelter Stern hat Höhe 1: Alle Kanten zeigen direkt auf die eindeutige Wurzel. Dieser Schritt benötigt O((|V|/p) log |V|) Zeit.

Kontraktion und parallele Gesamtlaufzeit

Zur Kontraktion werden die Wurzeln der Sterne die neuen Knoten. Bei k Komponenten ist V'={1,…,k}; eine bijektive Abbildung f benennt die Sternwurzeln auf diese Zahlen um. Für jede alte Kante (u,v,c,e_old), deren Endpunkte zu verschiedenen Sternen gehören, entsteht die Kante (f(pred(u)),f(pred(v)),c,e_old) in E'. So entsteht G'=(V',E').

E' kann parallele Kanten enthalten; von diesen wird jeweils nur die leichteste benötigt. Anschließend muss G' wieder als Adjazenzarray dargestellt werden. Kontraktion und diese Umwandlung sind jeweils in erwarteter Zeit O(|E|/p + log p) möglich.

Damit beträgt die erwartete Laufzeit pro Runde O(|E|/p + log p). Über alle Runden ergibt sich insgesamt O((|E|/p) log |V| + log²|V|).