External Memory Minimaler Spannbaum

Ein externer minimaler Spannbaum bezeichnet in der Informatik einen minimalen Spannbaum, der für einen in den Sekundärspeicher ausgelagerten Graphen berechnet wurde. Letzteres ist für Graphen nötig, deren Anzahl Knoten und Kanten zu groß ist, als das sie gleichzeitig vollständig in den Hauptspeicher passen.

Als Berechnungsmodell zieht man das External Memory Modell heran. Es besteht aus Haupt-und Sekundärspeicher, wobei ersterer eine Kapazität von $M$ hat und Datenblöcke der Größe $B$ zwischen ersterem und letzterem hin- und hergeschoben werden können. Das Lesen/Schreiben eines Blocks in vom (in den) Sekundärspeicher in den (vom) Hauptspeicher, bezeichnet man als I/O (= Input/Output).

Semiexterne Berechnung

Eine Einschränkung zur Definition aus der Einleitung, bilden semiexterne Algorithmen zur Berechnung minimaler Spannbäume. Jene Algorithmen verarbeiten ungerichtete Graphen $G=(V,E)$, von denen nur die Knoten in den Hauptspeicher passen. Formal ist das durch die Beziehung

$M=c\cdot |V|<|E|$
gegeben, wobei $c$ eine Konstante ist.

Der Algorithmus von Kruskal lässt sich leicht als semiexterne Variante umsetzen. Dazu muss man die Kanten zunächst nach aufsteigendem Gewicht extern sortieren, was sich mithilfe von $sort(|E|):=\Theta ({\frac {|E|}{B}}\cdot \log _{\frac {M}{B}}({\frac {|E|}{B}}))$(die Sortierschranke) I/Os realisieren lässt. Die Union-Find-Struktur lässt sich vollständig im Hauptspeicher verwalten, wodurch sich insgesamt $O(sort(|E|))$ I/Os ergeben.

Externe Berechnung

Falls die Knotenmenge ebenfalls zu groß für den Hauptspeicher ist, so lässt sich ein minimaler Spannbaum durch externe Algorithmen berechnen.

Algorithmus von Prim

Ein bekannter Vertreter ist der Algorithmus von Prim, den man für gewöhnlich im Hauptspeicher ausführt. Man kann ihn durch eine kleine Modifikation extern ausführen, wozu es einer externen Prioritätswarteschlange bedarf. Diese speichert die Kanten des Graphen, wobei als Priorität deren Gewichte genommen werden. Der Algorithmus wählt iterativ die Kante geringsten Gewichts aus, was durch eine extractMin()-Operation der Warteschlange bewerkstelligt wird. Den Ablauf kann man einfach in Pseudocode gießen (es ist zu beachten, dass die gerichteten Kanten von $G$ betrachtet werden):

G = (V,E): Graph
c: Gewichtsfunktion der Kanten
s $\in$ V(G): Startknoten
Adj: adjazenten Knoten eines Knoten
Inc: inzidente Kanten eines Knoten 

external_prim(G,c,s):
01  T $\leftarrow (\emptyset ,\emptyset )$ // T = (V,E): Knoten und Kanten des zu berechnenden MST
02  Q $\leftarrow$ leere externe Prioritätswarteschlange
03  für alle e $\in$ Adj(s)
04      Q.insert(e, c(e))
05  solange Q nicht leer
06      (u,v) $\leftarrow$Q.extractMin()
07      wenn v nicht Teil von T
08          V(T) $\leftarrow$ V(T) $\cup${v}
09          E(T) $\leftarrow$ E(T) $\cup${(u,v)}
10          für alle e $\in$ Inc(v) \ {(v,u)} // denn (u,v) ist schon aufgenommen worden
11              Q.insert(e, c(e))        
12  return T

Hier ist die wichtige Annahme, wodurch die I/O-Effizienz zustande kommt, dass die Kantengewichte paarweise verschieden sind. Damit kann man die Überprüfung in Zeile 7, ob der v Knoten bereits im Spannbaum enthalten ist, leicht realisieren. Man muss dazu lediglich überprüfen, ob die nächste Kante minimalen Gewichts gleich (u,v) (aus Zeile 6) ist, was nur eine zusätzliche extractMin()-Operation der Warteschlange Q erfordert. Denn jeder Knoten fügt seine inzidenten Kanten in Q ein und falls v schon Teil des Spannbaums sind, so befindet sich die Kante (v,u) ebenfalls in Q. Darin muss diese Kante aber der unmittelbare Nachfolger von (u,v) sein, da nach Annahme keine zwei Kanten das selbe Gewicht haben.

Die gesamte I/O-Komplexität beträgt $O(sort(|E|)+|V|)$. Zunächst wird für jeden Knoten dessen adjazente Knoten ausgelesen, was bei Umsetzung per Adjazenzliste $O(|V|+|E|/B)$ I/Os erfordert (der zweite Summand ist die Scanschranke $scan(|E|):=\Theta ({\frac {|E|}{B}})$ I/Os ). Der Algorithmus verarbeitet alle Kanten von $G$ und führt pro Kante höchstens zwei Operationen der Warteschlange aus. Wenn man davon ausgeht, dass die Warteschlange $n$ Operationen mit$O(sort(n))$ I/Os unterstützt, dann lässt sich die Gesamtkomplexität mit $O(|V|+sort(|E|))$ I/Os bemessen.

Kantenreduktion

Ein anderer Ansatz ist es, iterativ Kanten des minimalen Spannbaumes zu identifizieren, sodass man diese entfernen kann. Das führt man solange fort, bis der resultierende Graph ausreichend dicht ist. Ist der Graph ausreichend dicht, so fällt die Komplexität für das Berechnen des minimalen Spannbaumes auf dem verbleibenden Graphen insgesamt nicht mehr ins Gewicht .

Beispiel einer Kantenkontraktion: die Kante $\{1,2\}$wurde kontrahiert. Die neue Kante $\{1,3\}$war vorher $\{2,3\}$.

Konkret will man die Anzahl Knoten auf mindestens ${\frac {|E|}{B}}$ reduzieren, um dann auf dem resultierenden Graphen den Algorithmus von Prim laufen zu lassen, wodurch sich die Komplexität von letzterem zu $O(sort(|E|)$ I/Os vereinfacht.

Die Reduktion entstammt dem Algorithmus von Borůvka, weswegen der folgende Ablauf auch Boruvka-Phase genannt wird: für jeden Knoten wählt man die leichteste adjazente Kante aus, welche Teil des minimalen Spannbaums sein muss. Anschließend kontrahiert man jede solche Kante, sodass sich die Anzahl Knoten mindestens halbiert. Bei der Kontraktion können neue Kanten entstehen, sodass man für diese Verweise auf dessen ursprüngliche Kante speichern muss. Letzteres ist nötig, um am Ende einen minimalen Spannbaum für den ursprünglichen Graphen konstruieren zu können.

Insgesamt sind dafür $\lceil \log _{2}({\frac {|V|\cdot B}{|E|}})\rceil$ Phasen nötig. Eine einzelne Phase lässt sich mit $O(sort(|E|))$ I/Os implementieren, sodass sich insgesamt $O(sort(|E|))\cdot \max {\{1,\log _{2}({\frac {|V|\cdot B}{|E|}})\}}$ I/Os ergeben . Das Maximum findet sich in der Komplexität wieder, weil mindestens eine Sortierphase nötig ist.

Randomisiert

Anstatt den deterministischen Verfahren kann man die Berechnung auch randomisiert durchführen. Im Folgenden wird ein solcher Algorithmus von Dementiev et al. beschrieben.

Die Idee ist es die Anzahl Knoten solange zu reduzieren, bis man auf dem verbleibenden Graphen einen semiexternen Algorithmus ausführen kann. Die Reduktion wird auch durch Kantenkontraktion, wie oben beschrieben, umgesetzt. Dabei wird iterativ ein zufälliger Knoten ausgewählt und nur dessen leichteste Kante kontrahiert, nachdem sie in den minimalen Spannbaum aufgenommen wurde.

Literatur

• Otakar Borůvka: O jistém problému minimálním. S.37-58, ([1]).
• Alok Aggarwal, Jeffrey Vitter: The Input/Output Complexity of Sorting and Related Problems., ACM, New York 1988, S.1116-1127 ([2]).
• Autor: Titel. Verlag, Ort Jahr, ISBN.
• Autor: Titel. Verlag, Ort Jahr, ISBN, S. X–Y.
• Herausgeber (Hrsg.): Titel (= Reihe. Band). x. Auflage. Verlag, Ort Jahr, ISBN.
• Autor: Titel. In: Herausgeber (Hrsg.): Sammelwerk (= Reihe. Band). Verlag, Ort Jahr, ISBN, S. X–Y ([http:// online]).
• Autor X, Autor Y: Titel. Untertitel. In: Zeitschrift. Band/Jahrgang, Nr. X, Jahr, ISSN 0000-0000, S. X–Y ([http:// PDF; 1,1 MB]).
• Autor: Titel. Herausgegeben von Herausgeber. Verlag, Ort Jahr, ISBN.