Wikipedia · einfach zusammengefasst · Stand
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 G = ( V …
Inhalt5 Abschnitte
Grundidee und Berechnungsmodell
Ein externer minimaler Spannbaum ist ein minimaler Spannbaum eines Graphen G=(V,E), der berechnet wird, obwohl der Graph im Sekundärspeicher liegt. Dies ist nötig, wenn Knoten und Kanten nicht gleichzeitig vollständig in den Hauptspeicher passen.
Als Beispiel nennt der Artikel einen Twitter-Crawl von 2010 mit 41.652.230 Knoten und 1.468.365.182 Kanten. Speichert man eine Kante ohne Gewicht als Paar von Knotenindizes, beträgt die Größe des Graphen
( (2·⌈log₂(41652230)⌉)·1468365182 ) / 8 Bytes ≈ 9,55·10⁹ Bytes,
also 9,55 Gigabytes. Bei angenommenen 8 GB Hauptspeicher eines Desktop-PCs reicht dieser nicht für eine vollständig interne Berechnung.
Externe Algorithmen verwenden das External-Memory-Modell: Der Hauptspeicher hat Größe M, Daten liegen außerdem im Sekundärspeicher, und Blöcke der Größe B können übertragen werden. Das Lesen eines Blocks aus dem Sekundärspeicher beziehungsweise das Schreiben eines Blocks dorthin heißt I/O (Input/Output). Anders als etwa im Random-Access-Machine-Modell wird vor allem die Zahl der I/Os minimiert, weil Zugriffe auf den Sekundärspeicher deutlich langsamer sind und zum Flaschenhals werden können.
Semiexterne Berechnung mit Kruskal
Semiexterne Algorithmen sind ein Sonderfall: Sie verarbeiten ungerichtete Graphen, bei denen die Knoten, aber nicht alle Kanten, in den Hauptspeicher passen. Formal gilt
M=c·|V|<|E|,
wobei c eine Konstante ist.
Der Algorithmus von Kruskal lässt sich dafür einfach einsetzen. Zuerst werden alle Kanten extern nach aufsteigendem Gewicht sortiert. Dies benötigt die Sortierschranke
sort(|E|):=Θ((|E|/B)·log_(M/B)(|E|/B)) I/Os.
Die Union-Find-Struktur, mit der festgestellt wird, ob eine Kante zwei bereits verbundene Knoten verbindet, kann vollständig im Hauptspeicher liegen. Insgesamt benötigt die semiexterne Kruskal-Variante daher O(sort(|E|)) I/Os.
Externer Prim-Algorithmus
Passen auch die Knoten nicht in den Hauptspeicher, kann Prim mit einer externen Prioritätswarteschlange ausgeführt werden. Die Warteschlange speichert Kanten; ihre Prioritäten sind die Kantengewichte. Von einem beliebigen Startknoten s aus werden zunächst dessen adjazente Kanten eingefügt. Danach wird wiederholt die Kante kleinsten Gewichts mit extractMin() entnommen. Führt sie zu einem Knoten v, der noch nicht zum bisherigen Spannbaum T gehört, werden v und die Kante (u,v) in T aufgenommen. Anschließend werden die inzidenten Kanten von v, außer (v,u), eingefügt.
Der Artikel betrachtet dabei gerichtete Kanten von G. Es wird angenommen, dass alle Kantengewichte paarweise verschieden sind. Dann kann die Prüfung, ob v schon in T ist, durch eine zusätzliche extractMin()-Operation umgesetzt werden: Hat v seine inzidenten Kanten bereits eingefügt, ist die Gegenkante (v,u) in der Warteschlange und wegen der unterschiedlichen Gewichte unmittelbar der Nachfolger von (u,v).
Das Auslesen aller adjazenten Knoten benötigt bei einer Adjazenzlisten-Darstellung O(|V|+|E|/B) I/Os. Jede Kante verursacht höchstens zwei Operationen auf der Prioritätswarteschlange. Unterstützt diese n Operationen mit O(sort(n)) I/Os, beträgt die gesamte I/O-Komplexität O(|V|+sort(|E|)).
Kantenreduktion durch Borůvka-Phasen
Ein anderer externer Ansatz identifiziert schrittweise Kanten, die sicher zum minimalen Spannbaum gehören, und kontrahiert sie. Bei einer Kantenkontraktion werden ihre Endknoten zu einem Knoten zusammengefasst. Im Beispiel wird die Kante {1,2} kontrahiert; die neue Kante {1,3} war zuvor {2,3}. Für neu entstehende Kanten müssen Verweise auf ihre ursprünglichen Kanten gespeichert werden, damit am Ende ein minimaler Spannbaum des ursprünglichen Graphen rekonstruiert werden kann.
Die Reduktion folgt dem Algorithmus von Borůvka: Jeder Knoten wählt seine leichteste adjazente Kante; diese muss zum minimalen Spannbaum gehören. Anschließend werden alle ausgewählten Kanten kontrahiert. Dadurch halbiert sich die Knotenzahl mindestens. Ziel ist, die Knotenzahl auf mindestens |E|/B zu reduzieren. Auf dem dann ausreichend dichten Graphen kann Prim mit O(sort(|E|)) I/Os ausgeführt werden.
Benötigt werden insgesamt
⌈log₂((|V|·B)/|E|)⌉
Phasen. Eine Phase kostet O(sort(|E|)) I/Os. Damit ergibt sich
O(sort(|E|)·max{1,⌈log₂((|V|·B)/|E|)⌉}) I/Os.
Das Maximum mit 1 stellt sicher, dass mindestens eine Borůvka-Phase berücksichtigt wird.
Randomisierter Sweep
Statt eines deterministischen Verfahrens kann die Knotenanzahl randomisiert durch Kantenkontraktionen reduziert werden, bis ein semiexterner Algorithmus auf dem Restgraphen möglich ist. Iterativ wird ein zufälliger Knoten gewählt, seine leichteste Kante in den minimalen Spannbaum aufgenommen und diese Kante kontrahiert.
Eine unmittelbare zufällige Auswahl wäre teuer, weil für jeden willkürlich angesprochenen Knoten ein I/O anfällt. Deshalb wird eine zufällige Permutation der Knotenindizes erzeugt und die Knoten werden gemäß ihren neuen Indizes absteigend abgearbeitet; dies heißt Sweeping.
Wieder speichert eine externe Prioritätswarteschlange die Kanten. Ihre Priorität ist der größere Knotenindex einer Kante. Bei gleichen Indizes hat die Kante mit kleinerem Gewicht die höhere Priorität. So lässt sich für einen Knoten effizient seine leichteste inzidente Kante bestimmen. Wird von u die leichteste Kante {u,v} kontrahiert, wird in der nächsten Iteration eine Kante {u,w} als {v,w} mit gleichem Gewicht in die Warteschlange eingefügt.
Bis die Knotenzahl auf M sinkt, werden erwartungsgemäß 2·|E|·ln(|V|/M) Kanten betrachtet. Insgesamt erfolgen |E|+4·|E|·ln(|V|/M) Warteschlangenoperationen. Die I/O-Komplexität ist daher O(sort(|E|·ln(|V|/M))).
