Kantenauswahl bei Kruskal

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!

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!
giuley
Neuling
Neuling
Beiträge: 4
Registriert: 13. Sep 2016 12:44

Kantenauswahl bei Kruskal

Beitrag von giuley » 13. Sep 2016 12:56

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
Kruskal.png (63.47 KiB) 366 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

Benutzeravatar
sqrt(2)
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 201
Registriert: 12. Apr 2015 11:35

Re: Kantenauswahl bei Kruskal

Beitrag von sqrt(2) » 13. Sep 2016 13:00

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
Ich meine das liegt daran, dass weder c noch k in einer Ergebnismenge liegen.

EDIT: Falsche Antwort... :oops:
Zuletzt geändert von sqrt(2) am 13. Sep 2016 13:08, insgesamt 1-mal geändert.

giuley
Neuling
Neuling
Beiträge: 4
Registriert: 13. Sep 2016 12:44

Re: Kantenauswahl bei Kruskal

Beitrag von giuley » 13. Sep 2016 13:03

Das kann nicht sein, denn dann würde in diesem Beispiel b-4-l oder d-4-l gewählt werden.
Kruskal2.png
Kruskal2.png (68.08 KiB) 361 mal betrachtet
Es wird aber f-4-l gewählt :S

Benutzeravatar
sqrt(2)
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 201
Registriert: 12. Apr 2015 11:35

Re: Kantenauswahl bei Kruskal

Beitrag von sqrt(2) » 13. Sep 2016 13:05

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
Neuling
Neuling
Beiträge: 4
Registriert: 13. Sep 2016 12:44

Re: Kantenauswahl bei Kruskal

Beitrag von giuley » 13. Sep 2016 13:09

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

Antworten

Zurück zu „AuD: Arbeit mit Nabla“