Algorithmus von Prim

Der Algorithmus von Prim dient der Berechnung eines minimalen Spannbaumes in einem zusammenhängenden, ungerichteten, kantengewichteten 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

Der Prim-Algorithmus hat viele Anwendungen, beispielsweise bei der Erzeugung dieses Labyrinths, bei dem der Prim-Algorithmus auf einen zufällig gewichteten Gittergraphen angewendet wird.

Der Algorithmus beginnt mit einem trivialen Graphen <math>T</math>, der aus einem beliebigen Knoten des gegebenen Graphen besteht. In jedem Schritt wird nun eine 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
V_G: Knotenmenge von G
w: Gewichtsfunktion für Kantenlänge
r: Startknoten (r ∈ V_G)
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> V_G   //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 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 Gesamtlaufzeit von <math>O(|E| + |V| \cdot \log |V|)</math>.

Die Schleife ist inhärent sequentiell, da sich die leichteste Kante im Schnitt von <math>S</math> und <math>V \setminus S</math> mit dem Hinzufügen eines neuen 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> Prozessoren lässt sich der Zugriff auf die Prioritätswarteschlange zu konstanter Zeit beschleunigen<ref name="A_Parallel_Prio_4-21"/>, sodass sich eine 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 Graphen gezeigt. Der aktuelle Baum <math>T</math> ist jeweils grün hervorgehoben. Alle Knoten, die im jeweiligen Schritt über eine einzelne 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.

Datei:Prim Algorithm 0.svg	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	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	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	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	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	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	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	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 finden, die man dem entstehenden Baum <math>T</math> hinzufügen kann. Man benötigt also eine Prioritätswarteschlange, in der alle 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 liefert nun immer einen Knoten mit dem kleinsten Wert zurück.

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

Korrektheitsbeweis

Sei <math>G</math> ein zusammenhängender, kantengewichteter Graph. Bei jeder Iteration des Algorithmus muss eine Kante gefunden werden, die einen Knoten in einem Teilgraphen mit einem Knoten außerhalb des Teilgraphen verbindet. Weil <math>G</math> zusammenhängend ist, gibt es immer einen Pfad zu jedem Knoten. Der resultierende Graph <math>T</math> des Algorithmus ist ein 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 Algorithmen beginnen mit einem 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 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 der beiden 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 {{#invoke:Vorlage:Literatur|f}}</ref>

Parallele Implementierung

Datei:Distributed adjacency matrix for parallel prim.png

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 Natur, da sich die äußere Schleife aufgrund von Datenabhängigkeiten zwischen den Iterationen 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> Prozessoren lässt sich der Zugriff auf die Prioritätswarteschlange zu konstanter Zeit beschleunigen<ref name="A_Parallel_Prio_4-21">{{#invoke:Vorlage:Literatur|f}}{{#if:

       | {{#if: Vorlage:Cite book/ParamBool
               | Vorlage:Toter Link/archivebot
               | Vorlage:Webarchiv/archiv-bot
         }}
  }}{{#invoke:TemplatePar|check
   |all    = title=
   |opt    = vauthors= author= author1= authorlink= author-link= author-link1= author1-link= author2= author3= author4= author5= author6= author7= author8= author9= editor= last= first= last1= first1= last2= first2= last3= first3= last4= first4= last5= first5= last6= first6= last7= first7= last8= first8= last9= first9= last10= first10= last11= first11= last12= first12= last13= first13= last14= first14= last15= first15= others= script-title= trans-title= date= year= volume= issue= number= series= page= pages= at= issn= arxiv= bibcode= doi= pmid= pmc= jstor= oclc= id= url= url-status= format= access-date= archive-date= archive-url= archivebot= offline= location= publisher= language= quote= work= journal= newspaper= magazine= periodical=  name-list-style= url-access= doi-access= display-authors= via= s2cid= mr= type= citeseerx=  accessdate= archivedate= archiveurl= coauthors= month= day= last16= first16= last17= first17= last18= first18= last19= first19= last20= first20= last21= first21= last22= first22= last23= first23= last24= first24= last25= first25= last26= first26= last27= first27= last28= first28= last29= first29= last30= first30= last31= first31=
   |cat      = Wikipedia:Vorlagenfehler/Vorlage:Cite journal
   |errNS    = 0
   |template = Vorlage:Cite journal
   |format   = @@@
   |preview  = 1
  }}Vorlage:Cite book/URL{{#if:  | Vorlage:Cite book/Meldung }}{{#if:        | Vorlage:Cite book/Meldung }}{{#if: Journal of Parallel and Distributed Computing
     || Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
        | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
       | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}Vorlage:Cite book/Meldung2{{#ifexpr: 0{{#ifeq:^^|^^||+1}}{{#ifeq:Brodal|^^||+1}}{{#ifeq:^^|^^||+1}}{{#ifeq:^^|^^||+1}} > 1
    | Vorlage:Cite book/Meldung
  }}</ref>, sodass sich eine Gesamtlaufzeit in <math>O(|E|+|V|)</math> ergibt. Alternativ können die Knoten zwischen mehreren Prozessoren aufgeteilt werden, sodass jeder Prozessor die eingehenden Kanten zu seinem Teil der Knoten verwaltet.<ref name="grama2003">{{#invoke:Vorlage:Literatur|f}}{{#if:

| {{#if: Vorlage:Cite book/ParamBool | Vorlage:Toter Link/archivebot | Vorlage:Webarchiv/archiv-bot }}

  }}{{#invoke:TemplatePar|check

|all = title= |opt = vauthors= author= author-link= authorlink= author1= author-link1= author1-link= first= last= first1= last1= first2= last2= author2= first3= last3= author3= first4= last4= author4= first5= last5= author5= first6= last6= author6= first7= last7= author7= first8= last8= author8= others= coauthors= script-title= trans-title= orig-date= orig-year= chapter= chapter-url= editor= editor-first= editor-last= editor-first1= editor-last1= editor-first2= editor-last2= editor-first3= editor-last3= editor-link= editor-link1= language= format= others= series= issue= number= edition= volume= publisher= location= date= year= isbn= page= at= pages= arxiv= doi= jstor= bibcode= pmc= pmid= lccn= oclc= id= url= url-status= access-date= accessdate= archive-url= archiveurl= archive-date= archivedate= quote= url-access= ref= coauthors= origyear= archivebot= offline= |cat = Wikipedia:Vorlagenfehler/Vorlage:Cite book |errNS = 0 |template = Vorlage:Cite book |format = @@@ |preview = 1

  }}Vorlage:Cite book/URLVorlage:Cite book/Meldung2{{#if: Vorlage:Cite book/ParamBool
    | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool

| Vorlage:Cite book/Meldung

  }}{{#if: Vorlage:Cite book/ParamBool

| Vorlage:Cite book/Meldung

  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool

| Vorlage:Cite book/Meldung

  }}{{#if: Vorlage:Cite book/ParamBool

| Vorlage:Cite book/Meldung

  }}{{#if: Vorlage:Cite book/ParamBool

| Vorlage:Cite book/Meldung

  }}{{#if:  Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:Grama|^^||+1}}{{#ifeq:^^|^^||+1}}{{#ifeq:^^|^^||+1}} > 1
    | Vorlage:Cite book/Meldung
  }}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:^^|^^||+1}} > 1
    | Vorlage:Cite book/Meldung
  }}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:444–446|^^||+1}} > 1
    | Vorlage:Cite book/Meldung
  }}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:^^|^^||+1}} > 1
    | Vorlage:Cite book/Meldung
  }}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:^^|^^||+1}} > 1
    | Vorlage:Cite book/Meldung
  }}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:^^|^^||+1}} > 1
    | Vorlage:Cite book/Meldung
  }}</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:
1. 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).
2. 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.
3. Teile jedem Prozessor den gewählten Knoten mithilfe eines Broadcast mit.
4. Füge den neuen Knoten sowie die dazugehörige Kante (es sei denn es handelt sich um den ersten Knoten) dem Spannbaum hinzu
5. 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 Verteilten Systemen,<ref name="grama2003" /> auf Shared Memory Systemen<ref>{{#invoke:Vorlage:Literatur|f}}</ref>, sowie auf Grafikprozessoren<ref>{{#invoke:Vorlage:Literatur|f}}{{#if:

       | {{#if: Vorlage:Cite book/ParamBool
               | Vorlage:Toter Link/archivebot
               | Vorlage:Webarchiv/archiv-bot
         }}
  }}{{#invoke:TemplatePar|check
   |all    = title=
   |opt    = vauthors= author= author1= authorlink= author-link= author-link1= author1-link= author2= author3= author4= author5= author6= author7= author8= author9= editor= last= first= last1= first1= last2= first2= last3= first3= last4= first4= last5= first5= last6= first6= last7= first7= last8= first8= last9= first9= last10= first10= last11= first11= last12= first12= last13= first13= last14= first14= last15= first15= others= script-title= trans-title= date= year= volume= issue= number= series= page= pages= at= issn= arxiv= bibcode= doi= pmid= pmc= jstor= oclc= id= url= url-status= format= access-date= archive-date= archive-url= archivebot= offline= location= publisher= language= quote= work= journal= newspaper= magazine= periodical=  name-list-style= url-access= doi-access= display-authors= via= s2cid= mr= type= citeseerx=  accessdate= archivedate= archiveurl= coauthors= month= day= last16= first16= last17= first17= last18= first18= last19= first19= last20= first20= last21= first21= last22= first22= last23= first23= last24= first24= last25= first25= last26= first26= last27= first27= last28= first28= last29= first29= last30= first30= last31= first31=
   |cat      = Wikipedia:Vorlagenfehler/Vorlage:Cite journal
   |errNS    = 0
   |template = Vorlage:Cite journal
   |format   = @@@
   |preview  = 1
  }}Vorlage:Cite book/URL{{#if:  | Vorlage:Cite book/Meldung }}{{#if:        | Vorlage:Cite book/Meldung }}{{#if: International Journal of Modern Education and Computer Science (IJMECS)
     || Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
        | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
       | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}Vorlage:Cite book/Meldung2{{#ifexpr: 0{{#ifeq:^^|^^||+1}}{{#ifeq:Wang|^^||+1}}{{#ifeq:^^|^^||+1}}{{#ifeq:^^|^^||+1}} > 1
    | Vorlage:Cite book/Meldung
  }}</ref> implementieren. Die 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>{{#invoke:Vorlage:Literatur|f}}{{#if:

       | {{#if: Vorlage:Cite book/ParamBool
               | Vorlage:Toter Link/archivebot
               | Vorlage:Webarchiv/archiv-bot
         }}
  }}{{#invoke:TemplatePar|check
   |all    = title=
   |opt    = vauthors= author= author1= authorlink= author-link= author-link1= author1-link= author2= author3= author4= author5= author6= author7= author8= author9= editor= last= first= last1= first1= last2= first2= last3= first3= last4= first4= last5= first5= last6= first6= last7= first7= last8= first8= last9= first9= last10= first10= last11= first11= last12= first12= last13= first13= last14= first14= last15= first15= others= script-title= trans-title= date= year= volume= issue= number= series= page= pages= at= issn= arxiv= bibcode= doi= pmid= pmc= jstor= oclc= id= url= url-status= format= access-date= archive-date= archive-url= archivebot= offline= location= publisher= language= quote= work= journal= newspaper= magazine= periodical=  name-list-style= url-access= doi-access= display-authors= via= s2cid= mr= type= citeseerx=  accessdate= archivedate= archiveurl= coauthors= month= day= last16= first16= last17= first17= last18= first18= last19= first19= last20= first20= last21= first21= last22= first22= last23= first23= last24= first24= last25= first25= last26= first26= last27= first27= last28= first28= last29= first29= last30= first30= last31= first31=
   |cat      = Wikipedia:Vorlagenfehler/Vorlage:Cite journal
   |errNS    = 0
   |template = Vorlage:Cite journal
   |format   = @@@
   |preview  = 1
  }}Vorlage:Cite book/URL{{#if:  | Vorlage:Cite book/Meldung }}{{#if:        | Vorlage:Cite book/Meldung }}{{#if: Proc. International Conference on High Performance Computing (HiPC)
     || Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
        | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
       | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}Vorlage:Cite book/Meldung2{{#ifexpr: 0{{#ifeq:Setia|^^||+1}}{{#ifeq:^^|^^||+1}}{{#ifeq:^^|^^||+1}}{{#ifeq:^^|^^||+1}} > 1
    | Vorlage:Cite book/Meldung
  }}</ref> Im Allgemeinen eignen sich andere MST Algorithmen, wie beispielsweise der Algorithmus von Borůvka, jedoch besser für eine Parallelisierung.

Programmierung

Das folgende Beispiel in der Programmiersprache C# zeigt die Implementierung des Algorithmus von Prim. Bei der Ausführung des Programms wird die Methode Main verwendet, die die Kanten und die Abstände auf der Konsole ausgibt. Die Matrix für die Abstände wird in einem zweidimensionalen Array vom Datentyp Integer gespeichert.<ref>{{#if:|{{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|Vorlage:FormatDate/Wartung/Error}}| |}}}}{{#if:|{{{autor}}}: }}{{#if:|{{#if:Prim’s Algorithm for Minimum Spanning Tree (MST)|[{{#invoke:Vorlage:Internetquelle|archivURL|1={{#invoke:URLutil|getNormalized|1={{{archiv-url}}}}}}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=Prim’s Algorithm for Minimum Spanning Tree (MST)}}]{{#if:| ({{{format}}})}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}|{{#if:https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/%7C{{#if:{{#invoke:TemplUtl%7Cfaculty%7C}}%7C{{#invoke:Vorlage:Internetquelle%7CTitelFormat%7Ctitel={{#invoke:WLink%7CgetEscapedTitle%7C1=Prim’s Algorithm for Minimum Spanning Tree (MST)}}}}|[{{#invoke:URLutil|getNormalized|1=https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#invoke:WLink|getEscapedTitle|1=Prim’s Algorithm for Minimum Spanning Tree (MST)}}}}]}}{{#if:| ({{{format}}}{{#if:geeksforgeeks2024-12-05{{#if: 2025-01-29 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}

          | )
          | {{#if:{{#ifeq:en|de||{{#if:en|1}}}}| ; 
              | )}}}}}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}}}{{#if:https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/}}%7C%7C URL ungültig}}}}{{#if:Prim’s Algorithm for Minimum Spanning Tree (MST)|{{#if:{{#invoke:WLink|isValidLinktext|1=Prim’s Algorithm for Minimum Spanning Tree (MST)|lines=0}}|| Linktext ungültig}}}}{{#if: geeksforgeeks| In: {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=geeksforgeeks}}}}{{#if: | {{{hrsg}}}{{#if: 2024-12-05|,|{{#if: 2025-01-29 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: 2024-12-05| {{#if:{{#invoke:DateTime|format|2024-12-05|noerror=1}}
            |{{#invoke:DateTime|format|2024-12-05|T._Monat JJJJ}}
            |{{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, datum=2024-12-05|class=Zitationswartung}} }}{{#if: |,|{{#if: 2025-01-29 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | S. {{{seiten}}}{{#if: |,|{{#if: 2025-01-29 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: {{#invoke:TemplUtl|faculty|}}| {{#if:2024-12-05|{{#if:|archiviert|ehemals}}|{{#if:|Archiviert|Ehemals}}}} {{#if:|vom|im}} Vorlage:Referrer{{#if:{{#invoke:TemplUtl|faculty|}}| (nicht mehr online verfügbar)}}{{#if: | am {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|Vorlage:FormatDate/Wartung/Error}}|{{{archiv-datum}}}{{#if:14090||(?)}}}}}}{{#if: 2025-01-29|;}}}}{{#if: 2025-01-29| {{#if:2024-12-05{{#invoke:TemplUtl|faculty|}}|abgerufen|Abgerufen}} {{#switch: {{#invoke:Str|len| {{#invoke:DateTime|format| 2025-01-29 |ISO|noerror=1}} }}
       |4=im Jahr
       |7=im
       |10=am
       |#default={{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, abruf=2025-01-29|class=Zitationswartung}} }} {{#invoke:DateTime|format|2025-01-29|T._Monat JJJJ}}
    | {{#invoke:TemplUtl|failure|1=Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}} Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}}{{#if:{{#ifeq:en|de||{{#if:en|1}}}}|{{#if:geeksforgeeks2024-12-05{{#if: 2025-01-29 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
       |  (
       | {{#if: | |  (}}
       }}{{#ifeq:{{#if:en|en|de}}|de||
          {{#invoke:Multilingual|format|en|slang=!|split=[%s,]+|shift=m|separator=, }}}}{{#if: |{{#ifeq:{{#if:en|en|de}}|de||, }}{{{kommentar}}}}})}}{{#if: 2024-12-05{{#if: 2025-01-29 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}} }}en|{{#if: |: {{
 #if: 
 | „{{
     #ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | Vorlage:Str trim
     | {{#invoke:Vorlage:lang|flat}}
     }}“
 | {{#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | „Vorlage:Str trim“
     | {{#invoke:Text|quote
         |1={{#if: 
              | {{#invoke:Vorlage:lang|flat}}
              | {{#invoke:Vorlage:lang|flat}} }}
         |2={{#if: {{#invoke:TemplUtl|faculty|}}|de-CH|de}}
         |3=1}} }}

}}{{#if:

   |  (<templatestyles src="Person/styles.css" />{{#if:  | :  }}{{#if:  | , deutsch: „“ }})
   | {{#if: 
       |  ({{#if:  | , deutsch: „“ }})
       | {{#if:  |  (deutsch: „“) }}
 }}

}}{{#if: {{{zitat}}}

   | {{#if: 
       | {{#if: {{{zitat}}}
           | Vorlage:": Text= und 1= gleichzeitig, bzw. Pipe zu viel }} }}
   | Vorlage:": Text= fehlt }}{{#if:  | {{#if: {{#invoke:Text|unstrip|{{{ref}}}}}
             | Vorlage:": Ungültiger Wert: ref=
             | {{{ref}}} }}

}}|.{{#if:{{#invoke:TemplUtl|faculty|}}|{{#if:||{{#ifeq: | JaKeinHinweis |{{#switch:

   |0|=Vorlage:Toter Link/Core{{#if: https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/
       | {{#if:  | [1] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   =  @@@
         |preview  = 1
    }}{{#if: https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/
      | {{#if:{{#invoke:URLutil|isWebURL|https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/}}
          ||  Fehler bei Vorlage:Toter Link: Wert in 'url' ist ungültig.{{#if:  ||  }} 
        }}
      | {{#if: 
           |  Fehler bei Vorlage:Toter Link: 'text' angegeben, aber 'url'' fehlt.{{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             ||  Fehler bei Vorlage:Toter Link: Wert in 'date' ist ungültig.{{#if:  ||  }} 
         }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=   Fehler bei Vorlage:Toter Link: Wert in 'botlauf' ist ungültig.{{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/ Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   =  @@@
         |preview  = 1
       }}{{#if: https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/
       | {{#if:{{#invoke:URLutil|isWebURL|https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/}}
          ||  Fehler bei Vorlage:Toter Link: Wert in 'url' ist ungültig.{{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             ||  Fehler bei Vorlage:Toter Link: Wert in 'date' ist ungültig.{{#if:  ||  }} 
           }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=   Fehler bei Vorlage:Toter Link: Wert in 'botlauf' ist ungültig.{{#if:  ||  }}
    }}[https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/ }}|{{#switch: 
   |0|=Vorlage:Toter Link/Core{{#if: https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/
       | {{#if:  | [2] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   =  @@@
         |preview  = 1
    }}{{#if: https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/
      | {{#if:{{#invoke:URLutil|isWebURL|https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/}}
          ||  Fehler bei Vorlage:Toter Link: Wert in 'url' ist ungültig.{{#if:  ||  }} 
        }}
      | {{#if: 
           |  Fehler bei Vorlage:Toter Link: 'text' angegeben, aber 'url'' fehlt.{{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             ||  Fehler bei Vorlage:Toter Link: Wert in 'date' ist ungültig.{{#if:  ||  }} 
         }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=   Fehler bei Vorlage:Toter Link: Wert in 'botlauf' ist ungültig.{{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/ Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   =  @@@
         |preview  = 1
       }}{{#if: https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/
       | {{#if:{{#invoke:URLutil|isWebURL|https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/}}
          ||  Fehler bei Vorlage:Toter Link: Wert in 'url' ist ungültig.{{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             ||  Fehler bei Vorlage:Toter Link: Wert in 'date' ist ungültig.{{#if:  ||  }} 
           }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=   Fehler bei Vorlage:Toter Link: Wert in 'botlauf' ist ungültig.{{#if:  ||  }}
    }}[https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/ }} }}}}}}}}}}{{#if:|
        {{#invoke:Vorlage:Internetquelle|archivBot|stamp={{{archiv-bot}}}|text={{#if:|Vorlage:Webarchiv/archiv-bot}}

}}}} {{#invoke:TemplatePar|check |all= url= titel= |opt= autor= hrsg= format= sprache= titelerg= werk= seiten= datum= abruf= zugriff= abruf-verborgen= archiv-url= archiv-datum= archiv-bot= kommentar= zitat= AT= CH= offline= |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Internetquelle}} |template= Vorlage:Internetquelle |format=0 |preview=1 }}</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

{{#invoke:Vorlage:Literatur|f}}
{{#invoke:Vorlage:Literatur|f}}
{{#invoke:Vorlage:Literatur|f}}

Weblinks

[{{canonicalurl:Commons:Category:{{#if:Prim's algorithm|Prim's algorithm|Algorithmus von Prim}}|uselang=de}} Commons: {{#if:Algorithmus von Prim|Algorithmus von Prim|{{#if:Prim's algorithm|Prim's algorithm|{{#invoke:WLink|getArticleBase}}}}}}]{{#switch:1

|X|x= |0|-= |S|s= – Sammlung von Bildern |1|= – Sammlung von Bildern{{#if: 0

    | {{#switch: {{#invoke:TemplUtl|faculty|1}}/{{#invoke:TemplUtl|faculty|0}}
        |1/=  und Videos
        |1/1=, Videos und Audiodateien
        |/1=  und Audiodateien}}
    | , Videos und Audiodateien
  }}

|#default= – }}{{#if: Prim's algorithm

   | {{#ifeq: {{#invoke:Str|left|prim's algorithm|9}} 
       | category:

| FEHLER: Ohne Category: angeben!}}}}

Vorlage:Wikidata-Registrierung

[[b:{{#if:|{{{lang}}}:}}{{#if:Algorithmensammlung: Graphentheorie: Algorithmus von Prim|Algorithmensammlung: Graphentheorie: Algorithmus von Prim|Algorithmus von Prim}}|Wikibooks: {{#if:Algorithmus von Prim|Algorithmus von Prim|{{#if:Algorithmensammlung: Graphentheorie: Algorithmus von Prim|Algorithmensammlung: Graphentheorie: Algorithmus von Prim|Algorithmus von Prim}}}}]]{{#switch: Implementierungen in der Algorithmensammlung

|1|= – Lern- und Lehrmaterialien |0|-= |X|x={{#switch: 0

      |0|4|10|12|14|100=}}

|#default= – Implementierungen in der Algorithmensammlung

}}{{#if: | ({{#invoke:Multilingual|format|{{{lang}}}|slang=!|shift=m}}) }}

{{#invoke:TemplatePar|check

  |opt= 1= 2= lang= suffix=
  |template=Vorlage:Wikibooks
  |cat=Wikipedia:Vorlagenfehler/Schwesterprojekt
  }}

<templatestyles src="Webarchiv/styles.css" />{{#if:20150614233605

      | {{#ifeq: 20150614233605 | *
    | Vorlage:Webarchiv/Wartung/Stern{{#if: Reza Sefidgar: Interaktives Applet zur Lernen, Ausprobieren und Demonstrieren des Algorithmus | {{#invoke:WLink|getEscapedTitle|Reza Sefidgar: Interaktives Applet zur Lernen, Ausprobieren und Demonstrieren des Algorithmus}} | {{#invoke:Webarchiv|getdomain|http://www-m9.ma.tum.de/material/de/mst-prim/}} }} (Archivversionen)
    | {{#iferror: {{#time: j. F Y|20150614233605}}
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/DatumDer Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
         | {{#if: Reza Sefidgar: Interaktives Applet zur Lernen, Ausprobieren und Demonstrieren des Algorithmus | {{#invoke:WLink|getEscapedTitle|Reza Sefidgar: Interaktives Applet zur Lernen, Ausprobieren und Demonstrieren des Algorithmus}} | {{#invoke:Webarchiv|getdomain|http://www-m9.ma.tum.de/material/de/mst-prim/}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y|20150614233605}} im Internet Archive{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
      }}
  }}
      | {{#if:
          | {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
    | {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
       | 16= {{#if: Reza Sefidgar: Interaktives Applet zur Lernen, Ausprobieren und Demonstrieren des Algorithmus | {{#invoke:WLink|getEscapedTitle|Reza Sefidgar: Interaktives Applet zur Lernen, Ausprobieren und Demonstrieren des Algorithmus}} | {{#invoke:Webarchiv|getdomain|http://www-m9.ma.tum.de/material/de/mst-prim/}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | 9 = {{#if: Reza Sefidgar: Interaktives Applet zur Lernen, Ausprobieren und Demonstrieren des Algorithmus | {{#invoke:WLink|getEscapedTitle|Reza Sefidgar: Interaktives Applet zur Lernen, Ausprobieren und Demonstrieren des Algorithmus}} | {{#invoke:Webarchiv|getdomain|http://www-m9.ma.tum.de/material/de/mst-prim/}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!Vorlage:Webarchiv/Wartung/webcitation{{#if:  || }}
      }}
    | c|{{{webciteID}}}}} {{#if: Reza Sefidgar: Interaktives Applet zur Lernen, Ausprobieren und Demonstrieren des Algorithmus | {{#invoke:WLink|getEscapedTitle|Reza Sefidgar: Interaktives Applet zur Lernen, Ausprobieren und Demonstrieren des Algorithmus}} | {{#invoke:Webarchiv|getdomain|http://www-m9.ma.tum.de/material/de/mst-prim/}} }} (Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
  }}
          | {{#if: 
              | Vorlage:Webarchiv/Today
              | {{#if:
                      | Vorlage:Webarchiv/Generisch
                      | {{#if: Reza Sefidgar: Interaktives Applet zur Lernen, Ausprobieren und Demonstrieren des Algorithmus | {{#invoke:WLink|getEscapedTitle|Reza Sefidgar: Interaktives Applet zur Lernen, Ausprobieren und Demonstrieren des Algorithmus}} | {{#invoke:Webarchiv|getdomain|http://www-m9.ma.tum.de/material/de/mst-prim/}} }}  
                 }}}}}}}}{{#if:
    | Vorlage:Webarchiv/archiv-bot
  }}{{#invoke:TemplatePar|check
     |all      = url=
     |opt      = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
     |cat      = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
     |errNS    = 0
     |template = Vorlage:Webarchiv
     |format   = *
     |preview  = 1
  }}{{#ifexpr: {{#if:20150614233605|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
  }}{{#if: 
    | {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
        | web.archive.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}} 
        | webcitation.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}} 
        | archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
      }}{{#if: 
         | {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|Vorlage:FormatDate/Wartung/Error}}
             | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
          |  }} 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
      }}
    | {{#if: 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
      }}
  }}{{#if:{{#invoke:URLutil|isHostPathResource|http://www-m9.ma.tum.de/material/de/mst-prim/}}
    || {{#if:  || }} URL/Pfad ungültig.
  }}{{#if: Reza Sefidgar: Interaktives Applet zur Lernen, Ausprobieren und Demonstrieren des Algorithmus
    | {{#if: {{#invoke:WLink|isBracketedLink|Reza Sefidgar: Interaktives Applet zur Lernen, Ausprobieren und Demonstrieren des Algorithmus}}
        | {{#if:  || }} Linktext ungültig.
      }}
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Linktext_fehlt Linktext fehlt.
  }}{{#switch: 
    |addlarchives|addlpages= {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/Parameter}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
  }}{{#ifeq: {{#invoke:Str|find|http://www-m9.ma.tum.de/material/de/mst-prim/%7Carchiv}} |-1
    || {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://www-m9.ma.tum.de/material/de/mst-prim/%7C4}}%7Chttp}} |-1
         || {{#switch: {{#invoke:Webarchiv|getdomain|http://www-m9.ma.tum.de/material/de/mst-prim/ }}
              | abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org = 
              | #default = {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/URL}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
            }} 
       }}
  }}

<templatestyles src="Webarchiv/styles.css" />{{#if:20211228013007

      | {{#ifeq: 20211228013007 | *
    | Vorlage:Webarchiv/Wartung/Stern{{#if: Java-Applet zur Schritt-für-Schritt-Visualisierung | {{#invoke:WLink|getEscapedTitle|Java-Applet zur Schritt-für-Schritt-Visualisierung}} | {{#invoke:Webarchiv|getdomain|http://www.unf.edu/~wkloster/foundations/PrimApplet/PrimApplet.htm}} }} (Archivversionen)
    | {{#iferror: {{#time: j. F Y|20211228013007}}
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/DatumDer Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
         | {{#if: Java-Applet zur Schritt-für-Schritt-Visualisierung | {{#invoke:WLink|getEscapedTitle|Java-Applet zur Schritt-für-Schritt-Visualisierung}} | {{#invoke:Webarchiv|getdomain|http://www.unf.edu/~wkloster/foundations/PrimApplet/PrimApplet.htm}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y|20211228013007}} im Internet Archive{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
      }}
  }}
      | {{#if:
          | {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
    | {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
       | 16= {{#if: Java-Applet zur Schritt-für-Schritt-Visualisierung | {{#invoke:WLink|getEscapedTitle|Java-Applet zur Schritt-für-Schritt-Visualisierung}} | {{#invoke:Webarchiv|getdomain|http://www.unf.edu/~wkloster/foundations/PrimApplet/PrimApplet.htm}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | 9 = {{#if: Java-Applet zur Schritt-für-Schritt-Visualisierung | {{#invoke:WLink|getEscapedTitle|Java-Applet zur Schritt-für-Schritt-Visualisierung}} | {{#invoke:Webarchiv|getdomain|http://www.unf.edu/~wkloster/foundations/PrimApplet/PrimApplet.htm}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!Vorlage:Webarchiv/Wartung/webcitation{{#if:  || }}
      }}
    | c|{{{webciteID}}}}} {{#if: Java-Applet zur Schritt-für-Schritt-Visualisierung | {{#invoke:WLink|getEscapedTitle|Java-Applet zur Schritt-für-Schritt-Visualisierung}} | {{#invoke:Webarchiv|getdomain|http://www.unf.edu/~wkloster/foundations/PrimApplet/PrimApplet.htm}} }} (Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
  }}
          | {{#if: 
              | Vorlage:Webarchiv/Today
              | {{#if:
                      | Vorlage:Webarchiv/Generisch
                      | {{#if: Java-Applet zur Schritt-für-Schritt-Visualisierung | {{#invoke:WLink|getEscapedTitle|Java-Applet zur Schritt-für-Schritt-Visualisierung}} | {{#invoke:Webarchiv|getdomain|http://www.unf.edu/~wkloster/foundations/PrimApplet/PrimApplet.htm}} }}  
                 }}}}}}}}{{#if:
    | Vorlage:Webarchiv/archiv-bot
  }}{{#invoke:TemplatePar|check
     |all      = url=
     |opt      = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
     |cat      = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
     |errNS    = 0
     |template = Vorlage:Webarchiv
     |format   = *
     |preview  = 1
  }}{{#ifexpr: {{#if:20211228013007|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
  }}{{#if: 
    | {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
        | web.archive.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}} 
        | webcitation.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}} 
        | archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
      }}{{#if: 
         | {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|Vorlage:FormatDate/Wartung/Error}}
             | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
          |  }} 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
      }}
    | {{#if: 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
      }}
  }}{{#if:{{#invoke:URLutil|isHostPathResource|http://www.unf.edu/~wkloster/foundations/PrimApplet/PrimApplet.htm}}
    || {{#if:  || }} URL/Pfad ungültig.
  }}{{#if: Java-Applet zur Schritt-für-Schritt-Visualisierung
    | {{#if: {{#invoke:WLink|isBracketedLink|Java-Applet zur Schritt-für-Schritt-Visualisierung}}
        | {{#if:  || }} Linktext ungültig.
      }}
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Linktext_fehlt Linktext fehlt.
  }}{{#switch: 
    |addlarchives|addlpages= {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/Parameter}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
  }}{{#ifeq: {{#invoke:Str|find|http://www.unf.edu/~wkloster/foundations/PrimApplet/PrimApplet.htm%7Carchiv}} |-1
    || {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://www.unf.edu/~wkloster/foundations/PrimApplet/PrimApplet.htm%7C4}}%7Chttp}} |-1
         || {{#switch: {{#invoke:Webarchiv|getdomain|http://www.unf.edu/~wkloster/foundations/PrimApplet/PrimApplet.htm }}
              | abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org = 
              | #default = {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/URL}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
            }} 
       }}
  }}

<templatestyles src="Webarchiv/styles.css" />{{#if:20160127080051

      | {{#ifeq: 20160127080051 | *
    | Vorlage:Webarchiv/Wartung/Stern{{#if: Anschauliche Darstellung des Algorithmus im Rahmen des Informatikjahres, 2006 | {{#invoke:WLink|getEscapedTitle|Anschauliche Darstellung des Algorithmus im Rahmen des Informatikjahres, 2006}} | {{#invoke:Webarchiv|getdomain|http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo21.php}} }} (Archivversionen)
    | {{#iferror: {{#time: j. F Y|20160127080051}}
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/DatumDer Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
         | {{#if: Anschauliche Darstellung des Algorithmus im Rahmen des Informatikjahres, 2006 | {{#invoke:WLink|getEscapedTitle|Anschauliche Darstellung des Algorithmus im Rahmen des Informatikjahres, 2006}} | {{#invoke:Webarchiv|getdomain|http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo21.php}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y|20160127080051}} im Internet Archive{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
      }}
  }}
      | {{#if:
          | {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
    | {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
       | 16= {{#if: Anschauliche Darstellung des Algorithmus im Rahmen des Informatikjahres, 2006 | {{#invoke:WLink|getEscapedTitle|Anschauliche Darstellung des Algorithmus im Rahmen des Informatikjahres, 2006}} | {{#invoke:Webarchiv|getdomain|http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo21.php}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | 9 = {{#if: Anschauliche Darstellung des Algorithmus im Rahmen des Informatikjahres, 2006 | {{#invoke:WLink|getEscapedTitle|Anschauliche Darstellung des Algorithmus im Rahmen des Informatikjahres, 2006}} | {{#invoke:Webarchiv|getdomain|http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo21.php}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!Vorlage:Webarchiv/Wartung/webcitation{{#if:  || }}
      }}
    | c|{{{webciteID}}}}} {{#if: Anschauliche Darstellung des Algorithmus im Rahmen des Informatikjahres, 2006 | {{#invoke:WLink|getEscapedTitle|Anschauliche Darstellung des Algorithmus im Rahmen des Informatikjahres, 2006}} | {{#invoke:Webarchiv|getdomain|http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo21.php}} }} (Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
  }}
          | {{#if: 
              | Vorlage:Webarchiv/Today
              | {{#if:
                      | Vorlage:Webarchiv/Generisch
                      | {{#if: Anschauliche Darstellung des Algorithmus im Rahmen des Informatikjahres, 2006 | {{#invoke:WLink|getEscapedTitle|Anschauliche Darstellung des Algorithmus im Rahmen des Informatikjahres, 2006}} | {{#invoke:Webarchiv|getdomain|http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo21.php}} }}  
                 }}}}}}}}{{#if:
    | Vorlage:Webarchiv/archiv-bot
  }}{{#invoke:TemplatePar|check
     |all      = url=
     |opt      = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
     |cat      = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
     |errNS    = 0
     |template = Vorlage:Webarchiv
     |format   = *
     |preview  = 1
  }}{{#ifexpr: {{#if:20160127080051|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
  }}{{#if: 
    | {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
        | web.archive.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}} 
        | webcitation.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}} 
        | archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
      }}{{#if: 
         | {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|Vorlage:FormatDate/Wartung/Error}}
             | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
          |  }} 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
      }}
    | {{#if: 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
      }}
  }}{{#if:{{#invoke:URLutil|isHostPathResource|http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo21.php}}
    || {{#if:  || }} URL/Pfad ungültig.
  }}{{#if: Anschauliche Darstellung des Algorithmus im Rahmen des Informatikjahres, 2006
    | {{#if: {{#invoke:WLink|isBracketedLink|Anschauliche Darstellung des Algorithmus im Rahmen des Informatikjahres, 2006}}
        | {{#if:  || }} Linktext ungültig.
      }}
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Linktext_fehlt Linktext fehlt.
  }}{{#switch: 
    |addlarchives|addlpages= {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/Parameter}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
  }}{{#ifeq: {{#invoke:Str|find|http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo21.php%7Carchiv}} |-1
    || {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo21.php%7C4}}%7Chttp}} |-1
         || {{#switch: {{#invoke:Webarchiv|getdomain|http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo21.php }}
              | abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org = 
              | #default = {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/URL}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
            }} 
       }}
  }}

Einzelnachweise