Diskussion:Algorithmus von Kruskal

Laufzeit falsch

Die Abschätzung der Laufzeit ist falsch was |E|*log(|V|) betrifft. Der komplette Graph kann |V|^2 Kanten besitzten und nicht nur |V|. Die Aussage über den zusammenhängenden Graphen ist an dieser Stelle überflüssig. Diese gibt nur eine untere und keine obere Schranke für die Kantenanzahl, die die obere Schranke der Laufzeit verändern könnte! Die Sortierung der Kanten bei Kruskal benötigt alleine schon |E|*log(|E|) Laufzeit. --Tillschaefer (Diskussion) 14:41, 1. Aug. 2012 (CEST)

Laufzeit sonstiges

Ich habe die Laufzeitbetrachtung umformuliert, so dass keine Annahmen über die implementierung (Integer, Pointer...) getroffen werden. ursprünglich:

Der Trick ist, sich zu jedem Knoten die Komponente zu merken und wieviele Knoten diese enthält. Allerdings hat man nun das Problem, dies beim Einfügen einer Kante ebenfalls in konstanter Zeit zu updaten. Dies ist nur amortisiert möglich (siehe Zu jedem Knoten existiert ein Pointer auf einen Integer, welches die Größe der Komponente angibt. Knoten der selben Komponente zeigen auf die selbe Integer-Variable (und die verschiedener Komponenten auf verschiedene Variablen). Werden zwei Komponenten durch eine neue Kante verbunden, so wird der Wert der Integervariablen entsprechend erhöht und die Pointer der ehemals kleineren Komponente auf den Integer der ehemals größeren Komponente "umgebogen". Es läßt sich zeigen, daß in der Summe höchstens 2n mal (? stimmt das Jakob?) Pointer umgebogen werden müssen, so daß im Schnitt höchstens 2 Pointer umgebogen werden müssen, dieses Umbiegen amortisiert also nur konstant viel Zeit benötigt, obwohl bei einer Verschmelzung von zwei Komponenten bis zu n/2 Pointer pro Schritt umgebogen werden müssen.

-- JakobVoss 15:37, 23. Feb. 2003 Signatur nachträglich ergänzt --Daniel Mex 23:43, 17. Jul. 2007 (CEST)

bist du dir sicher daß amortisiert nur log(n) rauskommt? wenn ich zeit habe, werde ich irgendwann mal nachschauen... --Coma 19:49, 23. Feb 2003 (CET)

...Nach der beschriebenen Implementierung wird jedenfalls schlimmstenfalls die Hälfte der Knoten log(n) mal in eine andere Komponente verschoben. Das ist zum Beispiel der fall, wenn zuerst paarweise Knoten verbunden werden, dann die Paare zu 4-er-Komponenten etc. -- JakobVoss 12:28, 24. Feb 2003 (CET)

...Du hast mich überzeugt :-), eventuell sollte das auch in den Artikel rein... :--Coma 14:02, 24. Feb 2003 (CET)

Beispielgrafik

Was spricht eigentlich gegen den Rahmen um das Bild? (Version vom 11. Juli 2005?)

http://de.wikipedia.org/w/index.php?title=Algorithmus_von_Kruskal&oldid=7608946

Irgendjemand nimmt den immer weg. Ich finde allerdings dass es mit Rahmen wesentlich besser aussieht. Gibt es besondere Gründe gegen den Rahmen? --Cerno 10:21, 15. Jul 2005 (CEST)

Antwort: Der Rahmen ist unnötig und stört den Textfluss. Der Rahmen wäre sinnvoll, wenn das Bild den Artikel nur ergänzt. Hier gehört das Bild aber essenziel zum Artikel. --Squizzz 11:25, 15. Jul 2005 (CEST)

Hm, bei mir hat er den Textfluss nicht gestört, aber das mag browserabhängig sein. Ich fand ihn eigentlich schicker, zumal das Bild in meinem Browser genau so aussah wie jetzt, halt nur mit Rahmen. Aber von mir aus kann das so bleiben --Cerno 16:33, 20. Jul 2005 (CEST)

Antwort: Mit Textfluss stören meine ich, dass ein Rahmen das Bild vom Text absetzt. Vielleicht kann ich den Unterschied durch ein analoges Textbeispiel verdeutlichen: „blabla Bild blabla“ vs. „blabla | Bild | blabla“. --Squizzz 18:07, 20. Jul 2005 (CEST)

Okay, ist wohl Geschmackssache, von mir aus kann das so bleiben. :) --Cerno 12:40, 21. Jul 2005 (CEST)

Super! Die Beschreibung und das anschließende Bild (als Beispiel) erleichtern einem das verstehen des Algorithmuses bestens.

Ich möchte nur mal auf den Dijkstra Algorithmus verweisen, dort fehlt so etwas leider komplett. Also meiner Meinung nach sollte das so bleiben wie es derzeit ist ;-) --129.69.197.208 13:14, 1. Okt. 2007 (CEST)- 13:14, 1. Okt 2007 (CEST)

kleiner Grammatik-/Rechtschreib-Fehler

ursprünglich im letzten Satz: ... in eine andere>n< Komponente verschoben werden. ich hab's umgeändert in: ... in eine andere Komponente verschoben werden.

-- 84.174.113.22 13:04, 27. Jul. 2005 Signatur nachträglich ergänzt --Daniel Mex 23:43, 17. Jul. 2007 (CEST)

Beweis /Überarbeiten ?

Es fehlt noch der Teilbeweis für die Minimalität. --Ronnydotnet 13:57, 12. Jul 2006 (CEST)

Kantenfarbe/-gewichtung

Im Algorithmus wird ein nur ein kantengefärbter Graph benutzt, nicht ein kantengewichteter. Ist das wichtig? Wäre es sinnvoll, analog zum Artikel Typen_von_Graphen_in_der_Graphentheorie, das Kantengewicht $f$ zu nennen?

R. Möws 00:45, 5. Jul 2006 (CEST)

Stimmt. Es wird nur ein kantengefärbter Graph benutzt. Ich denke man kann das ohne Probleme auf kantengewichte Graphen erweitern: $w:E\rightarrow \mathbb {R}$. Allerdings sollte die Kantengewichtsfunktion $w$ auch weiterhin so bezeichnet werden, da Gewicht im Englischen weigth (w) heißt (die anderen Begriffe in der Graphenthorie haben auch englische Abkürzungen). --Ronnydotnet 19:50, 5. Jul 2006 (CEST)

Fehlender Korrektheitsbeweis

Liebe Mit-Bearbeiter der Seite zum Algorithmus von Kruskal: Ich habe am 10.4.06 den Korrektheitsbeweis zum Algorithmus von Kruskal verbessert, nachdem die vorige Version nicht gestimmt hat (ich hatte mich leider beim Vorbereiten auf eine Vorlesung auf die Wikipedia verlassen anstatt in der bibliothek ein Buch zu suchen, und mitten im Reden komme ich dann drauf, dass der Beweis nicht stimmt). Ich sehe heute zufaellig, dass die aktuelle Version des Artikels (heute ist der 19.11.06) den Korrektheitsbeweis nur mehr zum Teil enthaelt: der Beweis der Minimalitaet des erzeugten Spannbaumes ist verschwunden. Nachdem ich wenig Lust habe, den Artikel schon wieder zu korrigieren, moechte ich nur hier deponieren, dass alle die wollen, einen korrekten Beweis in der Version vom 10.4. nach meinen Korrekturen nachlesen koennen. Herzliche Gruesse, J. Wallner (TU Wien)

Der Beweis ist aber leider nicht richtig. Unter www-e.uni-magdeburg.de/harbich/mst.php gibt's einen korrekten Beweis. Der müsste allerdings noch auf die Definitionen der Graphentheorie der Wikipedia angepasst werden. --Ronnydotnet 21:51, 22. Nov. 2006 (CET)

Ich habe einen Korrektheitsbeweis aus einer anderen Quelle eingefügt, finde aber, dass er für den Artikel eigentlich schon zu komplex ist. --HeikoTheissen 19:11, 18. Mai 2007 (CEST)

Zeitkomplexität

Die Zeitkomlexität ist O(m*log(n)) und nicht O(m*log(m)). Setzt sich so zusammen: Bei der Verwendung von Union-Find Strukturen und Priority Queues ergeben sich logarithmische Laufzeiten für ExtractMin, Find und Union (amortisiert). Das Ganze wird m - Mal durchlaufen.

Habs geändert. -- 88.217.37.82 14:37, 26. Mär. 2007 Signatur nachträglich ergänzt --Daniel Mex 23:43, 17. Jul. 2007 (CEST)

Hab den ganzen Abschnitt überarbeitet und insbesondere die Union-Find-Struktur mit reingebracht. Gibt es irgendwo auf der Wikipedia schon eine Erläuterung von $\log ^{*}$? Samx 14:47, 18. Jul. 2007 (CEST)

Ich habe nichts gefunden, aber ich kannte diese Notation bisher auch noch nicht. --Daniel Mex 20:30, 18. Jul. 2007 (CEST)

Eine Zeitkomplexität für eine Sortierung anzugeben macht ohne entsprechenden Vermerk auf den Sortieralgorithmus wenig Sinn. Wie wird denn sortiert?! Heap-Sort, Merge-Sort?! Könnte genauso gut mit Bubble Sort (${\mathcal {O}}(n^{2})$) sortiert werden. --77.180.220.225 17:43, 28. Jun. 2016 (CEST)

Ein schlechter Sortieralgorithmus macht als Komponente einer Zeitabschätzung keinen Sinn. Man nimmt natürlich den besten, oder wenigstens einen sehr guten Algorithmus, z.B. Heap-Sort oder Merge-Sort. Der „Fachmann“ weiß das, aber für den Laien (und für Oma) könnte man einen passenden Algorithmus andeuten: Das Sortieren benötigt eine Laufzeit von ${\mathcal {O}}{\bigl (}\left|E\right|\cdot \log(\left|E\right|){\bigr )}$ (z.B. Mergesort). --H.Marxen (Diskussion) 18:44, 28. Jun. 2016 (CEST)

Formalisierter Algorithmus - Algorithmus - Pseudocode

Habe den Pseudocode hinsichtlich der Zyklenfreiheit und Vermeidung math. Symbole verändert, fühle mich als fast-nie-edit-Wikipedianer allerdings nicht berufen dies direkt einzuarbeiten:

 G = (V,E,w): ein zusammenhängender, ungerichteter, kantengewichteter Graph
 
 ''kruskal''(G)
 1  Sortiere die Kanten von G aufsteigend nach ihrem Kantengewicht.
 2  E' := leere Menge
 3  L := E
 4  '''solange''' L nicht leer
 5      wähle eine Kante e=(v1, v2) aus L mit kleinstem Kantengewicht
 6      entferne e aus L
 7      '''falls''' (v1 nicht in E') oder (v2 nicht in E')
 8          '''dann''' füge e zu E' hinzu
 9  M=(V,E') ist ein minimaler Spannbaum von G.

-- 89.15.37.158 19:46, 11. Jul. 2007 Signatur nachträglich ergänzt --Daniel Mex 23:43, 17. Jul. 2007 (CEST)

Mir gefällt dein Vorschlag zwar besser als der Pseudocode im Artikel, aber das Problem ist, dass dann jemand den Abschnitt Korrektheitsbeweis wieder anpassen müsste. Ob man Formelsymbole im Algorithmus haben will oder nicht, ist, denke ich, eher eine Geschmacksfrage. --Daniel Mex 23:51, 17. Jul. 2007 (CEST)

Verwandtschaft zum Algorithmus von Dijkstra

Ich finde, es sollte im Artikel erwähnt werden, dass die Algorithmen von Kruskal und Dijkstra recht ähnlich arbeiten, weiß aber noch nicht so recht, wo das reinpasst. Vielleicht im Abschnitt Formalisierter Algorithmus? --Daniel Mex 00:04, 13. Sep. 2007 (CEST)

Ähhm, welche Ähnlichkeiten siehst du bitte? --Koethnig 18:09, 13. Sep. 2007 (CEST)

Entschuldigung, ich merke gerade, dass ich die Algorithmen von Kruskal und Prim verwechselt habe. --Daniel Mex 19:47, 13. Sep. 2007 (CEST)

Ok, aber auch da sehe ich nicht, was da ähnlich ist?! --Koethnig 01:01, 14. Sep. 2007 (CEST)

Die beiden Algorithmen haben eine ähnliche bzw. meiner Ansicht nach sogar gleiche Struktur. Lediglich das Auswahlkriterium, nach dem die zu relaxierende Kante in jedem Schritt bestimmt wird, ist unterschiedlich. Ich schreibe die Algorithmen jetzt mal so hin, wie ich sie kennengelernt habe:

Dijkstra(G,w,s)
 1. Q ← newHeap(V)
 2. foreach vertex v in V do
 3.   d[v] ← ∞
 4. π[s] ← nil
 5. d[s] ← 0
 6. while Q ≠ Ø do
 7.   u ← Extract-Min(Q)
 8.   foreach vertex v in Adj[u] do
 9.     if d[v] > d[u] + w(u,v) then
10.       d[v] ← d[u] + w(u,v) 
11.       Heapify(Q)
12.       π[v] ← u
13. return π

Prim(G,w,s)
 1. Q ← newHeap(V)
 2. foreach vertex v in V do
 3.   d[v] ← ∞
 4. π[s] ← nil
 5. d[s] ← 0
 6. while Q ≠ Ø do
 7.   u ← Extract-Min(Q)
 8.   foreach vertex v in Adj[u] do
 9.     if d[v] > w(u,v) and v in Q then
10.       d[v] ← w(u,v) 
11.       Heapify(Q)
12.       π[v] ← u
13. return π

Als Schlüssel für den Heap Q dient das Feld d. Ich finde die Ähnlichkeit hier schon ziemlich auffällig. --Daniel Mex 21:14, 14. Sep. 2007 (CEST)

Wie schon im anderen Artikel erwähnt. Das ist unsinn. Ich kann auch für beliebe Alg. einen While-Schleife schreiben die immer gleich aussieht, bis auf das enthaltene Turing-Programm. --Koethnig 22:46, 19. Sep. 2007 (CEST)

Kantengewichte und maximaler Spannbaum

Ich finde die Einschränkung der Kantengewichte auf natürliche Zahlen nicht nachvollziehbar. Warum nicht auf $\mathbb {R}$ erweitern. Dies wurde zuvor schon einmal angesprochen. Wenn man das macht, ist auch der kurze Abschnitt zum maximalen Spannbaum zu verkürzen, indem man einfach definiert, dass die Gewichte negiert werden müssen.

Ich habe den Artikel so abgeändert, dass Kantengewichte reelle Zahlen sind. --Stefan Birkner 21:06, 7. Nov. 2008 (CET)

Greedy ließe sich auch auf ungewichtete Graphen anwenden. Das Sortieren der Kanten nach Gewichten würde einfach wegfallen. Man bekäme dann keinen minimalen Spannbaum, aber wenigstens irgendeinen Spannbaum. Ist ja auch schon was. Im ersten Textblock steht etwas über Sonderfälle. Da würde das hinpassen. --OnkelSchuppig (Diskussion) 13:21, 28. Nov. 2021 (CET)

Etwas irreführendes Beispiel

Liebe Leute, das Beispiel ist etwas irreführend da es suggeriert dass nach jedem Schritt Verbindungen gesucht werden, die zu Kreisen führen könnten. Es werden aber keine Kanten rot markiert, sondern einfach nur ggf. verworfen wenn sie dran sind und zu einem Kreis führen würden, würde man sie verwenden. -- 88.64.179.94 12:34, 10. Jun. 2009 (CEST)

Warum auf Kreisfreiheit prüfen?

Wenn der Ausgangsgraph kreisfrei wäre, dann hätten wir doch schon einen Minimal Spanning Tree; Aber in der Beschreibung unter Laufzeit lese ich: und dem Überprüfen, ob der Graph kreisfrei ist... Bei einer geeigneten Implementierung ist das Überprüfen auf Kreisfreiheit schneller möglich Das macht doch keinen Sinn!

Was man prüfen müsste, wäre: Ist der Graph zusammenhängend; denn nur, wenn er zusammenhängend ist, kann ein MST gebildet werden. (nicht signierter Beitrag von 2A01:C22:A450:4200:E805:3472:4903:55B (Diskussion) 20:47, 25. Nov. 2019 (CET))

Es ist auf Diskussionsseiten üblich, neue Beiträge hinten anzuhängen, nicht vorne einzufügen. Habe den neuen Abschnitt deswegen wieder nach hinten bewegt. Zum Inhalt...

Es geht nicht um die Kreisfreiheit des Ausgangsgraphen, sondern die des partiell konstruierten Kandidaten für den minimalen Spannbaum, inklusive neuer Kandidaten-Kante.

--H.Marxen (Diskussion) 00:39, 26. Nov. 2019 (CET)