Algorithmus von Prim

Der Algorithmus von Prim kann mithilfe einer externen Prioritätswarteschlange als externer Algorithmus ausgeführt werden. Sie speichert die Kanten des Graphen, wobei als Priorität deren Gewichte genommen werden. Der Algorithmus wählt iterativ die Kante geringsten Gewichts aus und fügt sie zum bisherigen minimalen Spannbaum hinzu. Die leichteste Kante erhält man durch eine extractMin()-Operation der Warteschlange. Im Folgenden ist der Algorithmus in Pseudocode beschrieben (es ist zu beachten, dass die gerichteten Kanten von ${\displaystyle G}$ betrachtet werden).

c: Gewichtsfunktion der Kanten
s ${\displaystyle \in }$ V(G): beliebiger Startknoten
Adj: adjazenten Knoten eines Knoten
Inc: inzidente Kanten eines Knoten

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

Es wird angenommen, dass die Kantengewichte paarweise verschieden sind. So 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 dasselbe Gewicht haben.

Die gesamte I/O-Komplexität umfasst ${\displaystyle {\mathcal {O}}(|V|+\operatorname {sort} (|E|))}$ I/Os. Zunächst werden für jeden Knoten dessen adjazente Knoten ausgelesen, was bei Umsetzung per Adjazenzliste

${\displaystyle {\mathcal {O}}\left(|V|+{\frac {|E|}{B}}\right)}$ I/Os

erfordert. Der Algorithmus verarbeitet weiterhin alle Kanten von ${\displaystyle G}$ und führt pro Kante höchstens zwei Operationen der Warteschlange aus. Wenn man davon ausgeht, dass die Warteschlange ${\displaystyle n}$ Operationen mit ${\displaystyle {\mathcal {O}}(\operatorname {sort} (n))}$ I/Os unterstützt, dann beträgt die Gesamtkomplexität ${\displaystyle {\mathcal {O}}(|V|+\operatorname {sort} (|E|))}$ I/Os.

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.

Konkret will man die Anzahl Knoten auf mindestens ${\displaystyle {\tfrac {|E|}{B}}}$ reduzieren, um dann auf dem resultierenden Graphen den Algorithmus von Prim laufen zu lassen, wodurch sich dessen Komplexität zu ${\displaystyle {\mathcal {O}}(\operatorname {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

${\displaystyle \left\lceil \log _{2}\left({\frac {|V|\cdot B}{|E|}}\right)\right\rceil }$ Phasen

nötig. Eine einzelne Phase lässt sich mit ${\displaystyle {\mathcal {O}}(\operatorname {sort} (|E|))}$ I/Os implementieren, sodass sich insgesamt

${\displaystyle {\mathcal {O}}\left(\operatorname {sort} (|E|)\cdot \max \left\{1,\left\lceil \log _{2}\left({\frac {|V|\cdot B}{|E|}}\right)\right\rceil \right\}\right)}$ I/Os

ergeben. Die Maximumsbildung in der Komplexität rührt daher, dass mindestens eine Boruvka-Phase nötig ist.

Randomisierter Sweep

Anstatt den deterministischen Verfahren kann man die Berechnung auch randomisiert durchführen. 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 ebenfalls 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.

Ein Problem ergibt sich, wenn die zufällige Auswahl direkt umgesetzt wird: für jeden Knoten fällt ein I/O an, da auf die Knoten in willkürlicher Reihenfolge zugegriffen wird. Man kann dem entgegnen, indem man stattdessen eine zufällige Permutation der Knotenindizes erstellt und die Knoten nach deren neu zugewiesenen Indizes absteigend abarbeitet (= Sweeping).

Auch hier wird wieder eine externe Prioritätswarteschlange benutzt, welche die Kanten des Graphen speichert. Als Priorität wird der größere Knotenindex der Kante gewählt, wobei bei zwei gleichen Indizes die Kante mit kleinerem Gewicht die höhere Priorität bekommt. Dadurch kann man effizient die zu einem Knoten inzidente leichteste Kante bestimmen. Durch die Sortierung nach Knotenindizes und weil in jedem Schritt von einem Knoten ${\displaystyle u}$ nur die leichteste Kante ${\displaystyle \{u,v\}}$ betrachtet wird, lässt sich die Kantenkontraktion ohne weiteres umsetzen. Dazu wird in der nächsten Iteration die Kante ${\displaystyle \{u,w\}}$ als Kante ${\displaystyle \{v,w\}}$ mit selbem Gewicht in die Warteschlange eingefügt.

Die erwartete Anzahl betrachteter Kanten, bis die Anzahl Knoten auf ${\displaystyle M}$ reduziert wurde, beträgt

${\displaystyle 2\cdot |E|\cdot \ln \left({\frac {|V|}{M}}\right)}$.

Damit werden insgesamt

${\displaystyle |E|+4\cdot |E|\cdot \ln \left({\frac {|V|}{M}}\right)}$ Operationen

auf der Warteschlange ausgeführt und es ergeben sich insgesamt

${\displaystyle {\mathcal {O}}\left(\operatorname {sort} \left(|E|\cdot \ln \left({\frac {|V|}{M}}\right)\right)\right)}$ I/Os.