Boruvka-Algorithmus Rechner

Pseudocode

Jede Komponente wählt ihre eigene billigste ausgehende Kante, und alle diese Wahlen werden auf einmal angewendet. Runden statt Einzelschritte, und genau das macht das Verfahren parallelisierbar.

Boruvka(graph):
    makeSet(v) für jeden Knoten
    mst = []

    solange mehr als eine Komponente übrig ist:
        billigste = {} // je Komponente
        für jede Kante (u, v, w):
            a = find(u); b = find(v)
            wenn a == b: weiter          // interne Kante
            wenn w < billigste[a]: billigste[a] = (u,v,w)
            wenn w < billigste[b]: billigste[b] = (u,v,w)

        für jede Kante e in billigste.werte():
            wenn find(e.u) != find(e.v):  // evtl. schon vereint
                union(e.u, e.v); mst.anhängen(e)

Die Absicherung in der zweiten Schleife ist notwendig, nicht bloß vorsichtshalber. Zwei Komponenten wählen häufig dieselbe Kante, je einmal von jedem Ende, und sie zweimal anzuwenden fügte ein Duplikat hinzu. Für die Korrektheit müssen die Kantengewichte verschieden sein oder es braucht eine einheitliche Regel zur Auflösung von Gleichständen, etwa den Vergleich von Kantenindizes: ohne eine solche Regel können mehrere Komponenten jeweils eine andere Kante gleichen Gewichts wählen und gemeinsam einen Zyklus bilden.

Durchgerechnetes Beispiel, Schritt für Schritt

Baue den minimalen Spannbaum auf demselben Graphen wie bei Prim und Kruskal, damit sich alle drei Verfahren unmittelbar vergleichen lassen.

Beispielgraph: Ungerichtete Kanten A-B (2), A-C (3), B-C (1), C-D (4) und B-D (7).

1. Beginn. Jeder Knoten bildet seine eigene Komponente: {A}, {B}, {C}, {D}. Jede Kante ist damit für beide ihrer Endpunkte eine ausgehende Kante.
2. Jede Komponente wählt. Komponente A vergleicht A-B mit 2 gegen A-C mit 3 und wählt A-B. Komponente B vergleicht A-B mit 2, B-C mit 1 und B-D mit 7 und wählt B-C. Komponente C vergleicht A-C mit 3, B-C mit 1 und C-D mit 4 und wählt B-C. Komponente D vergleicht C-D mit 4 gegen B-D mit 7 und wählt C-D.
3. Das Duplikat beachten. B und C nominierten beide dieselbe Kante B-C, je einmal von einem Ende. Die Absicherung in der zweiten Schleife wendet sie nur einmal an, und genau dafür existiert diese Prüfung.
4. Alle Wahlen auf einmal anwenden. Das Hinzufügen von A-B, B-C und C-D verschmilzt in einer einzigen Runde alles zu einer Komponente. Das sind drei Kanten für vier Knoten, der Baum ist also bereits vollständig.
5. Die Schleife endet. Es bleibt nur eine Komponente übrig, eine zweite Runde findet also nicht statt.

Der minimale Spannbaum besteht aus A-B, B-C und C-D mit Gesamtgewicht 2 + 1 + 4 = 7, also demselben Baum, den Prim und Kruskal lieferten. Boruvka erreichte ihn in einer Runde statt in drei aufeinanderfolgenden Schritten, und darum geht es: jede Runde halbiert die Zahl der Komponenten mindestens, da jede Komponente mit mindestens einer anderen verschmilzt, sodass nie mehr als O(log V) Runden nötig sind. Bei vier Knoten genügte hier bereits eine einzige.

Komplexität und woher sie kommt

Zeit: O(E log V) · Speicher: O(V + E)

Jede Runde durchsucht alle Kanten einmal mit O(E), um je Komponente die billigste ausgehende Kante zu finden. Während einer Runde verschmilzt jede Komponente mit mindestens einer anderen, die Komponentenzahl halbiert sich also mindestens, womit höchstens log zur Basis 2 von V Runden auftreten. Multipliziert ergibt das O(E log V) und entspricht damit Prim und Kruskal. Die auszeichnende Eigenschaft ist, dass innerhalb einer Runde jede Komponente unabhängig arbeitet, sodass sich der Durchlauf unmittelbar parallelisieren lässt; deshalb liegt Boruvka den MST-Implementierungen auf GPUs und in verteilten Systemen zugrunde, während Prim und Kruskal von Natur aus sequenziell sind. Hybride Verfahren führen einige Boruvka-Runden aus, um den Graphen zu verkleinern, und wechseln dann zu Prim.

Wann Borůvka-Algorithmus passt und wann nicht

Alle drei klassischen MST-Algorithmen kosten O(E log V). Der Unterschied ist struktureller Natur.

Häufige Fehler

• Gleiche Kantengewichte nicht behandeln. Bei gleichen Gewichten können verschiedene Komponenten verschiedene Kanten wählen, die zusammen einen Zyklus schließen, und das Ergebnis ist kein Baum. Löse Gleichstände einheitlich auf, etwa über den Kantenindex, sodass sich alle Komponenten auf dieselbe Ordnung stützen. Bei durchweg verschiedenen Gewichten verschwindet das Problem von selbst.
• Dieselbe Kante zweimal hinzufügen. Zwei Komponenten nominieren regelmäßig dieselbe Kante von gegenüberliegenden Enden. Ohne eine Prüfung, ob die Endpunkte zum Zeitpunkt des Anwendens noch in verschiedenen Komponenten liegen, wird die Kante zweimal aufgenommen und die Kantenzahl übersteigt V - 1.
• Komponenten innerhalb des Kantendurchlaufs neu berechnen. Wiederholte find-Aufrufe ohne Pfadkompression machen jede Runde weit teurer als O(E). Nutze Union-Find mit Pfadkompression und Union by Rank, genau wie bei Kruskal.
• Annehmen, er brauche einen zusammenhängenden Graphen. Wie Kruskal verarbeitet Boruvka unzusammenhängende Eingaben von Haus aus und liefert einen minimalen Spannwald. Die Schleifenbedingung muss dann aber lauten "keine Komponente hat eine ausgehende Kante" statt "eine Komponente bleibt übrig", sonst terminiert er nicht.
• Übersehen, dass er älter ist als die anderen. 1926 zur Planung eines Stromnetzes in Mähren veröffentlicht, ist Boruvka der älteste bekannte MST-Algorithmus, älter als Prim und Kruskal. Er wird oft zuletzt gelehrt, was verdeckt, dass die parallele Formulierung zuerst da war.

Häufig gestellte Fragen

Wie funktioniert der Algorithmus von Boruvka?

Jede Komponente wählt gleichzeitig die billigste aus ihr herausführende Kante, und alle gewählten Kanten werden auf einmal hinzugefügt, wodurch Komponenten verschmelzen. Das wiederholt sich, bis eine einzige Komponente übrig ist. Da jede Komponente pro Runde mit mindestens einer anderen verschmilzt, halbiert sich ihre Zahl jedes Mal mindestens und es sind nur O(log V) Runden nötig.

Wie ist die Zeitkomplexität des Algorithmus von Boruvka?

O(E log V). Jede Runde durchsucht alle E Kanten, um je Komponente die billigste ausgehende Kante zu finden, und es treten höchstens log V Runden auf, weil sich die Komponentenzahl in jeder Runde halbiert. Das entspricht asymptotisch Prim und Kruskal.

Warum eignet sich Boruvka gut für paralleles Rechnen?

Weil innerhalb einer Runde jede Komponente ihre billigste ausgehende Kante unabhängig bestimmt, ohne gemeinsamen Zustand und ohne Reihenfolgeanforderung. Das lässt sich direkt auf GPUs und verteilte Cluster abbilden. Prim und Kruskal sind von Natur aus sequenziell: beide hängen von der einen globalen Entscheidung ab, die unmittelbar zuvor getroffen wurde.

Warum müssen die Kantengewichte verschieden sein?

Bei gleichen Gewichten können verschiedene Komponenten unterschiedliche Kanten gleicher Kosten wählen, die zusammen einen Zyklus bilden, sodass das Ergebnis kein Baum ist. Jede einheitliche Regel zur Auflösung von Gleichständen, etwa der Vergleich von Kantenindizes bei gleichem Gewicht, stellt die Korrektheit wieder her. Verschiedene Gewichte machen den minimalen Spannbaum zudem eindeutig.

Was ist der Unterschied zwischen Boruvka, Prim und Kruskal?

Alle drei liefern einen minimalen Spannbaum in O(E log V). Prim lässt einen Baum von einem Startknoten aus mit einer Prioritätswarteschlange wachsen. Kruskal sortiert alle Kanten und fügt jene hinzu, die keinen Zyklus schließen. Boruvka lässt jede Komponente in parallelen Runden ihre billigste ausgehende Kante wählen und ist als einziger der drei natürlich parallelisierbar.