Prim:Wie wird lexikografisch sortiert?

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!
WagAd
Erstie
Erstie
Beiträge: 11
Registriert: 19. Feb 2017 21:25

Prim:Wie wird lexikografisch sortiert?

Beitrag von WagAd » 7. Apr 2017 10:52

Guten Morgen,

Ich habe eine Frage zu dem Prim Algorithmus. Und zwar frage ich mich, wie lexikografisch sortiert wird.
Szenario:

Folgende Kanten haben die gleiche Kantenlänge (z.b: 5):
- (c,d)
- (b,f)
- (b,g)
- (a,b)

Wie würden diese lexikografisch sortiert werden? Anhand des 1. Knoten oder doch des 2. Knotens?

Danke & Grüße.
Zuletzt geändert von WagAd am 7. Apr 2017 13:23, insgesamt 2-mal geändert.

Verenax
Neuling
Neuling
Beiträge: 7
Registriert: 23. Apr 2016 15:35

Re: (Prim&Kruskal): Wie wird lexikografisch sortiert?

Beitrag von Verenax » 7. Apr 2017 12:29

Bei Kruskal spielt das ja garkeine Rolle. Du sortierst die Kanten ja nur nach der vorgegebenen Kantenreihenfolge in die Menge der Mengen UF ein. Die nach den Iterationen nicht benutzten Knoten werden jeweils in eine eigene Menge in UF gepackt, aber nicht besonders geordnet. Zumindest zeigt Nabla da dann keinen Fehler an, auch wenn in der Lösung eine andere Reihenfolge bei UF gewählt wurde. Wonach das dann aber sortiert ist habe ich selbst nicht herausfinden können :oops:

WagAd
Erstie
Erstie
Beiträge: 11
Registriert: 19. Feb 2017 21:25

Re: (Prim&Kruskal): Wie wird lexikografisch sortiert?

Beitrag von WagAd » 7. Apr 2017 12:41

Verenax hat geschrieben:Bei Kruskal spielt das ja garkeine Rolle. Du sortierst die Kanten ja nur nach der vorgegebenen Kantenreihenfolge in die Menge der Mengen UF ein. Die nach den Iterationen nicht benutzten Knoten werden jeweils in eine eigene Menge in UF gepackt, aber nicht besonders geordnet. Zumindest zeigt Nabla da dann keinen Fehler an, auch wenn in der Lösung eine andere Reihenfolge bei UF gewählt wurde. Wonach das dann aber sortiert ist habe ich selbst nicht herausfinden können :oops:
Ja, hast Recht, bei Kruskal spielt das keine Rolle :oops:
Ansonsten warte ich noch auf eine Antwort, ob und wie es lexikografisch sortiert werden sollte :?

yi_
Neuling
Neuling
Beiträge: 9
Registriert: 6. Aug 2016 18:07

Re: Prim:Wie wird lexikografisch sortiert?

Beitrag von yi_ » 7. Apr 2017 21:00

Hi WagAd,
soweit ich das verstanden und anhand von Nabla Aufgaben beobachten konnte, wird der lexikographisch erste neue Knoten genommen. An der Tabelle lässt es sich also nicht ablesen, sondern es geht um die noch wartenden Knoten in Q. Wenn dort zwei mit gleicher Entfernung warten, wird der lexikographisch erste genommen. Allerdings frage ich mich dann, wozu der Hinweis "Die Menge V ist lexikographisch sortiert und wird auch in dieser Reihenfolge durchlaufen." da steht. Probier das also am besten nochmal in Nabla aus.
Hier im Forum gab es irgendwo auch die Frage nach dem Sonderfall, wenn es zwei gleich lange Kanten in den gleichen Knoten gibt. Dann wird die Kante von dem Knoten aus genommen, der zuerst besucht wurde. Ich schätze aber, dass so ein Fall in der Klausur nicht drankommt.

Lieben Gruß
yi

WagAd
Erstie
Erstie
Beiträge: 11
Registriert: 19. Feb 2017 21:25

Re: Prim:Wie wird lexikografisch sortiert?

Beitrag von WagAd » 8. Apr 2017 09:32

yi_ hat geschrieben: Hier im Forum gab es irgendwo auch die Frage nach dem Sonderfall, wenn es zwei gleich lange Kanten in den gleichen Knoten gibt. Dann wird die Kante von dem Knoten aus genommen, der zuerst besucht wurde. Ich schätze aber, dass so ein Fall in der Klausur nicht drankommt.
Hi yi,
Das funktioniert so wirklich. Habe ich wohl übersehen/vergessen.
Danke :D

Antworten

Zurück zu „AuD: Arbeit mit Nabla“