Kantenauswahl bei Kruskal

[giuley]

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 (63.47 KiB) 629 mal betrachtet

Dieses Problem tritt gerade bei diesen Nabla Aufgaben sehr oft auf, da es in jeder Aufgabe mehrere gleichlange Kanten gibt.

Viele Grüße,
Giuliano

[sqrt(2)]

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

Ich meine das liegt daran, dass weder c noch k in einer Ergebnismenge liegen.

EDIT: Falsche Antwort...

[giuley]

Das kann nicht sein, denn dann würde in diesem Beispiel b-4-l oder d-4-l gewählt werden.

Kruskal2.png (68.08 KiB) 624 mal betrachtet

Es wird aber f-4-l gewählt :S

[sqrt(2)]

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.

[giuley]

Ach mist... ja ich habe die vorgegebene Reihenfolge übersehen. Vielen dank für den Hinweis