Prim-Algorithmus Rechner

Pseudocode

Prim lässt einen einzigen Baum von einem beliebigen Startknoten nach außen wachsen. In jedem Schritt nimmt er die billigste Kante, die genau einen Endpunkt bereits im Baum hat.

Prim(graph, start):
    imBaum = {start}
    pq = Prioritätswarteschlange der von start ausgehenden Kanten
    mst = []

    solange imBaum nicht alle Knoten enthält:
        (u, v, w) = pq.entnimmMinimum()
        wenn v in imBaum: weiter      // veraltet

        mst.anhängen((u, v, w))
        imBaum.hinzufügen(v)
        für jede Kante (v, x, w2):
            wenn x nicht in imBaum: pq.einfügen((v, x, w2))

Die Korrektheit beruht auf der Schnitteigenschaft: Für jede Aufteilung der Knoten in zwei Seiten gehört die billigste diesen Schnitt kreuzende Kante zu einem minimalen Spannbaum. Prim wendet sie mit dem Schnitt "bereits im Baum" gegen "noch nicht" an, und deshalb ist das Nehmen der billigsten kreuzenden Kante stets sicher und Backtracking nie nötig.

Durchgerechnetes Beispiel, Schritt für Schritt

Lasse einen minimalen Spannbaum von A aus auf einem kleinen gewichteten Graphen wachsen, in dem die gierige Wahl eine scheinbar günstigere direkte Kante bewusst verwirft.

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

1. Start bei A. Der Baum enthält nur A. Die ausgehenden Kanten sind A-B mit 2 und A-C mit 3.
2. A-B (2) nehmen. A-B ist die billigere kreuzende Kante, also tritt B dem Baum bei. Die Grenze enthält nun A-C mit 3, B-C mit 1 und B-D mit 7.
3. B-C (1) nehmen. B-C mit 1 ist jetzt die billigste kreuzende Kante, günstiger als die direkte A-C mit 3, also tritt C über B bei. Die direkte Kante A-C wird nie verwendet. Diesen Schritt lohnt es zu beobachten: ein zum Start benachbarter Knoten wird nicht zwangsläufig über den Start angebunden.
4. A-C wird intern. Da nun A und C beide im Baum sind, hat die Kante A-C beide Endpunkte innen und wird verworfen, sobald sie auftaucht. Das ist die Prüfung auf veraltete Einträge bei der Arbeit.
5. C-D (4) nehmen. Die verbleibenden kreuzenden Kanten sind C-D mit 4 und B-D mit 7. C-D ist günstiger, also tritt D bei und der Baum umspannt alle vier Knoten.

Der minimale Spannbaum besteht aus A-B, B-C und C-D mit Gesamtgewicht 2 + 1 + 4 = 7. Beachte, dass er genau drei Kanten hat, eine weniger als die vier Knoten, wie es bei jedem Spannbaum sein muss. Beachte auch, dass der Baum hier ein Pfad ist, was daran erinnert, dass ein minimaler Spannbaum kein Kürzeste-Wege-Baum ist: die beiden Probleme optimieren Verschiedenes.

Komplexität und woher sie kommt

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

Mit einem Binärheap kann jede Kante einmal eingefügt und einmal entnommen werden, jeweils O(log E), und da E höchstens V hoch 2 ist, liegt log E innerhalb eines konstanten Faktors von log V, was O(E log V) ergibt. Jeder Knoten wird genau einmal in den Baum aufgenommen. Ein Fibonacci-Heap mit Verringern des Schlüssels statt trägem Einfügen verbessert die Schranke auf O(E + V log V), asymptotisch besser auf dichten Graphen, wenn auch selten die Konstanten wert. Auf einem sehr dichten Graphen gewinnt die einfachste Variante: ein Feld mit der billigsten bekannten Kante zu jedem Außenknoten, das jede Runde durchsucht wird, mit O(V hoch 2), was O(E log V) schlägt, sobald E sich V hoch 2 nähert.

Wann Prim MST-Algorithmus passt und wann nicht

Prim und Kruskal liefern beide einen minimalen Spannbaum. Welcher passt, hängt von der Dichte ab und davon, wie die Kanten eintreffen.

Häufige Fehler

• Einen minimalen Spannbaum mit einem Kürzeste-Wege-Baum verwechseln. Das sind verschiedene Ziele. Ein MST minimiert das Gesamtgewicht des ganzen Baums; ein Kürzeste-Wege-Baum minimiert die Distanz von einer Quelle zu jedem Knoten. Im obigen Beispiel kostet der MST-Weg von A nach D 7 in Baumkanten, und allgemein kann ein MST einzelne Paare weit weiter auseinander lassen als nötig.
• Die Prüfung auf veraltete Einträge weglassen. Ein träger Heap sammelt Kanten an, deren fernes Ende später auf anderem Weg dem Baum beitritt. Eine davon zu entnehmen und hinzuzufügen erzeugt einen Zyklus und zerstört den Baum. Prüfe stets, ob das Ziel bereits im Baum ist, bevor du eine Kante annimmst.
• Ihn auf einem unzusammenhängenden Graphen ausführen. Prim lässt einen Baum von einem Start wachsen und endet, wenn er keine kreuzende Kante mehr findet. Auf einem unzusammenhängenden Graphen liefert er nur einen Spannbaum einer Komponente. Brauchst du einen minimalen Spannwald, starte von jedem unbesuchten Knoten neu oder nimm Kruskal, der das von Haus aus beherrscht.
• Annehmen, der MST sei eindeutig. Teilen sich mehrere Kanten ein Gewicht, kann es viele minimale Spannbäume mit demselben Gesamtgewicht geben. Eindeutig ist der Baum nur, wenn alle Kantengewichte verschieden sind. Tests sollten das Gesamtgewicht vergleichen, nicht die Kantenmenge.
• Ihn auf einen gerichteten Graphen anwenden. Spannbäume im Sinne von Prim und Kruskal sind ungerichtete Begriffe. Das gerichtete Gegenstück ist die minimale spannende Arboreszenz, die den Chu-Liu/Edmonds-Algorithmus erfordert; Prim liefert dort falsche Antworten.

Häufig gestellte Fragen

Wofür wird der Algorithmus von Prim verwendet?

Er findet einen minimalen Spannbaum: die günstigste Kantenmenge, die alle Knoten eines gewichteten ungerichteten Graphen verbindet. Er dient dem Entwurf kostengünstiger Netze wie Stromnetzen, Glasfaser- und Telekomtrassen, Wasserleitungen und Chip-Verdrahtung, und er trägt außerdem Single-Linkage-Clustering und einige Verfahren zur Bildsegmentierung.

Wie ist die Zeitkomplexität des Algorithmus von Prim?

O(E log V) mit einem Binärheap, der üblichen Implementierung. Ein Fibonacci-Heap ergibt O(E + V log V), asymptotisch besser auf dichten Graphen, aber mit schlechteren Konstanten. Auf sehr dichten Graphen ist eine einfache Felddurchsuchung mit O(V hoch 2) tatsächlich schneller, weil sie den Heap-Aufwand vollständig vermeidet.

Was ist der Unterschied zwischen Prim und Kruskal?

Prim lässt einen einzigen zusammenhängenden Baum von einem Startknoten nach außen wachsen und fügt stets die billigste Kante hinzu, die einen neuen Knoten erreicht. Kruskal sortiert alle Kanten und fügt jede hinzu, die keinen Zyklus schließt, wodurch ein Wald wächst, der zu einem Baum verschmilzt. Prim passt zu dichten Graphen, Kruskal zu dünnen oder vorsortierten, und beide liefern einen minimalen Spannbaum.

Ist ein minimaler Spannbaum dasselbe wie ein Kürzeste-Wege-Baum?

Nein. Ein MST minimiert das Gesamtgewicht seiner Kanten; ein Kürzeste-Wege-Baum minimiert die Distanz von einer Quelle zu jedem Knoten. Sie unterscheiden sich häufig, und ein MST kann zwei Knoten in Baumdistanz weit auseinander lassen, obwohl eine kurze direkte Kante existiert, weil deren Verwendung das Gesamtgewicht erhöhen würde.

Ändert der Startknoten das Ergebnis?

Er kann ändern, welche Kanten bei Gewichtsgleichheit gewählt werden, nie aber das Gesamtgewicht. Prim liefert von jedem Start aus einen minimalen Spannbaum. Sind alle Kantengewichte verschieden, ist der Baum eindeutig und der Startknoten spielt überhaupt keine Rolle.