Hallo,
Folgendes Problem:
Wenn ich 2 oder mehr Kanten zur Auswahl habe, die beide die Länge x haben, welche wird dann ausgewählt?
In diesem Beispiel wird als nächstes c-6-k ausgewählt. Aber warum nicht c-6-f, f-6-k oder a-6-e?
Dieses Problem tritt gerade bei diesen Nabla Aufgaben sehr oft auf, da es in jeder Aufgabe mehrere gleichlange Kanten gibt.
Viele Grüße,
Giuliano
Kantenauswahl bei Kruskal
Moderator: Algorithmen und Datenstrukturen
Forumsregeln
Bei Postings zu Algorithmus X lassen Sie Ihren Betreff bitte mit
"X: " beginnen, bei allgemeinen Postings zu Nabla bitte mit "Nabla: ", jeweils gefolgt von einer möglichst präzisen Überschrift, danke!
Bei Postings zu Algorithmus X lassen Sie Ihren Betreff bitte mit
"X: " beginnen, bei allgemeinen Postings zu Nabla bitte mit "Nabla: ", jeweils gefolgt von einer möglichst präzisen Überschrift, danke!
Re: Kantenauswahl bei Kruskal
Ich meine das liegt daran, dass weder c noch k in einer Ergebnismenge liegen.giuley hat geschrieben:Hallo,
Folgendes Problem:
Wenn ich 2 oder mehr Kanten zur Auswahl habe, die beide die Länge x haben, welche wird dann ausgewählt?
In diesem Beispiel wird als nächstes c-6-k ausgewählt. Aber warum nicht c-6-f, f-6-k oder a-6-e?
Kruskal.png
Dieses Problem tritt gerade bei diesen Nabla Aufgaben sehr oft auf, da es in jeder Aufgabe mehrere gleichlange Kanten gibt.
Viele Grüße,
Giuliano
EDIT: Falsche Antwort...

Zuletzt geändert von sqrt(2) am 13. Sep 2016 13:08, insgesamt 1-mal geändert.
Re: Kantenauswahl bei Kruskal
Das kann nicht sein, denn dann würde in diesem Beispiel b-4-l oder d-4-l gewählt werden.
Es wird aber f-4-l gewählt :SRe: Kantenauswahl bei Kruskal
Tut mir leid, war eine Falsche Antwort.
Die Kanten die gewählt werden sind schon in der richtigen Reihenfolge. Sind die Knoten nicht in der selben Ergebnismenge, dann wählt man die Kante aus die als nächstes kommt. Andernfalls überspringt man diese und zählt eine Iteration hoch.
Die Kanten die gewählt werden sind schon in der richtigen Reihenfolge. Sind die Knoten nicht in der selben Ergebnismenge, dann wählt man die Kante aus die als nächstes kommt. Andernfalls überspringt man diese und zählt eine Iteration hoch.
Re: Kantenauswahl bei Kruskal
Ach mist... ja ich habe die vorgegebene Reihenfolge übersehen. Vielen dank für den Hinweis 
