Notizen

Prim-Algorithmus

tagsgraphentheorie

Der Prim-Algorithmus ist ein Greedy-Algorithmus zur Bestimmung eines Spannbaums.

Idee

  • Start an einem beliebigen Knoten
  • Schritt für schritt wählen wir die billigste Kante, einen neuen Knoten verbindet
    • Am Anfang ist das die leichteste Kante vom Startknoten
    • Danach ist es die leichteste Kante von allen bereits verbundenen Knoten zu einem neuen noch nicht verbundenen Knoten

Vorgangsweise anschaulich

https://www.youtube.com/watch?v=BjtCnyWnt7U

Zyklen

Da wir nur Knoten wählen, die noch nicht verbunden sind, können - anders als beim Kruskal-Algorithmus - keine Zyklen entstehen.

Implementierung

In der Implementierung kann man nicht einfach nach der billigsten Kante “suchen”, das würde zu lange dauern. Man gibt stattdessen jedem Knoten den Wert mit dem er aktuell billigst angebunden werden kann, diese Werte können dann effizient in einem Min-Heap verwaltet werden. Dieser würde uns dann direkt den kleinsten Wert liefern.

Vorgehensweise

  1. Der Startknoten hat bekannte Kosten von 0, alle anderen unendlich
  2. Wir schauen vom Startknoten, welche Knoten von ihm aus erreichbar sind.
    • Ist der Knoten noch nicht im Spannbaum und die Kosten dahin billiger als die uns bekannten, aktualisieren wir sie.
  3. Wir suchen uns jetzt den Knoten, der unseres Wissens nach am billigsten anbindbar ist und binden ihn an.
  4. Von dem schauen wir uns wieder an, welche Knoten verbunden sind:
    • Ist der Knoten noch nicht im Spannbaum und die Kosten dahin billiger als die uns bekannten, aktualisieren wir sie.
  5. Die Schritte 3-4 werden wiederholt, bis alle Knoten angebunden sind.

Pseudocode

Sei ein Graph, eine Gewichtung und ein Startknoten.

  • Algorithmus MST_Prim(, , ):
    • Für jeden Knoten : Initialisierung
      • .key =
      • .pred = NULL Um den Spannbaum später dann auch auszulesen. Kann sich während des Algorithmus ändern.
    • .key = 0 Starten mit v0, ist mit 0 Kosten anbindbar
    • = BuildHeap() Min-Heap über Key. Hier steht v0 mit 0 ganz oben, alle anderen stehen mit unendlich drunter
    • Solange nicht leer:
      • = .extractMin() Knoten mit leichtester Kante u
      • Für jeden Knoten AdjList[] Iteriere durch jeden seiner verbundenen Knoten v
        • Falls und .key: Falls der Knoten noch nicht mit dem Spannbaum verbunden ist und die Kante zu dem Knoten billiger ist als die uns bereits bekannte
          • .decreaseKey( Aktualisiere das billigste Gewicht im uns bekannten Verzeichnis (Heap). decreaseKey = updaten mit heapify
          • .pred = Speichere den Vorgänger falls wir diesen Knoten als nächstes wählen. Mit dieser Variable bauen wir später den Spannbaum auf.

Laufzeit

Insgesamt ergibt sich eine Laufzeit von:

Werden Fibonacci-Heaps verwendet, erzielt man eine etwas bessere Laufzeit:

Backlinks