Seite 1 von 1

Prim:Wie wird lexikografisch sortiert?

Verfasst: 7. Apr 2017 10:52
von WagAd
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.

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

Verfasst: 7. Apr 2017 12:29
von Verenax
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:

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

Verfasst: 7. Apr 2017 12:41
von WagAd
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 :?

Re: Prim:Wie wird lexikografisch sortiert?

Verfasst: 7. Apr 2017 21:00
von yi_
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

Re: Prim:Wie wird lexikografisch sortiert?

Verfasst: 8. Apr 2017 09:32
von WagAd
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