imported>PlusMinuscule: /* Vergleich mit dem Algorithmus von Kruskal */ Pfeil am Absatzende entfernt.

2025-06-24T14:34:08Z

Vergleich mit dem Algorithmus von Kruskal: Pfeil am Absatzende entfernt.

Neue Seite

Der '''Algorithmus von Prim''' dient der Berechnung eines [[Minimal spannender Baum|minimalen Spannbaumes]] in einem [[Zusammenhang von Graphen|zusammenhängenden]], [[Ungerichteter Graph|ungerichteten]], kantengewichteten [[Graph (Graphentheorie)|Graphen]].

Der Algorithmus wurde 1930 vom tschechischen Mathematiker [[Vojtěch Jarník]] entwickelt. 1957 wurde er zunächst von [[Robert C. Prim]] und dann 1959 von [[Edsger W. Dijkstra]] wiederentdeckt. Daher wird der [[Algorithmus]] in der Literatur auch gelegentlich unter anderen Namen geführt, so etwa '''Prim-Dijkstra-Algorithmus''' oder '''Algorithmus von Jarnik, Prim und Dijkstra''', im englischen Sprachraum auch ''Jarnik’s algorithm'' oder ''DJP algorithm''.

== Beschreibung ==
[[Datei:MAZE 30x20 Prim.ogv|mini|Der Prim-Algorithmus hat viele Anwendungen, beispielsweise bei der Erzeugung dieses [[Labyrinth]]s, bei dem der Prim-Algorithmus auf einen zufällig gewichteten Gittergraphen angewendet wird.]]
Der [[Algorithmus]] beginnt mit einem trivialen [[Graph (Graphentheorie)|Graphen]] <math>T</math>, der aus einem beliebigen [[Knoten (Graphentheorie)|Knoten]] des gegebenen Graphen besteht. In jedem Schritt wird nun eine [[Kante (Graphentheorie)|Kante]] mit minimalem Gewicht gesucht, die einen weiteren Knoten mit <math>T</math> verbindet. Diese und der entsprechende Knoten werden zu <math>T</math> hinzugefügt. Das Ganze wird solange wiederholt, bis alle Knoten in <math>T</math> vorhanden sind; dann ist <math>T</math> ein minimaler Spannbaum:

* Wähle einen beliebigen Knoten als Startgraph <math>T</math>.
* Solange <math>T</math> noch nicht alle Knoten enthält:
** Wähle eine Kante <math>e</math> mit minimalem Gewicht aus, die einen noch nicht in <math>T</math> enthaltenen Knoten <math>v</math> mit <math>T</math> verbindet.
** Füge <math>e</math> und <math>v</math> dem Graphen <math>T</math> hinzu.

Der skizzierte Algorithmus wird durch folgenden [[Pseudocode]] beschrieben:

G: Graph
VG: Knotenmenge von G
w: Gewichtsfunktion für Kantenlänge
r: Startknoten (r ∈ VG)
Q: Prioritätswarteschlange
π[u]: Elternknoten von Knoten u im Spannbaum
Adj[u]: Adjazenzliste von u (alle Nachbarknoten)
wert[u]: Abstand von u zum entstehenden Spannbaum

''algorithmus_von_prim''(G,w,r)
01 Q <math>\leftarrow</math> VG ''//Initialisierung''
02 '''für alle''' u ∈ Q
03 wert[u] <math>\leftarrow</math> ∞
04 π[u] <math>\leftarrow</math> 0
05 wert[r] <math>\leftarrow</math> 0
06 '''solange''' Q ≠ <math>\varnothing</math>
07 u <math>\leftarrow</math> ''extract_min''(Q)
08 '''für alle''' v ∈ Adj[u]
09 '''wenn''' v ∈ Q und w(u,v) < wert[v]
10 '''dann''' π[v] <math>\leftarrow</math> u
11 wert[v] <math>\leftarrow</math> w(u,v)

Nachdem der [[Algorithmus]] endet, ergibt sich der [[Minimaler Spannbaum|minimale Spannbaum]] wie folgt:

:<math>T = \left(V_G, \lbrace\left(u, \pi[u]\right) | u \in V_G \backslash \lbrace r \rbrace\rbrace\right)</math>

Zum Finden der leichtesten Schnittkante kann eine [[Prioritätswarteschlange]] verwendet werden. Dabei werden vom Algorithmus insgesamt <math>|V|</math> extractMin-Operationen und <math>|E|</math> decreaseKey-Operationen ausgeführt. Mit einem [[Fibonacci-Heap]] (extractMin in amortisiert <math>O(\log |V|)</math> und decreaseKey in amortisiert <math>O(1)</math>) als [[Datenstruktur]] ergibt sich eine [[Laufzeit (Informatik)|Gesamtlaufzeit]] von <math>O(|E| + |V| \cdot \log |V|)</math>.

Die [[Schleife (Programmierung)|Schleife]] ist inhärent sequentiell, da sich die leichteste [[Kante (Graphentheorie)|Kante]] im Schnitt von <math>S</math> und <math>V \setminus S</math> mit dem Hinzufügen eines neuen [[Knoten (Graphentheorie)|Knotens]] zu <math>S</math> ändern kann. Es ist jedoch für die Korrektheit wichtig, dass immer die aktuell leichteste Kante ausgewählt wird.

Auf einer [[Parallel Random Access Machine]] mit insgesamt <math>O(|V|)</math> [[Prozessor]]en lässt sich der Zugriff auf die [[Vorrangwarteschlange|Prioritätswarteschlange]] zu konstanter Zeit beschleunigen<ref name="A_Parallel_Prio_4-21"/>, sodass sich eine [[Laufzeit (Informatik)|Gesamtlaufzeit]] in <math>O(|E|+|V|)</math> ergibt. Insgesamt bieten der [[Algorithmus von Kruskal]] und der [[Algorithmus von Borůvka]] bessere Parallelisierungsansätze.

== Beispiel ==
In diesem Beispiel wird der Ablauf des Algorithmus von Prim an einem einfachen [[Graph (Graphentheorie)|Graphen]] gezeigt. Der aktuelle [[Baum (Graphentheorie)|Baum]] <math>T</math> ist jeweils grün hervorgehoben. Alle [[Knoten (Graphentheorie)|Knoten]], die im jeweiligen Schritt über eine einzelne [[Kante (Graphentheorie)|Kante]] mit dem Graphen verbunden werden können, sind zusammen mit der jeweiligen Kante geringsten Gewichts blau hervorgehoben. Der Knoten und die Kante, die hinzugefügt werden, sind hellblau markiert.

{| class="wikitable"
|[[Datei:Prim Algorithm 0.svg|200px]]
|Dies ist der Graph, zu dem der Algorithmus von Prim einen minimalen Spannbaum berechnet. Die Zahlen bei den einzelnen Kanten geben das jeweilige Kantengewicht an.
|-
|[[Datei:Prim Algorithm 1.svg|200px]]
|Als Startknoten für den Graphen <math>T</math> wird der Knoten <math>D</math> gewählt. (Es könnte auch jeder andere Knoten ausgewählt werden.) Mit dem Startknoten können die Knoten <math>A</math>, <math>B</math>, <math>E</math> und <math>F</math> jeweils unmittelbar durch die Kanten <math>DA</math>, <math>DB</math>, <math>DE</math> und <math>DF</math> verbunden werden. Unter diesen Kanten ist <math>DA</math> diejenige mit dem geringsten Gewicht und wird deshalb zusammen mit dem Knoten <math>A</math> zum Graphen <math>T</math> hinzugefügt.
|-
|[[Datei:Prim Algorithm 2.svg|200px]]
|Mit dem bestehenden Graphen <math>T</math> kann der Knoten <math>B</math> durch die Kanten <math>AB</math> oder <math>DB</math>, der Knoten <math>E</math> durch die Kante <math>DE</math> und der Knoten <math>F</math> durch die Kante <math>DF</math> verbunden werden. Unter diesen vier Kanten ist <math>DF</math> diejenige mit dem geringsten Gewicht und wird deshalb zusammen mit dem Knoten <math>F</math> zum Graphen <math>T</math> hinzugefügt.
|-
|[[Datei:Prim Algorithm 3.svg|200px]]
|Mit dem bestehenden Graphen <math>T</math> kann der Knoten <math>B</math> durch die Kanten <math>AB</math> oder <math>DB</math>, der Knoten <math>E</math> durch die Kanten <math>DE</math> oder <math>FE</math> und der Knoten <math>G</math> durch die Kante <math>FG</math> verbunden werden. Unter diesen Kanten ist <math>AB</math> diejenige mit dem geringsten Gewicht und wird deshalb zusammen mit dem Knoten <math>B</math> zum Graphen <math>T</math> hinzugefügt.
|-
|[[Datei:Prim Algorithm 4.svg|200px]]
|Mit dem bestehenden Graphen <math>T</math> kann der Knoten <math>C</math> durch die Kante <math>BC</math>, der Knoten <math>E</math> durch die Kanten <math>BE</math>, <math>DE</math> oder <math>FE</math> und der Knoten <math>G</math> durch die Kante <math>FG</math> verbunden werden. Unter diesen Kanten ist <math>BE</math> diejenige mit dem geringsten Gewicht und wird deshalb zusammen mit dem Knoten <math>E</math> zum Graphen <math>T</math> hinzugefügt.
|-
|[[Datei:Prim Algorithm 5.svg|200px]]
|Mit dem bestehenden Graphen <math>T</math> kann der Knoten <math>C</math> durch die Kanten <math>BC</math> oder <math>EC</math> und der Knoten <math>G</math> durch die Kanten <math>EG</math> oder <math>FG</math> verbunden werden. Unter diesen Kanten ist <math>EC</math> diejenige mit dem geringsten Gewicht und wird deshalb zusammen mit dem Knoten <math>C</math> zum Graphen <math>T</math> hinzugefügt.
|-
|[[Datei:Prim Algorithm 6.svg|200px]]
|Der verbliebene Knoten <math>G</math> kann durch die Kanten <math>EG</math> oder <math>FG</math> mit dem Graphen <math>T</math> verbunden werden. Da <math>EG</math> unter diesen beiden das geringere Gewicht hat, wird sie zusammen mit dem Knoten <math>G</math> zum Graphen <math>T</math> hinzugefügt.
|-
|[[Datei:Prim Algorithm 7.svg|200px]]
|Der Graph <math>T</math> enthält jetzt alle Knoten des Ausgangsgraphen und ist ein minimaler Spannbaum dieses Ausgangsgraphen.
|}

== Effizienz und Laufzeit ==
Für eine effiziente [[Implementierung]] des Algorithmus von Prim muss man möglichst einfach eine [[Kante (Graphentheorie)|Kante]] finden, die man dem entstehenden [[Baum (Graphentheorie)|Baum]] <math>T</math> hinzufügen kann. Man benötigt also eine [[Prioritätswarteschlange]], in der alle [[Knoten (Graphentheorie)|Knoten]] gespeichert sind, die noch nicht zu <math>T</math> gehören. Alle Knoten haben einen Wert, der dem der leichtesten Kante entspricht, durch die der Knoten mit <math>T</math> verbunden werden kann. Existiert keine solche Kante, wird dem Knoten der Wert <math>\infty</math> zugewiesen. Die [[Warteschlange (Datenstruktur)|Warteschlange]] liefert nun immer einen Knoten mit dem kleinsten Wert zurück.

Die Effizienz des Algorithmus hängt infolgedessen von der Implementierung der [[Warteschlange (Datenstruktur)|Warteschlange]] ab. Bei Verwendung eines [[Fibonacci-Heap]]s ergibt sich eine optimale [[Laufzeit (Informatik)|Laufzeit]] von <math>\mathcal{O}(|E| + |V| \log |V|)</math>.

== Korrektheitsbeweis ==
Sei <math>G</math> ein [[Zusammenhängender Graph|zusammenhängender]], kantengewichteter [[Graph (Graphentheorie)|Graph]]. Bei jeder Iteration des [[Algorithmus]] muss eine [[Kante (Graphentheorie)|Kante]] gefunden werden, die einen [[Knoten (Graphentheorie)|Knoten]] in einem [[Teilgraph]]en mit einem Knoten außerhalb des Teilgraphen verbindet. Weil <math>G</math> zusammenhängend ist, gibt es immer einen [[Pfad (Graphentheorie)|Pfad]] zu jedem Knoten. Der resultierende Graph <math>T</math> des Algorithmus ist ein [[Baum (Graphentheorie)|Baum]], da die dem Baum hinzugefügte Kante und der Knoten verbunden sind.

Sei <math>T_1</math> ein [[minimaler Spannbaum]] des Graphen <math>G</math>. Wenn <math>T_1</math> gleich <math>T</math> ist, dann ist <math>T</math> ein minimaler Spannbaum.

Andernfalls sei <math>e</math> die erste Kante, die während der Konstruktion des Baums <math>T</math> hinzugefügt wird, die sich nicht im Baum <math>T_1</math> befindet, und <math>V</math> sei die Menge der Knoten, die durch die vor der Kante <math>e</math> hinzugefügten Kanten verbunden waren. Dann befindet sich ein Knoten der Kante <math>e</math> in der Menge <math>V</math> der schon verbundenen Knoten und der andere nicht. Weil der Baum <math>T_1</math> ein Spannbaum des Graphen <math>G</math> ist, gibt es im Baum <math>T_1</math> einen Pfad, der die beiden Endknoten verbindet. Wenn man den Pfad entlang fährt, muss man auf eine Kante <math>f</math> stoßen, die einen Knoten der Menge <math>V</math> mit einem Knoten verbindet, der nicht in der Menge <math>V</math> liegt. Bei der Iteration, in der die Kante <math>e</math> zu Baum <math>T</math> hinzugefügt wurde, könnte nun auch die Kante <math>f</math> hinzugefügt worden sein und sie würde anstelle der Kante <math>e</math> hinzugefügt, wenn ihr Gewicht kleiner als das Gewicht von <math>e</math> wäre, und weil die Kante <math>f</math> nicht hinzugefügt wurde, schließen wir daraus, dass ihr Gewicht mindestens so groß ist wie das Gewicht von <math>e</math>.

Der Baum <math>T_2</math> sei der Graph, der aus <math>T_1</math> durch Entfernen der Kante <math>f</math> und Hinzufügen der Kante <math>e</math> entsteht. Es ist einfach zu zeigen, dass der Baum <math>T_2</math> zusammenhängend ist, die gleiche Anzahl von Kanten wie der Baum <math>T_1</math> hat und das Gesamtgewicht seiner Kanten nicht größer als das von Baum <math>T_1</math> ist, daher ist <math>T_2</math> auch ein minimaler Spannbaum des Graphen <math>G</math> und er enthält die Kante <math>e</math> und alle Kanten, die während der Konstruktion der Menge <math>V</math> hinzugefügt wurden. Wiederholt man die bisherigen Schritte, dann erhält man schließlich einen minimalen Spannbaum des Graphen <math>G</math>, der mit dem Baum <math>T</math> identisch ist. Dies zeigt, dass <math>T</math> ein minimaler Spannbaum ist.

== Vergleich mit dem Algorithmus von Kruskal ==
Wie auch der [[Algorithmus von Kruskal]], der ebenfalls einen minimal spannenden Baum konstruiert, ist Prims Algorithmus ein [[Greedy-Algorithmus]]. Beide [[Algorithmus|Algorithmen]] beginnen mit einem [[Graph (Graphentheorie)|Graphen]] ohne Kanten und fügen in jedem Schritt eine Kante mit minimalem Gewicht hinzu. Sie unterscheiden sich vor allem darin, wie die Bildung eines [[Kreis (Graphentheorie)|Kreises]] vermieden wird.

Während der Algorithmus von Kruskal global nach möglichen Kanten mit dem kleinsten Gewicht sucht und bei der Aufnahme dieser Kanten in den Lösungsgraph die Kreisbildung aktiv vermeidet, betrachtet der Algorithmus von Prim nur Kanten, die von den Knoten der bisher konstruierten Teilknotenmenge zu Knoten der Komplementärmenge verlaufen. Da aus dieser Kantenmenge eine Kante ausgewählt wird, vermeidet der Algorithmus per Konstruktion das Auftreten von Kreisen.

Ein Vergleich der [[Laufzeit (Informatik)|Laufzeit]] der beiden [[Algorithmus|Algorithmen]] ist schwierig, da im Algorithmus von Prim die ''Knoten'' die zentrale Komplexitätsschranke bestimmen, während der Algorithmus von Kruskal auf Basis einer sortierten Kantenliste arbeitet und daher dessen Laufzeit von der Anzahl der ''Kanten'' dominiert wird.<ref>vgl. dazu {{Literatur |Autor=Ellis Horowitz, [[Sartaj Sahni]] | Titel=Fundamentals of Computer Algorithms |Hrsg=Computer Science Press |Datum=1984-09 |Seiten=174-183 |ISBN= 978-0914894223 |Sprache=en}}</ref>

== Parallele Implementierung ==
[[Datei:Distributed adjacency matrix for parallel prim.png|mini|Grafische Darstellung der Aufteilung einer [[Adjazenzmatrix]] für die Parallelisierung von Prims Algorithmus. In jeder Iteration des Algorithmus wird von jedem Prozessor sein Teil des Kostenvektors <math>C</math> aktualisiert. Hierfür wird die Reihe des neu gewählten Knotens in den zugehörigen Spalten des Prozessors betrachtet und anschließend der lokal optimale Knoten bestimmt. Die Ergebnisse aller Prozessoren werden anschließend gesammelt um den nächsten Knoten des Spannbaums zu bestimmen]]

Der Algorithmus von Prim ist grundlegend [[Sequentieller Zugriff|sequentieller]] Natur, da sich die äußere [[Schleife (Programmierung)|Schleife]] aufgrund von Datenabhängigkeiten zwischen den [[Iteration]]en nicht parallelisieren lässt. Es ist allerdings möglich, die ''extract_min'' Operation zu parallelisieren. Hierfür kann zum Beispiel eine parallele [[Implementierung]] einer [[Prioritätswarteschlange]] verwendet werden. Auf einer [[Parallel Random Access Machine]] mit insgesamt <math>O(|V|)</math> [[Prozessor]]en lässt sich der Zugriff auf die Prioritätswarteschlange zu konstanter Zeit beschleunigen<ref name="A_Parallel_Prio_4-21">{{cite journal
| last1 = Brodal
| first = Gerth Stølting
| last2 = Träff
| first2 = Jesper Larsson
| last3 = Zaroliagis
| first3 = Christos D.
| date = 1998-02-25
| title = A Parallel Priority Queue with Constant Time Operations
| journal = Journal of Parallel and Distributed Computing
| volume = 49
| issue = 1
| pages = 4–21
| language=en
| doi=10.1006/jpdc.1998.1425}}</ref>, sodass sich eine [[Laufzeit (Informatik)|Gesamtlaufzeit]] in <math>O(|E|+|V|)</math> ergibt. Alternativ können die [[Knoten (Graphentheorie)|Knoten]] zwischen mehreren Prozessoren aufgeteilt werden, sodass jeder Prozessor die eingehenden Kanten zu seinem Teil der Knoten verwaltet.<ref name="grama2003">{{cite book|title=Introduction to Parallel Computing|last1=Grama|first1=Ananth|last2=Gupta|first2=Anshul|last3=Karypis|first3=George|last4=Kumar|first4=Vipin|publisher=|year=2003|isbn=978-0-201-64865-2|location=|pages=444–446|language=en}}</ref> Dies wird in folgendem [[Pseudocode]] dargestellt.

# Weise jedem Prozessor <math>P_i</math> einen Teil <math>V_i</math> der Knoten, sowie die dazugehörigen (eingehenden) Kanten zu. Bei Verwendung einer [[Adjazenzmatrix]] entspricht dies gerade einem Teil der Spalten.
# Erstelle auf jedem Prozessor einen Vektor <math>C</math>, welcher die aktuellen Kosten für jeden Knoten in <math>V_i</math> enthält. Initialisiere diesen Vektor mit <math>\infty</math>
# Wiederhole folgende Schritte solange nicht alle Knoten im Spannbaum enthalten sind:
## Auf jedem Prozessor: bestimme den Knoten <math>v_i</math> und dazugehörige Kante <math>e_i</math> welcher den minimalen Wert in <math>C</math> besitzt (lokale Lösung).
## Bestimme aus den lokalen Lösungen den Knoten dessen Verbindung zum aktuellen Spannbaum die geringsten Kosten hat. Dies ist mithilfe einer Minimum-Reduktion über alle Prozessoren möglich.
## Teile jedem Prozessor den gewählten Knoten mithilfe eines [[Broadcast]] mit.
## Füge den neuen Knoten sowie die dazugehörige Kante (es sei denn es handelt sich um den ersten Knoten) dem Spannbaum hinzu
## Auf jedem Prozessor: aktualisiere <math>C</math> indem die Kanten des neu eingefügten Knotens zu dem eigenen Knotenset betrachtet werden.

Diese Variation von Prims Algorithmus lässt sich sowohl auf [[Verteiltes System|Verteilten Systemen]],<ref name="grama2003" /> auf [[Shared Memory]] Systemen<ref>{{Literatur |Autor=Michael J. Quinn, Narsingh Deo |Titel=Parallel Graph Algorithms |DOI=10.1145/2514.2515 |Sammelwerk=[[Association for Computing Machinery|ACM]] Computing Surveys (CSUR) |Nummer=16 |Band=3 |Seiten=319–348 |Datum=1984 |Sprache=en}}</ref>, sowie auf [[Grafikprozessor]]en<ref>{{Cite journal|last1=Wang|first1=Wei|last2=Huang|first2=Yongzhong|last3=Guo|first3=Shaozhong|date=2011|title=Design and Implementation of GPU-Based Prim’s Algorithm|journal=International Journal of Modern Education and Computer Science (IJMECS)|volume=3|issue=4|language=en|doi=10.5815/ijmecs.2011.04.08}}</ref> implementieren. Die [[Laufzeit (Informatik)|Laufzeit]] beträgt dabei
:<math>O\left(\frac{|V|^2}{|P|}\right) + O(|V| \log |P|)</math>,
da in jeder der <math>|V|</math> Iterationen des Algorithmus jeweils <math>\tfrac{|V|}{|P|}</math> Einträge betrachtet werden müssen. Zusätzlich wird angenommen, dass sowohl die Minimum-Reduktion als auch der [[Broadcast]] in <math>O(\log |P|)</math> Zeit durchgeführt werden können.<ref name="grama2003" />

Als weitere Alternative für eine parallele Umsetzung von Prims Algorithmus wurde eine Variante präsentiert, in welcher der sequentielle Algorithmus parallel von verschiedenen Startknoten aus ausgeführt wird.<ref>{{Cite journal|last=Setia|first=Rohit|last2=Nedunchezhian |first2=Arun |last3=Balachandran |first3=Shankar |date=2009|title=A new parallel algorithm for minimum spanning tree problem|journal=Proc. International Conference on High Performance Computing (HiPC)|language=en|url=https://www.hipc.org/hipc2009/documents/HIPCSS09Papers/1569250351.pdf |format=PDF}}</ref> Im Allgemeinen eignen sich andere [[Minimal spannender Baum|MST]] Algorithmen, wie beispielsweise der [[Algorithmus von Borůvka]], jedoch besser für eine Parallelisierung.

== Programmierung ==
Das folgende Beispiel in der [[Programmiersprache]] [[C-Sharp|C#]] zeigt die Implementierung des Algorithmus von Prim. Bei der Ausführung des Programms wird die [[Methode (Programmierung)|Methode]] ''Main'' verwendet, die die Kanten und die [[Abstand|Abstände]] auf der Konsole ausgibt. Die [[Matrix (Mathematik)|Matrix]] für die Abstände wird in einem zweidimensionalen [[Feld (Datentyp)|Array]] vom [[Datentyp]] [[Integer (Datentyp)|Integer]] gespeichert.<ref>{{Internetquelle |url=https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/ |titel=Prim’s Algorithm for Minimum Spanning Tree (MST) |werk=geeksforgeeks |datum=2024-12-05 |abruf=2025-01-29 |sprache=en}}</ref>
<syntaxhighlight lang="c#">
using System;

class Program
{
// Diese Methode gibt den Index des Knotens mit dem minimalen Abstand zum Teilgraphen zurück
static int GetMinimumIndex(int[] distances, bool[] includedNodes)
{
int minimumDistance = int.MaxValue;
int minimumIndex = -1;
for (int i = 0; i < distances.Length; i++)
{
if (!includedNodes[i] && distances[i] < minimumDistance)
{
minimumDistance = distances[i];
minimumIndex = i;
}
}
return minimumIndex;
}

// Diese Methode verwendet den Algorithmus von Prim und gibt den minimalen Spannbaum zurück
static void Prim(int[,] distanceMatrix, int numberOfNodes, out int[] parent, out int[] distances)
{
parent = new int[numberOfNodes];
distances = new int[numberOfNodes];
bool[] includedNodes = new bool[numberOfNodes];
for (int i = 0; i < numberOfNodes; i++)
{
distances[i] = int.MaxValue;
includedNodes[i] = false;
}
distances[0] = 0;
parent[0] = -1;
for (int i = 0; i < numberOfNodes - 1; i++)
{
int minimumIndex = GetMinimumIndex(distances, includedNodes);
includedNodes[minimumIndex] = true;
for (int j = 0; j < numberOfNodes; j++)
{
if (distanceMatrix[minimumIndex, j] != 0 && !includedNodes[j] && distanceMatrix[minimumIndex, j] < distances[j])
{
parent[j] = minimumIndex;
distances[j] = distanceMatrix[minimumIndex, j];
}
}
}
}

// Hauptmethode, die das Programm ausführt
public static void Main()
{
int[, ] distanceMatrix = new int[,] { {0, 2, 0, 6, 0},
{2, 0, 3, 8, 5},
{0, 3, 0, 0, 7},
{6, 8, 0, 0, 9},
{0, 5, 7, 9, 0} }; // Deklariert und initialisiert die Matrix mit den Abständen zwischen allen Punkten als zweidimensionales Array vom Typ int
int[] parent;
int[] distances;
int numberOfNodes = 5;
Prim(distanceMatrix, numberOfNodes, out parent, out distances);
Console.WriteLine("Kante\tAbstand"); // Ausgabe auf der Konsole
for (int i = 1; i < numberOfNodes; i++)
{
Console.WriteLine(parent[i] + " - " + i + "\t" + distanceMatrix[i, parent[i]]); // Ausgabe auf der Konsole
}

Console.ReadLine();
}
}
</syntaxhighlight>

== Literatur ==
* {{Literatur |Autor=[[Robert C. Prim]] |Titel=Shortest connection networks and some generalisations |Sammelwerk=Bell System Technical Journal |Nummer=6 |Band=36 |Datum=1957-11 |DOI=10.1002/j.1538-7305.1957.tb01515.x |Seiten=1389–1401 |Sprache=en}}
* {{Literatur |Autor=David Cheriton, [[Robert Tarjan]] |Titel=Finding Minimum Spanning Trees |Sammelwerk=SIAM Journal on Computing |Band=5 |Nummer=4 |Datum=1976-12 |Seiten=724–741 |DOI=10.1137/0205051 |Sprache=en}}
* {{Literatur |Autor=Ellis Horowitz, [[Sartaj Sahni]] | Titel=Fundamentals of Computer Algorithms |Hrsg=Computer Science Press |Datum=1984-09 |Seiten=174-183 |ISBN= 978-0914894223 |Sprache=en}}

== Weblinks ==
{{Commonscat|Prim's algorithm|Algorithmus von Prim|audio=0}}
{{Wikibooks|Algorithmensammlung: Graphentheorie: Algorithmus von Prim|Algorithmus von Prim|suffix=Implementierungen in der Algorithmensammlung}}
* {{Webarchiv |url=http://www-m9.ma.tum.de/material/de/mst-prim/ |wayback=20150614233605 |text=Reza Sefidgar: Interaktives Applet zur Lernen, Ausprobieren und Demonstrieren des Algorithmus}}
* {{Webarchiv |url=http://www.unf.edu/~wkloster/foundations/PrimApplet/PrimApplet.htm |wayback=20211228013007 |text=Java-Applet zur Schritt-für-Schritt-Visualisierung}}
* {{Webarchiv |url=http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo21.php |wayback=20160127080051 |text=''Anschauliche Darstellung des Algorithmus im Rahmen des Informatikjahres, 2006''}}

== Einzelnachweise ==
<references />

[[Kategorie:Graphsuchalgorithmus|Prim, Algorithmus von]]
[[Kategorie:Optimierungsalgorithmus|Prim, Algorithmus von]]
[[Kategorie:Wikipedia:Artikel mit Video]]

Algorithmus von Prim - Versionsgeschichte

imported>PlusMinuscule: /* Vergleich mit dem Algorithmus von Kruskal */ Pfeil am Absatzende entfernt.