Direkt zum Inhalt

Lexikon der Mathematik: Prim, Algorithmus von

liefert in einem zusammenhängenden bewerteten Graphen G mit der Komplexität O(|E(G)|2) einen minimal spannenden Baum von G.

Bei diesem Algorithmus aus dem Jahre 1957 läßt man im Graphen G einen Baum wie folgt wachsen. Ausgehend von einer beliebigen Ecke des Graphen wähle man eine Kante k1K(G) minimaler Länge, die mit dieser Ecke inzidiert. Hat man die Kanten k1, k2,…, ki bereits gewählt, so wähle man eine Kante ki+1 minimaler Länge, so daß ki+1 mit einer Ecke des induzierten Baumes \begin{eqnarray}{T}_{k}\ =\ G\ [\{{k}_{1},\ {k}_{2},\ \ldots,\ {k}_{i}\}]\end{eqnarray} und mit einer Ecke aus E(G)−E(Tk) inzidiert. Nach |E(G)| − 1 solcher Schritte gelangt man dann zu einem minimal spannenden Baum von G.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos