Der Algorithmus von Prim erklärt

Mohammed Islam Hadjoudj

Experte für Operations Research

1. Einführung in den Algorithmus von Prim

Der Algorithmus von Prim erzeugt einen minimalen Spannbaum: Aus einem zusammenhängenden, ungerichteten, gewichteten Graphen wählt er eine Teilmenge der Kanten, die jeden Knoten berührt, keinen Zyklus enthält und das kleinstmögliche Gesamtgewicht besitzt. Bei einem Graphen mit V Knoten umfasst diese Teilmenge stets genau V - 1 Kanten.

Die Strategie besteht darin, einen einzigen Baum nach außen wachsen zu lassen. Beginnen Sie bei einem beliebigen Knoten, greifen Sie dann wiederholt über den Rand des bereits Gebauten hinaus und holen Sie die günstigste Kante herein, die einen noch nicht besessenen Knoten berührt. Wiederholen Sie das V - 1 Mal, und der Baum ist fertig. Es gibt kein Zurücknehmen, und nichts wird je entfernt.

Diese Beschreibung klingt fast zu gierig, um korrekt zu sein. Immer die gerade günstigste Kante zu wählen, ohne vorauszuschauen, ist genau die Strategie, die bei kürzesten Wegen scheitert, sobald eine negative Kante auftaucht. Bei minimalen Spannbäumen scheitert sie nicht, und der Grund ist ein einziger Satz, den man verstanden haben sollte, bevor man Code anfasst.

2. Warum es funktioniert: die Schnitteigenschaft

Ein Schnitt teilt die Knoten in zwei nicht leere Gruppen. Eine Kante kreuzt den Schnitt, wenn ihre beiden Endpunkte in verschiedenen Gruppen liegen. Der Satz, auf dem der Algorithmus von Prim ruht, lautet:

Der Beweis ist kurz und lohnt sich, denn er erklärt den gesamten Algorithmus. Sei e die günstigste Kante, die einen Schnitt kreuzt, und angenommen, ein minimaler Spannbaum T enthält sie nicht. Fügt man e zu T hinzu, entsteht genau ein Zyklus, und dieser Zyklus muss den Schnitt ein zweites Mal kreuzen, über eine andere Kante f. Entfernen Sie f. Sie haben weiterhin einen Spannbaum, und da e die günstigste kreuzende Kante war, ist ihr Gewicht nicht größer als das von f, der neue Baum also nicht schwerer. Es existiert somit ein minimaler Spannbaum, der e enthält.

Betrachten Sie nun, was der Algorithmus von Prim in jedem Schritt tut. Die bereits im Baum enthaltenen Knoten bilden die eine Seite eines Schnitts, alles Übrige die andere. Der Algorithmus wählt die günstigste Kante, die genau diesen Schnitt kreuzt. Nach der Schnitteigenschaft ist jede gewählte Kante sicher: Sie gehört zu einem minimalen Spannbaum. Die gierige Wahl ist nie ein Glücksspiel, das zufällig aufgeht, sondern ein V - 1 Mal angewandter Satz.

3. Wie der Baum wächst

Konkret verwaltet der Algorithmus drei Dinge: die Menge der bereits im Baum enthaltenen Knoten, einen key-Wert für jeden Knoten außerhalb und einen parent-Zeiger, der festhält, welcher Baumknoten diesen Schlüssel angeboten hat.

• key[v] ist das Gewicht der günstigsten einzelnen Kante, die v mit dem aktuellen Baum verbindet, oder unendlich, wenn es eine solche Kante noch nicht gibt.
• parent[v] ist der Baumknoten am anderen Ende dieser Kante. Er ermöglicht es, am Ende den tatsächlichen Baum auszugeben und nicht nur sein Gewicht.

Jede Runde nimmt den Knoten außerhalb des Baums mit dem kleinsten key, fügt ihn zusammen mit der Kante zu seinem parent hinzu und relaxiert anschließend: Ist für einen Nachbarn w außerhalb des Baums die Kante zu w günstiger als key[w], wird key[w] gesenkt und parent[w] umgesetzt.

Achten Sie genau darauf, was der Schlüssel darstellt. Er ist das Gewicht einer einzelnen Kante, nicht die Kosten eines Weges. Genau dieses Detail trennt diesen Algorithmus von dem Dijkstras, ein Punkt, auf den wir zurückkommen, sobald der Code auf der Seite steht.

4. Schritt für Schritt durchgerechnet

Nehmen wir den Graphen mit sechs Knoten, der sich durch unseren Leitfaden zu minimalen Spannbäumen zieht. Seine neun Kanten sind:

A-B 4    A-C 1    B-C 2
B-D 5    C-D 6    C-E 7
D-E 2    D-F 8    E-F 3

Starten Sie bei A. In jeder Runde ist die "Front" die Menge der Kanten mit genau einem Endpunkt im Baum, und der Algorithmus nimmt davon die günstigste.

1. Baum = {A}. Front: A-C (1), A-B (4). Am günstigsten ist A-C (1). C hinzufügen.
2. Baum = {A, C}. Front: B-C (2), A-B (4), C-D (6), C-E (7). Beachten Sie, dass B nun auf zwei Wegen erreichbar ist, mit 4 über A und mit 2 über C, sein Schlüssel fällt also auf 2. Am günstigsten ist B-C (2). B hinzufügen.
3. Baum = {A, C, B}. Front: B-D (5), C-D (6), C-E (7). D ist mit 5 oder 6 erreichbar, sein Schlüssel ist also 5. Am günstigsten ist B-D (5). D hinzufügen.
4. Baum = {A, C, B, D}. Front: D-E (2), C-E (7), D-F (8). Der Schlüssel von E fällt von 7 auf 2. Am günstigsten ist D-E (2). E hinzufügen.
5. Baum = {A, C, B, D, E}. Front: E-F (3), D-F (8). Der Schlüssel von F fällt von 8 auf 3. Am günstigsten ist E-F (3). F hinzufügen.

Fünf Kanten für sechs Knoten, und der Algorithmus hält an. Der Baum besteht aus A-C (1), B-C (2), B-D (5), D-E (2), E-F (3) mit einem Gesamtgewicht von 13. Die Kanten A-B (4), C-D (6), C-E (7) und D-F (8) werden nie verwendet.

Zwei Momente dieser Ablaufverfolgung verdienen Aufmerksamkeit. In Runde 3 akzeptierte der Algorithmus eine Kante mit Gewicht 5, während eine Kante mit Gewicht 2 (D-E) anderswo im Graphen unberührt lag. Prim kann D-E noch nicht nehmen, weil keiner ihrer Endpunkte im Baum liegt und ihre Aufnahme zwei getrennte Fragmente statt eines wachsenden Baums hinterlassen würde. In Runde 4 fiel der Schlüssel von E von 7 auf 2, sobald D beitrat. Schlüssel können nur kleiner werden, und genau das macht die Umsetzung mit einer Prioritätswarteschlange effizient.

5. Implementierung: Lazy und Eager Prim

Zwei Umsetzungen sind üblich, und der Unterschied liegt darin, was die Prioritätswarteschlange enthält.

Lazy Prim

Die einfachere Variante legt jede angetroffene Kante in einen Min-Heap und verwirft beim Entnehmen jene Einträge, die sich als veraltet erweisen.

function LazyPrim(Graph, start):
    inTree = set()
    pq = leerer Min-Heap, sortiert nach Kantengewicht
    mst = []

    visit(start)                    // markieren und Kanten einfügen

    while pq nicht leer and size(mst) < V - 1:
        (w, u, v) = pq.pop()        // bisher günstigste Kante
        if v in inTree: continue    // veraltet: beide Enden schon im Baum
        mst.append((u, v, w))
        visit(v)

    return mst

function visit(x):
    inTree.add(x)
    for jede Kante (x, y) mit Gewicht w:
        if y not in inTree: pq.push((w, x, y))

Die Zeile if v in inTree: continue leistet die eigentliche Arbeit. Sie verhindert Zyklen, und sie ist der Grund, warum der Heap gefahrlos veraltete Einträge halten darf: Sie werden beim Auftauchen einfach übersprungen.

Eager Prim

Die eifrige Variante hält höchstens einen Eintrag pro Knoten, den aktuellen key[v], und senkt ihn an Ort und Stelle mit einer Decrease-Key-Operation. Sie benötigt eine indizierte Prioritätswarteschlange, also mehr Maschinerie, dafür wächst der Heap nie über V Einträge statt E hinaus.

function EagerPrim(Graph, start):
    for jeden Knoten v:
        key[v] = Infinity
        parent[v] = Null
    key[start] = 0
    pq = indizierter Min-Heap aller Knoten, sortiert nach key[]

    while pq nicht leer:
        u = pq.popMin()
        inTree.add(u)
        for jede Kante (u, v) mit Gewicht w:
            if v not in inTree and w < key[v]:
                key[v] = w                  // das KANTENGEWICHT, keine Summe
                parent[v] = u
                pq.decreaseKey(v, w)

    return parent            // parent[] ist der Baum

Bevorzugen Sie Eager Prim bei dichten Graphen, in denen E weit größer als V ist und es verschwenderisch wird, jede Kante im Heap zu halten. Lazy Prim ist bei dünn besetzten Graphen völlig angemessen und deutlich leichter fehlerfrei umzusetzen.

6. Zeit- und Speicherkomplexität

• Lazy Prim, binärer Heap: O(E log E) Zeit. Jede Kante kann einmal eingefügt und einmal entnommen werden. Da E < V2 gilt, ist log E in O(log V), weshalb man meist O(E log V) schreibt. Speicher: O(E).
• Eager Prim, indizierter binärer Heap: O(E log V) Zeit, aus V Entnahmen und bis zu E Decrease-Key-Operationen zu je O(log V). Speicher: O(V).
• Eager Prim, ohne Heap, Adjazenzmatrix: O(V2) Zeit durch lineare Suche nach dem kleinsten Schlüssel. Bei einem dichten Graphen, in dem E sich V2 nähert, schlägt das die Heap-Variante, denn O(V2) ist besser als O(V2 log V).
• Eager Prim, Fibonacci-Heap: O(E + V log V), die beste bekannte Schranke für Prim, da Decrease-Key amortisiert konstante Zeit kostet. Die konstanten Faktoren sind groß genug, dass es in der Praxis selten gewinnt.

Praktisch zusammengefasst: binärer Heap bei dünn besetzten Graphen, schlichte O(V2)-Matrixsuche bei dichten. Der Fibonacci-Heap ist überwiegend von theoretischem Interesse.

7. Prim gegen Dijkstra: eine Zeile Unterschied

Stellt man den Pseudocode von Eager Prim neben den Dijkstra-Algorithmus, sind es nahezu dieselben Programme. Beide führen einen Schlüssel pro Knoten, beide entnehmen wiederholt das Minimum, beide relaxieren die Nachbarn des gerade Entnommenen. Der gesamte Unterschied liegt darin, was in den Schlüssel kommt:

Prim:      if w < key[v]:              key[v] = w
Dijkstra:  if key[u] + w < key[v]:     key[v] = key[u] + w

Der Schlüssel bei Prim ist das Gewicht einer einzelnen Kante. Der Schlüssel bei Dijkstra ist die aufsummierte Länge eines ganzen Weges von der Quelle. Deshalb beantworten sie verschiedene Fragen: Prim fragt "wie günstig lässt sich dieser Knoten an meinen Baum anhängen", Dijkstra fragt "wie günstig lässt sich dieser Knoten von der Quelle aus erreichen".

Das erklärt auch, warum negative Gewichte den einen brechen und den anderen nicht. Die Korrektheit von Dijkstra hängt davon ab, dass Wegkosten nicht sinken, wenn Wege länger werden, was eine negative Kante zerstört. Prim addiert überhaupt nie Gewichte, daher sind negative Kantengewichte für ihn völlig unschädlich. Ein minimaler Spannbaum ist auf einem Graphen mit negativen Gewichten wohldefiniert, und Prim findet ihn ohne Anpassung.

8. Prim gegen Kruskal

Beide Algorithmen sind gierig, beide werden durch die Schnitteigenschaft gerechtfertigt, und bei paarweise verschiedenen Gewichten liefern beide denselben Baum. Sie unterscheiden sich darin, was unterwegs zusammenhängend bleibt.

• Prim hält jederzeit einen zusammenhängenden Baum und lässt ihn nach außen wachsen. Er sortiert die Kanten nie und braucht eine Prioritätswarteschlange.
• Kruskal sortiert alle Kanten nach Gewicht und fügt jede hinzu, sofern sie keinen Zyklus schließt, hält also einen Wald aus Fragmenten, die erst ganz am Ende zu einem Baum verschmelzen. Er braucht eine Union-Find-Struktur.

Die praktische Regel folgt aus der Dichte. Kruskals Kosten werden vom Sortieren dominiert, mit O(E log E), was hervorragend ist, solange E klein bleibt. Prim mit Adjazenzmatrix läuft unabhängig von der Kantenzahl in O(V2) und gewinnt bei dichten Graphen. Bei unzusammenhängender Eingabe gibt es zudem einen strukturellen Unterschied: Kruskal liefert von Natur aus einen minimalen Spannwald, während Prim von einem einzigen Startknoten aus nur dessen Zusammenhangskomponente aufspannt, sodass Sie ihn je Komponente einmal neu starten müssen.

9. Praxishinweise und typische Fallstricke

Vier Situationen bereiten Schwierigkeiten, wenn man vom Lehrbuchfall zu echten Eingaben übergeht.

• Gleiche Gewichte bedeuten mehrere gültige Antworten. Teilen sich zwei Kanten ein Gewicht, kann der Graph mehr als einen minimalen Spannbaum besitzen, und welchen Sie erhalten, hängt davon ab, wie Ihre Prioritätswarteschlange Gleichstände auflöst. Alle sind gleich optimal, weshalb ein Test, der gegen eine fest verdrahtete Kantenliste vergleicht, grundlos fehlschlägt. Vergleichen Sie stattdessen das Gesamtgewicht.
• Unzusammenhängende Eingaben scheitern lautlos. Von einem Knoten aus gestartet spannt Prim nur dessen Komponente auf und hält dann an, wobei er einen Baum zurückgibt, der völlig gültig aussieht. Die Prüfung ist Zählen: Ein echter Spannbaum hat genau V - 1 Kanten. Weniger bedeutet, dass der Graph unzusammenhängend war und Sie von einem noch nicht besuchten Knoten aus neu starten müssen.
• Schleifen und Mehrfachkanten. Eine Schleife kann niemals einen Schnitt kreuzen und ist daher stets ignorierbar. Unter Mehrfachkanten zwischen demselben Knotenpaar kann nur die günstigste je gewählt werden. Beides bricht den Algorithmus nicht, doch ein Herausfiltern beim Einlesen hält den Heap kleiner.
• Gerichtete Graphen sind ein ganz anderes Problem. Ein minimaler Spannbaum ist für ungerichtete Graphen definiert. Gerichtete Kanten in Prim zu geben liefert etwas Bedeutungsloses. Das gerichtete Gegenstück ist eine minimale Spannarboreszenz, gefunden von Edmonds' Algorithmus, und sie ist deutlich schwieriger.

10. Anwendungen in der Praxis

Minimale Spannbäume beantworten eine wiederkehrende Frage: Wie verbindet man alles möglichst günstig und ohne Redundanz? Prim passt zu den Fällen, in denen das Netz tatsächlich von einer Quelle aus wächst.

Versorgungs- und Netzplanung

Kabel, Glasfaser, Wasserleitungen oder Straßen zwischen festen Standorten zu verlegen, wobei jeder Standort erreichbar sein muss und Gesamtlänge oder Kosten zu minimieren sind, ist die ursprüngliche Motivation. Prims Arbeit entstand genau an diesem Problem bei Bell Labs.

Clusteranalyse

Den minimalen Spannbaum einer Punktmenge zu bilden und dann seine schwersten Kanten zu entfernen, ist Single-Linkage-Clustering: Entfernt man die k - 1 schwersten Kanten, bleiben genau k Cluster. Der Baum wird einmal berechnet, und jeder Wert von k ergibt sich daraus.

Näherung für schwerere Probleme

Der minimale Spannbaum liefert eine untere Schranke für die Rundreise des Handlungsreisenden, und das Verdoppeln seiner Kanten ergibt bei metrischen Instanzen eine Tour, die höchstens doppelt so lang wie die optimale ist. Er ist der Ausgangspunkt der Christofides-Konstruktion, die diese Garantie auf 1,5 verbessert.

Bildsegmentierung und Labyrinthe

Behandelt man Pixel als Knoten und Unähnlichkeit als Kantengewicht, gruppiert MST-basierte Segmentierung ein Bild in Regionen. Lässt man Prim stattdessen auf einem Gitter mit zufälligen Gewichten laufen, entsteht ein gleichmäßig wirkendes Labyrinth, weshalb er ein Klassiker der prozeduralen Generierung ist.

11. Wissenschaftliche Quellen und Geschichte

Wie mehrere klassische Graphenalgorithmen wurde auch dieser mehr als einmal entdeckt, und der Name, den er trägt, ist nicht der jener Person, die ihn zuerst fand.

• Otakar Borůvka (1926) stellte und löste das Problem des minimalen Spannbaums zuerst, motiviert durch die Elektrifizierung des ländlichen Mährens. Sein Algorithmus ist ein anderer: Er fügt in parallelen Runden die günstigste Kante aus jedem Fragment hinzu.
• Vojtěch Jarník (1930) veröffentlichte den Algorithmus, den wir heute Prim nennen, in einem Brief als Antwort an Borůvka. Deshalb wird er zutreffend auch Jarník-Prim-Algorithmus genannt.
• Robert C. Prim (1957) entdeckte ihn bei den Bell Laboratories unabhängig neu, während er die Kosten von Verbindungsnetzen untersuchte, und seine Arbeit erreichte ein breites Publikum.
• Edsger W. Dijkstra (1959) entdeckte ihn ein drittes Mal, in derselben kurzen Arbeit, die seinen Kürzeste-Wege-Algorithmus einführte, was angesichts ihrer Nähe kein Zufall ist.

Für die maßgebliche Darstellung, wer was wann fand, siehe die Problemgeschichte von Graham und Hell. Für eine strenge Behandlung mit vollständigen Beweisen der Schnitteigenschaft und beider Algorithmen ist Cormen, Leiserson, Rivest und Stein, Introduction to Algorithms, im Kapitel über minimale Spannbäume das Standardwerk. Wer wissen möchte, wie weit die Komplexität getrieben wurde, sollte das Fibonacci-Heap-Ergebnis von Fredman und Tarjan sowie Chazelles nahezu linearen Algorithmus ansehen. Die vollständigen Quellenangaben finden sich am Ende dieses Artikels.