Nebenläufige Programmierung mit Java

19 Minimal aufspannende Bäume

Das folgende Beispiel stammt aus dem Bereich der Graphentheorie, die ein sehr großes Anwendungspotenzial hat. Weitere Informationen zu dem Gebiet findet man z. B. in [31, 50]. Der im Folgenden vorgestellte Algorithmus von Prim¹ berechnet einen minimalen Spannbaum in einem zusammenhängenden, ungerichteten Graphen, wobei die Kanten gewichtet sind. Abbildung 19-1 zeigt ein Beispiel eines solchen Graphen.

Abbildung 19-1: Ein schlichter, zusammenhängender, ungerichteter Graph mit Kantengewichten

19.1 Graphen und Spannbäume

Für Graphen existieren verschiedene Möglichkeiten, wie diese in Datenstrukturen abgebildet werden ...