Algorithmus von Kruskal
Der Algorithmus von Kruskal ist ein Greedy-Algorithmus der Graphentheorie zur Berechnung minimaler Spannbäume von ungerichteten Graphen. Der Graph muss dazu zusammenhängend, kantengewichtet und endlich sein.
Der Algorithmus stammt von Joseph Kruskal, der ihn 1956 in der Zeitschrift „Proceedings of the American Mathematical Society“ veröffentlichte. Er beschrieb ihn dort wie folgt:
- Führe den folgenden Schritt so oft wie möglich aus: Wähle unter den noch nicht ausgewählten Kanten von <math>G</math> (dem Graphen) die kürzeste Kante, die mit den schon gewählten Kanten keinen Kreis bildet.<ref name="KRUSKAL">Joseph Kruskal: On the shortest spanning subtree and the traveling salesman problem. In: Proceedings of the American Mathematical Society, 7, 1956, S. 48–50 (englisch)</ref>
Die kürzeste Kante bezeichnet dabei jeweils die Kante mit dem kleinsten Kantengewicht. Nach Abschluss des Algorithmus bilden die ausgewählten Kanten einen minimalen Spannbaum des Graphen.
Wendet man den Algorithmus auf unzusammenhängende Graphen an, so berechnet er für jede Zusammenhangskomponente des Graphen einen minimalen Spannbaum. Diese Bäume bilden einen minimalen aufspannenden Wald.
Idee
Der Algorithmus von Kruskal nutzt die Kreiseigenschaft minimaler Spannbäume ({{#invoke:Vorlage:lang|full|CODE=en|SCRIPTING=Latn|SERVICE=englisch}}, MST). Dazu werden die Kanten in der ersten Phase aufsteigend nach ihrem Gewicht sortiert. In der zweiten Phase wird über die sortierten Kanten iteriert. Wenn eine Kante zwei Knoten verbindet, die noch nicht durch einen Pfad vorheriger Kanten verbunden sind, wird diese Kante zum MST hinzugenommen.
Beispiel
| Datei:Prim Algorithm 0.svg | Dies ist der Graph, zu dem nach dem Algorithmus von Kruskal ein minimaler Spannbaum berechnet wird. Die Zahlen bei den einzelnen Kanten geben das jeweilige Kantengewicht an. Zu Beginn ist noch keine Kante ausgewählt. |
| Datei:Kruskal Algorithm 1.svg | Die Kanten AD und CE sind die kürzesten (noch nicht ausgewählten) Kanten des Graphen. Beide können ausgewählt werden. Hier wird zufällig AD ausgewählt. (Dass diese keinen Kreis bildet, ist im ersten Schritt selbstverständlich.) |
| Datei:Kruskal Algorithm 2.svg | Nun ist CE die kürzeste, noch nicht ausgewählte Kante. Da sie mit AD keinen Kreis bildet, wird sie nun ausgewählt. |
| Datei:Kruskal Algorithm 3.svg | Die nächste Kante ist DF mit Länge 6. Sie bildet mit den schon gewählten Kanten keinen Kreis und wird deshalb ausgewählt. |
| Datei:Kruskal Algorithm 4.svg | Jetzt könnten die Kanten AB und BE, jeweils mit Länge 7, ausgewählt werden. Es wird zufällig AB gewählt. Die Kante BD wird rot markiert, da sie mit den bis jetzt gewählten Kanten einen Kreis bilden würde und somit im weiteren Verlauf des Algorithmus nicht mehr berücksichtigt werden muss. |
| Datei:Kruskal Algorithm 5.svg | BE ist nun mit Länge 7 die kürzeste der noch nicht ausgewählten Kanten und da sie mit den bisher gewählten keinen Kreis bildet, wird sie ausgewählt. Analog zur Kante BD im letzten Schritt werden jetzt die Kanten BC, DE und FE rot markiert. |
| Datei:Kruskal Algorithm 6.svg | Als letzte wird die Kante EG mit Länge 9 ausgewählt, da alle kürzeren bzw. gleich langen Kanten entweder schon ausgewählt sind oder einen Kreis bilden würden. Die Kante FG wird rot markiert. Da nun alle nicht ausgewählten Kanten einen Kreis bilden würden (sie sind rot markiert) ist der Algorithmus am Ende angelangt und der grüne Graph ist ein minimaler Spannbaum des zugrundeliegenden Graphen. |
Algorithmus
Die Grundidee ist, die Kanten in Reihenfolge aufsteigender Kantengewichte zu durchlaufen und jede Kante zur Lösung hinzuzufügen, die mit allen zuvor gewählten Kanten keinen Kreis bildet. Es werden somit sukzessiv sogenannte Komponenten zum minimalen Spannbaum verbunden.
Input
Als Eingabe dient ein zusammenhängender kantenbewerteter Graph <math>G = (V,\,E,\,w)</math>. <math>V</math> bezeichnet die Menge der Knoten (vertices), <math>E</math> die Menge der Kanten (edges). Die Gewichtsfunktion <math>w\colon E \rightarrow \R</math> ordnet jeder Kante ein Kantengewicht zu.
Output
Der Algorithmus liefert einen minimalen Spannbaum <math>M = (V,\,E')</math> mit <math>E' \subseteq E</math>.
Pseudocode
Der Algorithmus von Kruskal arbeitet nicht-deterministisch, d. h., er liefert unter Umständen beim wiederholten Ausführen unterschiedliche Ergebnisse. Alle diese Ergebnisse sind minimale Spannbäume von <math>G</math>.
G = (V,E,w): ein zusammenhängender, ungerichteter, kantengewichteter Graph kruskal(G) 1 <math>E' \leftarrow \emptyset</math> 2 <math>L \leftarrow E</math> 3 Sortiere die Kanten in L aufsteigend nach ihrem Kantengewicht. 4 solange <math>L \neq \emptyset</math> 5 wähle eine Kante <math>e \in L</math> mit kleinstem Kantengewicht 6 entferne die Kante <math>e</math> aus <math>L</math> 7 wenn der Graph <math>(V,E' \cup \lbrace e \rbrace)</math> keinen Kreis enthält 8 dann <math>E' \leftarrow E' \cup \lbrace e \rbrace</math> 9 M = (V,E') ist ein minimaler Spannbaum von G.
Derselbe Algorithmus lässt sich analog für einen maximalen Spannbaum anwenden. Sei <math>G=(V,E,w)</math> etwa ein zusammenhängender kantengewichteter Graph. Dann gibt man <math>G'=(V,E,w')</math> mit <math>w'(e) = s - w(e)</math>, <math>s \in \mathbb{N}</math> und <math>\forall e \in E \,: s > w(e)</math> im Algorithmus von Kruskal ein. Als Ausgabe erhält man schließlich einen minimalen Spannbaum von <math>G'</math> und somit einen maximalen von <math>G</math>.
Zum Testen, ob Knoten <math>u</math> und <math>v</math> in unterschiedlichen Teilbäumen sind, kann eine Union-Find-Struktur verwendet werden. Dann ergibt sich eine Laufzeit von <math>O(T_\text{sort}(|E|) + |E| \cdot \alpha(|V|))</math>. Dabei ist <math>T_\text{sort}</math> die Zeit, die zum Sortieren der Kantengewichte benötigt wird und <math>\alpha(\cdot)</math> das Inverse der Ackermannfunktion. Für realistische Eingaben ist <math>\alpha(|V|)</math> immer kleiner oder gleich <math>5</math>
Programmierung
Das folgende Beispiel in der Programmiersprache C++ zeigt die Implementierung eines ungerichteten Graphen mit einem Array von Kanten. Der ungerichtete Graph wird als Klasse UndirectedGraph deklariert. Bei der Ausführung des Programms wird die Methode main verwendet, die die Kanten und Kantengewichte eines minimalen Spannbaums auf der Konsole ausgibt. Die Funktion unionSubsets verwendet union by rank, um zwei Teilmengen von Kanten des Graphen zu vereinigen.<ref>{{#if:|{{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}| |}}}}{{#if:|{{{autor}}}: }}{{#if:|{{#if:Kruskal’s Minimum Spanning Tree Algorithm|[{{#invoke:Vorlage:Internetquelle|archivURL|1={{#invoke:URLutil|getNormalized|1={{{archiv-url}}}}}}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=Kruskal’s Minimum Spanning Tree Algorithm}}]{{#if:| ({{{format}}})}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}|{{#if:https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/%7C{{#if:{{#invoke:TemplUtl%7Cfaculty%7C}}%7C{{#invoke:Vorlage:Internetquelle%7CTitelFormat%7Ctitel={{#invoke:WLink%7CgetEscapedTitle%7C1=Kruskal’s Minimum Spanning Tree Algorithm}}}}|[{{#invoke:URLutil|getNormalized|1=https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#invoke:WLink|getEscapedTitle|1=Kruskal’s Minimum Spanning Tree Algorithm}}}}]}}{{#if:| ({{{format}}}{{#if:geeksforgeeks2024-12-10{{#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/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/}}%7C%7C}}}}{{#if:Kruskal’s Minimum Spanning Tree Algorithm|{{#if:{{#invoke:WLink|isValidLinktext|1=Kruskal’s Minimum Spanning Tree Algorithm|lines=0}}||}}}}{{#if: geeksforgeeks| In: {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=geeksforgeeks}}}}{{#if: | {{{hrsg}}}{{#if: 2024-12-10|,|{{#if: 2025-01-29 | {{#if:{{#invoke:TemplUtl|faculty|}}||,}}}}}}}}{{#if: 2024-12-10| {{#if:{{#invoke:DateTime|format|2024-12-10|noerror=1}}
|{{#invoke:DateTime|format|2024-12-10|T._Monat JJJJ}}
|{{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, datum=2024-12-10|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-10|{{#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}}|}}|{{{archiv-datum}}}{{#if:13855||(?)}}}}}}{{#if: 2025-01-29|;}}}}{{#if: 2025-01-29| {{#if:2024-12-10{{#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}} }}{{#if:{{#ifeq:en|de||{{#if:en|1}}}}|{{#if:geeksforgeeks2024-12-10{{#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-10{{#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/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/ | {{#if: | [1] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive ){{#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/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/ | {{#if:{{#invoke:URLutil|isWebURL|https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/}} || {{#if: || }} }} | {{#if: | {{#if: || }} | {{#if: || }} }} }}{{#if: | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}} || {{#if: || }} }} }}{{#switch: deadurl |checked|deadurl|= |#default= {{#if: || }} }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/ Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. ) {{#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/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/ | {{#if:{{#invoke:URLutil|isWebURL|https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/}} || {{#if: || }} }} }}{{#if: | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}} || {{#if: || }} }} }}{{#switch: deadurl |checked|deadurl|= |#default= {{#if: || }} }}[https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/ }}|{{#switch: |0|=Vorlage:Toter Link/Core{{#if: https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/ | {{#if: | [2] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive ){{#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/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/ | {{#if:{{#invoke:URLutil|isWebURL|https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/}} || {{#if: || }} }} | {{#if: | {{#if: || }} | {{#if: || }} }} }}{{#if: | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}} || {{#if: || }} }} }}{{#switch: |checked|deadurl|= |#default= {{#if: || }} }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/ Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. ) {{#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/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/ | {{#if:{{#invoke:URLutil|isWebURL|https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/}} || {{#if: || }} }} }}{{#if: | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}} || {{#if: || }} }} }}{{#switch: |checked|deadurl|= |#default= {{#if: || }} }}[https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/ }} }}}}}}}}}}{{#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++">
- include <iostream>
- include <sstream>
using namespace std;
// Deklariert den Datentyp für die Knoten des Graphen struct Node {
int index; string value; Node* next;
};
// Deklariert den Datentyp für die Kanten des Graphen struct Edge {
int startIndex; int endIndex; int weight;
};
// Deklariert die Klasse für den ungerichteten Graphen class UndirectedGraph { public:
int numberOfVertices; Edge* edges; // Pointer auf das Array für die Kanten
};
// Deklariert die Klasse für Teilmengen (Teilbäume) der Kantenmenge des ungerichteten Graphen class subset { public:
int parent; // Index der Wurzel int rank; // Rang der Teilmenge
};
// Diese rekursive Funktion gibt den Index der Wurzel der Teilmenge (Teilbaum) mit dem Index i zurück int find(subset subsets[], int i) {
// Setzt Index der Wurzel auf den Index der Wurzel der Teilmenge mit dem Index i
if (subsets[i].parent != i)
{
subsets[i].parent = find(subsets, subsets[i].parent); // Rekursiver Aufruf der Funktion
}
return subsets[i].parent;
}
// Diese Methode bildet die Vereinigungsmenge der zwei Teilmengen (Teilbäume) mit den Indexen index1 und index2 void unionSubsets(subset subsets[], int index1, int index2) {
int newIndex1 = find(subsets, index1); // Index der Teilmenge mit dem Index index1
int newIndex2 = find(subsets, index2); // Index der Teilmenge mit dem Index index2
// Hängt den Teilbaum mit dem niedrigeren Rang unter die Wurzel des Baums mit dem höheren Rang
if (subsets[newIndex1].rank < subsets[newIndex2].rank)
{
subsets[newIndex1].parent = newIndex2;
}
else if (subsets[newIndex1].rank > subsets[newIndex2].rank)
{
subsets[newIndex2].parent = newIndex1;
}
else // Wenn die Teilbäume denselben Rang haben, wird der Rang des einen Baums erhöht und der andere Baum unter die Wurzel des anderen Baums gehängt
{
subsets[newIndex2].parent = newIndex1;
subsets[newIndex1].rank++;
}
}
// Diese Funktion vergleicht die Gewichte der Kanten edge1 und edge2 int compare(const void* edge1, const void* edge2) {
return ((Edge*)edge1)->weight > ((Edge*)edge2)->weight; // Gibt 1 zurück, wenn der Vergleich true ergibt. Gibt 0 zurück, wenn der Vergleich false ergibt.
}
// Diese Funktion verwendet den Algorithmus von Kruskal und gibt den minimalen Spannbaum zurück Edge* getMSTByKruskal(UndirectedGraph* graph) {
Edge* edges = graph->edges; // Pointer auf das Array für die Kanten int numberOfVertices = graph->numberOfVertices; // Variable für die Anzahl der Knoten int numberOfEdges = sizeof(edges); // Variable für die Anzahl der Kanten
Edge* minimalSpanningTree = new Edge[numberOfVertices]; // Deklariert ein Array für die Kanten, das als Ergebnis der Methode zurückgegeben wird int currentIndex = 0; // Aktueller Kantenindex int nextIndex = 0; // Kantenindex für die nächste Iteration qsort(edges, numberOfEdges, sizeof(edges[0]), compare); // Sortiert das Array edges der Kanten mit der C++-Standardfunktion qsort (Sortierverfahren Quicksort) und der oben definierten Vergleichsfunktion compare
subset* subsets = new subset[numberOfVertices]; // Deklariert ein Array für die Teilmengen der Kantenmenge
for (int i = 0; i < numberOfVertices; i++) // for-Schleife, die Teilmengen mit einzelnen Kanten erzeugt
{
subsets[i].parent = i;
subsets[i].rank = 0;
}
while (currentIndex < numberOfVertices - 1 && nextIndex < numberOfEdges) // So lange der aktuelle Kantenindex kleiner als die Anzahl der Knoten minus 1 ist
{
Edge nextEdge = edges[nextIndex++]; // Weist die verbleibende Kante mit dem kleinsten Kantengewicht zu und erhöht den Kantenindex für die nächste Iteration um 1
int index1 = find(subsets, nextEdge.startIndex); // Index der Wurzel der Teilmenge mit dem Index nextEdge.startIndex
int index2 = find(subsets, nextEdge.endIndex); // Index der Wurzel der Teilmenge mit dem Index nextEdge.endIndex
if (index1 != index2) // Wenn die Kante keinen Zyklus erzeugt
{
minimalSpanningTree[currentIndex++] = nextEdge; // Fügt die Kante dem minimalen Spannbaum hinzu
unionSubsets(subsets, index1, index2); // Methodenaufruf, der die Vereinigungsmenge der zwei Mengen mit den Indexen index1 und index2 bildet
}
}
return minimalSpanningTree;
}
// Gibt die Kanten, die Gewichte und das gesamte Kantengewicht des minimalen Spannbaums auf der Konsole aus string MSTtoString(Edge* minimalSpanningTree) {
stringstream text;
int weight = 0;
for (int i = 0; i < sizeof(minimalSpanningTree) - 1; i++)
{
Edge edge = minimalSpanningTree[i];
text << "(" << edge.startIndex << ", " << edge.endIndex << "), Gewicht: " << edge.weight << endl;
weight += edge.weight;
}
text << "Kantengewicht des minimalen Spannbaums: " << weight << endl;
return text.str(); // Typumwandlung von stringstream nach string
}
// Hauptfunktion die das Programm ausführt int main() {
// Deklariert und initialisiert ein Array mit 5 Kanten Edge* edges = new Edge[5]; edges[0].startIndex = 0; edges[0].endIndex = 1; edges[0].weight = 10; edges[1].startIndex = 0; edges[1].endIndex = 2; edges[1].weight = 6; edges[2].startIndex = 0; edges[2].endIndex = 3; edges[2].weight = 5; edges[3].startIndex = 1; edges[3].endIndex = 3; edges[3].weight = 15; edges[4].startIndex = 2; edges[4].endIndex = 3; edges[4].weight = 4;
// Erzeugt den ungerichteten Graphen mit den gegebenen Kanten UndirectedGraph* undirectedGraph = new UndirectedGraph; undirectedGraph->edges = edges; undirectedGraph->numberOfVertices = 4; Edge* minimalSpanningTree = getMSTByKruskal(undirectedGraph); // Aufruf der Methode, die einen Pointer auf das Array von Kanten zurückgibt cout << MSTtoString(minimalSpanningTree); // Aufruf der Methode, die das Ergebnis auf der Konsole ausgibt
} </syntaxhighlight>
Varianten
Paralleles Sortieren
Das Sortieren der ersten Phase kann parallelisiert werden. In der zweiten Phase ist es für die Korrektheit jedoch wichtig, dass die Kanten nacheinander abgearbeitet werden. Mit <math>O(\log |V|)</math> Prozessoren kann in linearer Zeit parallel sortiert werden. Dadurch sinkt die Gesamtlaufzeit auf <math>O(|E| \cdot \alpha(|V|))</math>.
Filter-Kruskal
Eine Variante des Algorithmus von Kruskal namens Filter-Kruskal wurde von Osipov et al.<ref name="osipov2009" /> beschrieben und eignet sich besser zur Parallelisierung. Die grundlegende Idee besteht darin, die Kanten in ähnlicher Weise wie bei Quicksort zu partitionieren und anschließend Kanten auszusortieren, welche Knoten im gleichen Teilbaum verbinden, um somit die Kosten für die weitere Sortierung zu verringern. Filter-Kruskal eignet sich besser zur Parallelisierung, da das Sortieren, Partitionieren und Filtern einfach parallel ausgeführt werden können, indem die Kanten zwischen den Prozessoren aufgeteilt werden. Der Algorithmus wird im folgenden Pseudocode dargestellt.
filterKruskal(<math>G</math>):
falls <math>|E| <</math> KruskalSchwellwert:
return kruskal(<math>G</math>)
pivot = zufällige Kante aus <math>E</math>
<math>(E_{\leq}</math>, <math>E_{>}) \gets </math>partition(<math>E</math>, pivot)
<math>A \gets</math> filterKruskal(<math>E_{\leq}</math>)
<math>E_{>} \gets</math> filter(<math>E_{>}</math>)
<math>A \gets A</math> <math>\cup</math> filterKruskal(<math>E_{>}</math>)
return <math>A</math>
partition(<math>E</math>, pivot):
<math>E_{\leq} \gets \emptyset </math>
<math>E_{>} \gets \emptyset</math>
für alle <math>(u, v) \in E</math>:
falls gewicht(<math>u, v</math>) <math>\leq</math> gewicht(pivot):
<math>E_{\leq} \gets E_{\leq} \cup {(u, v)}</math>
sonst
<math>E_{>} \gets E_{>} \cup {(u, v)} </math>
return (<math>E_{\leq}</math>, <math>E_{>}</math>)
filter(<math>E</math>):
<math>E_{filtered} \gets \emptyset </math>
für alle <math>(u, v) \in E</math>:
falls find-set(u) <math>\neq</math> find-set(v):
<math>E_{filtered} \gets E_{filtered} \cup {(u, v)}</math>
return <math>E_{filtered}</math>
Korrektheitsbeweis
Sei <math>G = (V,E,w)</math> ein zusammenhängender kantengewichteter Graph und <math>M = (V,E')</math> die Ausgabe des Algorithmus von Kruskal. Um nun die Korrektheit des Algorithmus zu beweisen, muss Folgendes gezeigt werden:
- der Algorithmus terminiert (er enthält keine Endlosschleife).
- <math>M</math> ist ein minimaler Spannbaum von <math>G</math>, also:
- <math>M</math> ist spannender Teilgraph von <math>G</math>.
- <math>M</math> enthält keinen Kreis.
- <math>M</math> ist zusammenhängend.
- <math>M</math> ist bezüglich <math>G</math> minimal.
Im Nachstehenden folgen einige Beweisideen, die die Gültigkeit der einzelnen Aussagen darlegen:
- Terminierung
- Durch Zeile 6 wird in jedem Schleifendurchlauf genau ein Element aus <math>L</math> entfernt. Außerdem wird <math>L</math> durch keine weitere Operation verändert. Aus <math>L</math> werden wegen Zeile 4 nur solange Elemente entfernt, bis <math>L = \emptyset</math>. Da zu Beginn im Algorithmus <math>L = E</math> gesetzt wurde und <math>E</math> nach Definition nur endlich ist, wird auch die Schleife nur endlich oft durchlaufen. Daraus folgt, dass Kruskals Algorithmus terminiert.
- M ist aufspannender Teilgraph von G
- Da die Menge der Knoten nach Definition des Algorithmus bei <math>M</math> und <math>G</math> gleich ist und wegen Zeile 8 offensichtlich <math>E' \subseteq E</math> gilt, ist <math>M</math> aufspannender Teilgraph von <math>G</math>.
- M enthält keinen Kreis
- Dass <math>M</math> keinen Kreis beinhalten kann, ist durch Zeile 7 trivial.
- M ist zusammenhängend
- Im Folgenden wird indirekt gezeigt, dass <math>M</math> zusammenhängend ist. Sei <math>M</math> also nicht zusammenhängend. Dann gibt es in <math>M</math> zwei Knoten <math>x</math> und <math>y</math>, die nicht durch einen Weg verbunden sind. Da aber <math>x</math> und <math>y</math> in <math>G</math> durch einen Weg verbunden sind, existiert eine Kante <math>k</math> in <math>G</math>, welche nicht in <math>M</math> vorhanden ist. Der Algorithmus betrachtet in Zeile 7 garantiert jede Kante aus <math>G</math> und damit auch <math>k</math>. Der Graph <math>(V,E' \cup \lbrace k \rbrace)</math> in Zeile 7 muss kreisfrei sein, da es zwischen <math>x</math> und <math>y</math> in <math>M=(V,E')</math> keinen Weg gibt. Mit Zeile 8 wird <math>k</math> dann in <math>M</math> eingefügt. Dies widerspricht allerdings der Tatsache, dass <math>k</math> nicht in <math>M</math> enthalten ist. Somit ist unsere Annahme hinfällig und <math>M</math> doch zusammenhängend.
- M ist bezüglich G minimal
- Wir zeigen durch Induktion, dass für <math>k=0,...,n</math> die folgende Behauptung wahr ist:
Wenn <math>F</math> die Kantenmenge ist, die im <math>k</math>-ten Schritt des Algorithmus erzeugt wurde, dann gibt es einen minimalen Spannbaum, der <math>F</math> enthält. Die Behauptung ist für <math>k=0</math> wahr, d. h. <math>F = \emptyset</math> (d. h., es ist noch keine Kante eingeplant). Jeder minimale Spannbaum erfüllt die Behauptung und es existiert ein minimaler Spannbaum, da ein gewichteter, zusammenhängender Graph immer einen minimalen Spannbaum besitzt. Jetzt nehmen wir an, dass die Behauptung für <math>0 \le k < n</math> erfüllt ist und <math>F</math> die vom Algorithmus nach Schritt <math>k</math> erzeugte Kantenmenge ist. Es sei <math>H</math> ein minimaler Spannbaum, der <math>F</math> enthält. Wir betrachten jetzt den Fall <math>k+1</math>. Dafür sei <math>e</math> die letzte vom Algorithmus eingefügte Kante.
- Falls <math>e \in H</math>
- Dann ist die Behauptung auch für <math>F+e</math> erfüllt, da der minimale Spannbaum <math>F</math> um eine Kante aus dem minimalen Spannbaum <math>H</math> erweitert wird.
- Falls <math>e \notin H</math>
- Dann enthält <math>H + e</math> einen Kreis und es gibt eine Kante <math>f</math>, die im Kreis, aber nicht in <math>F</math> liegt. (Wenn es keine solche Kante <math>f</math> geben würde, dann hätte <math>e</math> nicht zu <math>F</math> hinzufügt werden können, da dann ein Kreis entstanden wäre.) Damit ist <math>H-f+e</math> ein Baum. Weiterhin kann das Gewicht von <math>f</math> nicht geringer als das Gewicht von <math>e</math> sein, da sonst der Algorithmus <math>f</math> anstelle von <math>e</math> hinzugefügt hätte. Mit <math>w(e) \le w(f)</math> folgt, dass <math>w(H-f+e) \le w(H)</math> gilt. Da aber <math>H</math> minimaler Spannbaum ist, gilt außerdem <math>w(H) \le w(H-f+e)</math> und daraus folgt <math>w(H-f+e) = w(H)</math>. Somit ist <math>H-f+e</math> ein minimaler Spannbaum, der <math>F+e</math> enthält, und die Behauptung ist erfüllt.
Damit folgt für <math>k=n</math>, dass der Kruskal-Algorithmus nach <math>n</math> Schritten eine Menge <math>F</math> erzeugt, die zu einem minimalen Spannbaum erweitert werden kann. Da aber das Ergebnis nach <math>n</math> Schritten des Algorithmus bereits ein Baum ist (wie oben gezeigt wurde), muss dieser minimal sein.
Zeitkomplexität
Im Folgenden sei <math>\left|E\right|</math> die Anzahl der Kanten und <math>\left|V\right|</math> die Anzahl der Knoten. Die Laufzeit des Algorithmus setzt sich zusammen aus dem notwendigen Sortieren der Kanten nach ihrem Gewicht und dem Überprüfen, ob der Graph kreisfrei ist. Das Sortieren benötigt eine Laufzeit von <math>\mathcal{O}\bigl(\left|E\right| \cdot \log(\left|E\right|)\bigr)</math>. Bei einer geeigneten Implementierung ist das Überprüfen auf Kreisfreiheit schneller möglich, so dass das Sortieren die Gesamtlaufzeit bestimmt. Insbesondere bei Graphen mit vielen Kanten ist insofern der Algorithmus von Prim effizienter.
Wenn die Kanten bereits vorsortiert sind, arbeitet der Algorithmus von Kruskal schneller. Man betrachtet nun, wie schnell das Überprüfen auf Kreisfreiheit möglich ist. Um eine bestmögliche Laufzeit zu erreichen, speichert man alle Knoten in einer Union-Find-Struktur. Diese enthält Informationen darüber, welche Knoten zusammenhängen. Zu Beginn ist noch keine Kante in den Spannbaum eingetragen, daher ist jeder Knoten für sich in einer einzelnen Partition. Wenn eine Kante <math>(v_1,v_2)</math> hinzugefügt werden soll, wird überprüft, ob <math>v_1</math> und <math>v_2</math> in verschiedenen Partitionen liegen. Dazu dient die Operation Find(x): Sie liefert einen Repräsentanten der Partition, in dem der Knoten x liegt. Wenn Find(<math>v_1</math>) und Find(<math>v_2</math>) verschiedene Ergebnisse liefern, dann kann die Kante hinzugefügt werden und die Partitionen der beiden Knoten werden vereinigt (Union). Ansonsten würde durch Hinzunehmen der Kante ein Kreis entstehen, die Kante wird also verworfen. Insgesamt wird die Operation Find <math>2\cdot \left|E\right|</math> (für jede Kante) und die Operation Union <math>\left|V\right|-1</math> mal aufgerufen. Bei Verwenden der Heuristiken Union-By-Size und Pfadkompression ergibt eine amortisierte Laufzeitanalyse für den Algorithmus eine Komplexität von <math>\mathcal{O}(\left|E\right| \cdot \alpha( \left|V\right|))</math> (s. Laufzeiten).
Parallele Implementierung
Aufgrund von Datenabhängigkeiten zwischen den Iterationen lässt sich der Algorithmus von Kruskal grundsätzlich schwer parallelisieren. Es ist jedoch möglich, das Sortieren der Kanten zu Beginn parallel auszuführen oder alternativ eine parallele Implementation eines Binären Heaps zu verwenden, um in jeder Iteration die Kante mit dem kleinsten Gewicht zu finden.<ref>{{#invoke:Vorlage:Literatur|f}}</ref> Durch paralleles Sortieren, was auf <math>O(n \cdot \log n)</math> Prozessoren in <math>O(n)</math> Zeit möglich ist<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= 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
}}{{#if: Vorlage:Cite book/ParamBool
}}{{#if: Vorlage:Cite book/ParamBool
| Vorlage:Cite book/Meldung
}}{{#if: Vorlage:Cite book/ParamBool
}}{{#if: Vorlage:Cite book/ParamBool
}}{{#if: Vorlage:Cite book/ParamBool
}}{{#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:412–413|^^||+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>, kann die Laufzeit des Algorithmus auch bei zuvor unsortierten Kanten auf <math>O(|E| \cdot \log^*|V|)</math> reduziert werden.
Eine Variante des Algorithmus von Kruskal namens Filter-Kruskal wurde von Osipov et al.<ref name="osipov2009">{{#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: Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments (ALENEX). Society for Industrial and Applied Mathematics
|| 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:Osipov|^^||+1}}{{#ifeq:^^|^^||+1}}{{#ifeq:^^|^^||+1}} > 1
| Vorlage:Cite book/Meldung
}}</ref> beschrieben und eignet sich besser zur Parallelisierung. Die grundlegende Idee besteht darin, die Kanten in ähnlicher Weise wie bei Quicksort zu partitionieren und anschließend Kanten auszusortieren, welche Knoten im gleichen Teilbaum verbinden, um somit die Kosten für die Sortierung zu verringern. Der Algorithmus wird im folgenden Pseudocode dargestellt.
FILTER-KRUSKAL(G):
1 if |G.E| < KruskalThreshhold:
2 return KRUSKAL(G)
3 pivot = CHOOSE-RANDOM(G.E)
4 <math>E_{<=}</math>, <math>E_{>}</math> = PARTITION(G.E, pivot)
5 A = FILTER-KRUSKAL(<math>E_{<=}</math>)
6 <math>E_{>}</math> = FILTER(<math>E_{>}</math>)
7 A = A ∪ FILTER-KRUSKAL(<math>E_{>}</math>)
8 return A
PARTITION(E, pivot):
1 <math>E_{<=}</math> = ∅, <math>E_{>}</math> = ∅
2 foreach (u, v) in E:
3 if weight(u, v) <= pivot:
4 <math>E_{<=}</math> = <math>E_{<=}</math> ∪ {(u, v)}
5 else
6 <math>E_{>}</math> = <math>E_{>}</math> ∪ {(u, v)}
5 return <math>E_{<=}</math>, <math>E_{>}</math>
FILTER(E):
1 <math>E_{filtered}</math> = ∅
2 foreach (u, v) in E:
3 if FIND-SET(u) ≠ FIND-SET(v):
4 <math>E_{filtered}</math> = <math>E_{filtered}</math> ∪ {(u, v)}
5 return <math>E_{filtered}</math>
Filter-Kruskal eignet sich besser zur Parallelisierung, da sowohl das Sortieren und Partitionieren als auch das Filtern einfach parallel ausgeführt werden kann, indem die Kanten zwischen den Prozessoren aufgeteilt werden.<ref name="osipov2009" />
Weitere Varianten für eine Parallelisierung von Kruskals Algorithmus sind ebenfalls möglich. So besteht zum Beispiel die Möglichkeit, den sequentiellen Algorithmus auf mehreren Teilgraphen parallel auszuführen, um diese dann zusammenzuführen bis schlussendlich nur noch der finale minimale Spannbaum übrigbleibt<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: Transactions on Engineering Technologies.
|| 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:Lončar|^^||+1}}{{#ifeq:^^|^^||+1}}{{#ifeq:^^|^^||+1}} > 1
| Vorlage:Cite book/Meldung
}}</ref>. Eine simplere Form des Filter-Kruskals, bei welchem Hilfsthreads benutzt werden, um Kanten, die eindeutig nicht Teil des minimalen Spannbaums sind, im Hintergrund zu entfernen, kann ebenfalls verwendet werden<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: Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), 2012 IEEE 26th International
|| 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:Katsigiannis|^^||+1}}{{#ifeq:^^|^^||+1}}{{#ifeq:^^|^^||+1}} > 1
| Vorlage:Cite book/Meldung
}}</ref>.
Sonstiges
Der Algorithmus diente Kruskal ursprünglich als Hilfsmittel für einen vereinfachten Beweis, dass ein Graph mit paarweise verschiedenen Kantengewichten einen eindeutigen minimalen Spannbaum besitzt.
Neben dem Algorithmus von Kruskal gibt es auch noch weitere Algorithmen zur Berechnung minimaler Spannbäume ungerichteter Graphen, wie zum Beispiel den Algorithmus von Prim oder den Algorithmus von Borůvka (siehe auch Spannbaum).
Weblinks
|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 }}
|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: Kruskal's algorithm
| {{#ifeq: {{#invoke:Str|left|kruskal's algorithm|9}}
| category:
| FEHLER: Ohne Category: angeben!}}}}Vorlage:Wikidata-Registrierung
- <templatestyles src="Webarchiv/styles.css" />{{#if:20160314221605
| {{#ifeq: 20160314221605 | *
| {{#if: Interaktives Applet zum Lernen, Ausprobieren und Demonstrieren des Algorithmus | {{#invoke:WLink|getEscapedTitle|Interaktives Applet zum Lernen, Ausprobieren und Demonstrieren des Algorithmus}} | {{#invoke:Webarchiv|getdomain|http://www-m9.ma.tum.de/graph-algorithms/mst-kruskal/index_de.html}} }} (Archivversionen)
| {{#iferror: {{#time: j. F Y|20160314221605}}
| {{#if: || }}Der Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
| {{#if: Interaktives Applet zum Lernen, Ausprobieren und Demonstrieren des Algorithmus | {{#invoke:WLink|getEscapedTitle|Interaktives Applet zum Lernen, Ausprobieren und Demonstrieren des Algorithmus}} | {{#invoke:Webarchiv|getdomain|http://www-m9.ma.tum.de/graph-algorithms/mst-kruskal/index_de.html}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer }} vom {{#time: j. F Y|20160314221605}} im Internet Archive{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
}}
}}
| {{#if:
| {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
| {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
| 16= {{#if: Interaktives Applet zum Lernen, Ausprobieren und Demonstrieren des Algorithmus | {{#invoke:WLink|getEscapedTitle|Interaktives Applet zum Lernen, Ausprobieren und Demonstrieren des Algorithmus}} | {{#invoke:Webarchiv|getdomain|http://www-m9.ma.tum.de/graph-algorithms/mst-kruskal/index_de.html}} }} {{#ifeq: | [] | [ | ( }}{{#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: Interaktives Applet zum Lernen, Ausprobieren und Demonstrieren des Algorithmus | {{#invoke:WLink|getEscapedTitle|Interaktives Applet zum Lernen, Ausprobieren und Demonstrieren des Algorithmus}} | {{#invoke:Webarchiv|getdomain|http://www-m9.ma.tum.de/graph-algorithms/mst-kruskal/index_de.html}} }} {{#ifeq: | [] | [ | ( }}{{#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!{{#if: || }}
}}
| c|{{{webciteID}}}}} {{#if: Interaktives Applet zum Lernen, Ausprobieren und Demonstrieren des Algorithmus | {{#invoke:WLink|getEscapedTitle|Interaktives Applet zum Lernen, Ausprobieren und Demonstrieren des Algorithmus}} | {{#invoke:Webarchiv|getdomain|http://www-m9.ma.tum.de/graph-algorithms/mst-kruskal/index_de.html}} }} ({{#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: Interaktives Applet zum Lernen, Ausprobieren und Demonstrieren des Algorithmus | {{#invoke:WLink|getEscapedTitle|Interaktives Applet zum Lernen, Ausprobieren und Demonstrieren des Algorithmus}} | {{#invoke:Webarchiv|getdomain|http://www-m9.ma.tum.de/graph-algorithms/mst-kruskal/index_de.html}} }}
}}}}}}}}{{#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:20160314221605|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
| {{#if: || }}{{#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}}|}}
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
| }}
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
}}
| {{#if:
| {{#if: || }}{{#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/graph-algorithms/mst-kruskal/index_de.html}}
|| {{#if: || }}
}}{{#if: Interaktives Applet zum Lernen, Ausprobieren und Demonstrieren des Algorithmus
| {{#if: {{#invoke:WLink|isBracketedLink|Interaktives Applet zum Lernen, Ausprobieren und Demonstrieren des Algorithmus}}
| {{#if: || }}
}}
| {{#if: || }}
}}{{#switch:
|addlarchives|addlpages= {{#if: || }}{{#if: 1 |}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
}}{{#ifeq: {{#invoke:Str|find|http://www-m9.ma.tum.de/graph-algorithms/mst-kruskal/index_de.html%7Carchiv}} |-1
|| {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://www-m9.ma.tum.de/graph-algorithms/mst-kruskal/index_de.html%7C4}}%7Chttp}} |-1
|| {{#switch: {{#invoke:Webarchiv|getdomain|http://www-m9.ma.tum.de/graph-algorithms/mst-kruskal/index_de.html }}
| abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org =
| #default = {{#if: || }}{{#if: 1 |}}{{#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}}
}}
}}
}}
- Ronny Harbich: <templatestyles src="Webarchiv/styles.css" />{{#if:
| {{#ifeq: {{{wayback}}} | *
| {{#if: Vollständiger Beweis zur Korrektheit des Algorithmus von Kruskal | {{#invoke:WLink|getEscapedTitle|Vollständiger Beweis zur Korrektheit des Algorithmus von Kruskal}} | {{#invoke:Webarchiv|getdomain|http://www.uni-magdeburg.de/harbich/mst.php}} }} (Archivversionen)
| {{#iferror: {{#time: j. F Y|{{{wayback}}}}}
| {{#if: || }}Der Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
| {{#if: Vollständiger Beweis zur Korrektheit des Algorithmus von Kruskal | {{#invoke:WLink|getEscapedTitle|Vollständiger Beweis zur Korrektheit des Algorithmus von Kruskal}} | {{#invoke:Webarchiv|getdomain|http://www.uni-magdeburg.de/harbich/mst.php}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer }} vom {{#time: j. F Y|{{{wayback}}}}} im Internet Archive{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
}}
}}
| {{#if:
| {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
| {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
| 16= {{#if: Vollständiger Beweis zur Korrektheit des Algorithmus von Kruskal | {{#invoke:WLink|getEscapedTitle|Vollständiger Beweis zur Korrektheit des Algorithmus von Kruskal}} | {{#invoke:Webarchiv|getdomain|http://www.uni-magdeburg.de/harbich/mst.php}} }} {{#ifeq: | [] | [ | ( }}{{#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: Vollständiger Beweis zur Korrektheit des Algorithmus von Kruskal | {{#invoke:WLink|getEscapedTitle|Vollständiger Beweis zur Korrektheit des Algorithmus von Kruskal}} | {{#invoke:Webarchiv|getdomain|http://www.uni-magdeburg.de/harbich/mst.php}} }} {{#ifeq: | [] | [ | ( }}{{#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!{{#if: || }}
}}
| c|{{{webciteID}}}}} {{#if: Vollständiger Beweis zur Korrektheit des Algorithmus von Kruskal | {{#invoke:WLink|getEscapedTitle|Vollständiger Beweis zur Korrektheit des Algorithmus von Kruskal}} | {{#invoke:Webarchiv|getdomain|http://www.uni-magdeburg.de/harbich/mst.php}} }} ({{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
}}
| {{#if: 20130106024716
| Vorlage:Webarchiv/Today
| {{#if:
| Vorlage:Webarchiv/Generisch
| {{#if: Vollständiger Beweis zur Korrektheit des Algorithmus von Kruskal | {{#invoke:WLink|getEscapedTitle|Vollständiger Beweis zur Korrektheit des Algorithmus von Kruskal}} | {{#invoke:Webarchiv|getdomain|http://www.uni-magdeburg.de/harbich/mst.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:|1|0}}{{#if:|+1}}{{#if:20130106024716|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
| {{#if: || }}{{#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}}|}}
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
| }}
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
}}
| {{#if:
| {{#if: || }}{{#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.uni-magdeburg.de/harbich/mst.php}}
|| {{#if: || }}
}}{{#if: Vollständiger Beweis zur Korrektheit des Algorithmus von Kruskal
| {{#if: {{#invoke:WLink|isBracketedLink|Vollständiger Beweis zur Korrektheit des Algorithmus von Kruskal}}
| {{#if: || }}
}}
| {{#if: || }}
}}{{#switch:
|addlarchives|addlpages= {{#if: || }}{{#if: 1 |}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
}}{{#ifeq: {{#invoke:Str|find|http://www.uni-magdeburg.de/harbich/mst.php%7Carchiv}} |-1
|| {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://www.uni-magdeburg.de/harbich/mst.php%7C4}}%7Chttp}} |-1
|| {{#switch: {{#invoke:Webarchiv|getdomain|http://www.uni-magdeburg.de/harbich/mst.php }}
| abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org =
| #default = {{#if: || }}{{#if: 1 |}}{{#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 | *
| {{#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: || }}Der 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: | [] | [ | ( }}{{#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: | [] | [ | ( }}{{#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: | [] | [ | ( }}{{#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!{{#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}} }} ({{#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: || }}{{#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}}|}}
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
| }}
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
}}
| {{#if:
| {{#if: || }}{{#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: || }}
}}{{#if: Anschauliche Darstellung des Algorithmus im Rahmen des Informatikjahres, 2006
| {{#if: {{#invoke:WLink|isBracketedLink|Anschauliche Darstellung des Algorithmus im Rahmen des Informatikjahres, 2006}}
| {{#if: || }}
}}
| {{#if: || }}
}}{{#switch:
|addlarchives|addlpages= {{#if: || }}{{#if: 1 |}}{{#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 |}}{{#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
<references />
- Wikipedia:Vorlagenfehler/Parameter:URL
- Wikipedia:Vorlagenfehler/Parameter:Linktext
- Wikipedia:Vorlagenfehler/Parameter:Datum
- Wikipedia:Vorlagenfehler/Vorlage:"
- Wikipedia:Weblink offline fix-attempted
- Wikipedia:Vorlagenfehler/Vorlage:Toter Link
- Wikipedia:Vorlagenfehler/Vorlage:Toter Link/URL fehlt
- Wikipedia:Vorlagenfehler/Schwesterprojekt
- Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
- Wikipedia:Vorlagenfehler/Vorlage:Webarchiv/Archiv-URL
- Wikipedia:Vorlagenfehler/Vorlage:Webarchiv/Linktext fehlt
- Optimierungsalgorithmus
- Graphsuchalgorithmus