Minimaler Spannbaum nach Prim (Algorithmus 4.7)

So geht’s: Beim Öffnen läuft der Testclient mit tinyEWG, in derselben Lage wie in Abbildung 4.61. Die Zahlen an den Kanten sind die Gewichte. Jede Runde beginnt mit pq.delMin(): Der Knoten mit der leichtesten Verbindung zum Baum kommt dazu, seine Kante ist dick rot. Danach prüft visit alle Kanten dieses Knotens, die gerade geprüfte ist blau gestrichelt. Grün sind die Knoten im Baum, schwarz die Kanten des minimalen Spannbaums. Rot umrandet sind die Knoten in der Warteschlange, ihre rote Kante ist die bisher beste Verbindung zum Baum. Kanten zwischen zwei Baumknoten werden blass. Rechts stehen edgeTo[] und distTo[] wie in der Abbildung, darunter die indizierte Vorrangwarteschlange: oben der Heap, unten das Zusatzarray qp[], über das change die Position eines Knotens im Heap sofort findet. Im Protokoll sammeln sich die Tabellen der Abbildung. „Zufallsgraph“ erzeugt einen neuen zusammenhängenden Graphen, „↺ Neu starten“ springt zurück zu tinyEWG.

Erklärung

Minimaler Spannbaum nach Prim, Eager-Version (Algorithmus 4.7), Klasse PrimMST. Abschnitt 4.3, kantengewichtete Graphen.

Das Problem: Ungerichteter Graph, jede Kante hat ein Gewicht (Kosten, Länge). Gesucht ist ein minimaler Spannbaum (MST): eine Auswahl von Kanten, die alle Knoten verbindet, keinen Zyklus enthält (also ein Baum mit V − 1 Kanten) und das kleinstmögliche Gesamtgewicht hat. Beispiele: Stromnetz, Leitungen, Straßen so legen, dass alles verbunden ist und am wenigsten kostet.

Grundlage: die Schnitteigenschaft. Teilt man die Knoten in zwei Gruppen, gehört die leichteste Kante, die beide Gruppen verbindet (kreuzende Kante), immer zum MST.

Prims Idee: Baum ab Knoten 0 wachsen lassen. Die Gruppen sind „im Baum“ und „noch nicht im Baum“. In jedem Schritt die leichteste kreuzende Kante nehmen und ihren Nicht-Baum-Knoten hinzufügen. Nach V − 1 Schritten ist der Baum fertig. Nach der Schnitteigenschaft ist jede so gewählte Kante richtig.

Der Code:

• marked[v]: v ist schon im Baum.
• edgeTo[w]: die bisher beste (leichteste) Kante vom Baum zu w.
• distTo[w]: deren Gewicht. Anfangs unendlich, für Knoten 0 null.
• pq: eine indizierte Vorrangwarteschlange (IndexMinPQ). Index ist der Knoten, Schlüssel sein distTo. Sie enthält die Nicht-Baum-Knoten, die schon eine Verbindung zum Baum haben.
• Hauptschleife: Knoten mit kleinstem distTo herausnehmen (delMin) und mit visit in den Baum holen.
• visit(v): v markieren. Für jede Kante v–w: Ist w schon im Baum, überspringen. Ist die Kante leichter als die bisher beste Verbindung zu w, dann edgeTo[w] und distTo[w] aktualisieren und w in der Warteschlange einfügen bzw. seinen Schlüssel senken (change).

Indizierte Vorrangwarteschlange: Wie der Heap aus [12], aber man kann zusätzlich über den Index den Schlüssel eines bestimmten Elements ändern und abfragen, ob es enthalten ist. Dafür führt sie intern ein Zusatzarray, das zu jedem Index die Position im Heap kennt.

Lazy vs. Eager:

Satz N: Die Eager-Version braucht Zusatzspeicher proportional zu V und im schlimmsten Fall Zeit proportional zu E log V.

Hinweise:

• Ist der Graph nicht zusammenhängend, liefert der Code nur den Spannbaum der Komponente von 0 (einen Spannwald gäbe es mit einem Start pro Komponente, wie in [32]).
• distTo ist hier das Gewicht einer einzelnen Kante zum Baum, nicht eine Pfadlänge. Genau an diesem Punkt unterscheidet sich später Dijkstra (Algorithmus 4.9), der sonst fast gleich aussieht.
• Als Nächstes kommt Kruskal (Algorithmus 4.8): gleiche Aufgabe, aber Kanten global nach Gewicht sortiert und mit Union-Find [21] auf Zyklen geprüft.

Stand Kapitel 4:

• Algorithmus 4.1: Tiefensuche für Pfade [30]
• Algorithmus 4.2: Breitensuche für kürzeste Pfade [31]
• Algorithmus 4.3: Zusammenhangskomponenten [32]
• Algorithmus 4.4: Erreichbarkeit in Digraphen [33]
• Algorithmus 4.5: Topologisches Sortieren [34]
• Algorithmus 4.6: Starke Komponenten nach Kosaraju [35], [36]
• Algorithmus 4.7: Minimaler Spannbaum nach Prim [37]