Introduction

Willkommen zum letzten Kurs in der Reihe Graphenalgorithmen! Wie Kruskal erstellt der Algorithmus von Prim einen minimalen Spannbaum: die günstigste Menge an Kanten, die jeden Knoten ohne einen Zyklus verbindet. Die beiden Algorithmen erreichen dasselbe Ergebnis auf unterschiedlichen Wegen.

Prim lässt den Baum von einem Startknoten aus nach außen wachsen. In jedem Schritt fügt er die günstigste Kante hinzu, die den Baum mit einem Knoten verbindet, der noch nicht darin enthalten ist.

Der Graph ist ungerichtet und gewichtet, gegeben als n (Knoten 0 bis n - 1) und edges, ein flaches Array von Tripeln [u0, v0, w0, ...] für eine ungerichtete Kante u - v mit dem Gewicht w. Wir beginnen bei Knoten 0.

Schließen wir die Reihe ab!