Prim-lexikographisch?

FloT
Neuling
Neuling
Beiträge: 6
Registriert: 25. Apr 2015 11:21

Prim-lexikographisch?

Beitrag von FloT »

Hallo Zusammen,

Mir ist gerade eventuell ein Fehler beim Prim-algo aufgefallen.
Folgende Ausgangssituation nach Iteration 3:
Bild
Als nächster Knoten kommt nur h in Frage, weshalb es nun zwei Möglichkeiten gibt, entweder von d nach h oder von e nach h.
Laut Aufgabestellung ist Die Menge V lexikographisch sortiert und wird auch in dieser Reihenfolge durchlaufen, demnach sollte die Kante (d,h) gegenüber (e,h) bevorzugt werden.

Die Lösung sagt jedoch etwas anderes:
Bild
Seed: bc01c6c218a7a60465b7d91640d83034

Habe ich den Algorithmus falsch verstanden oder kann das abc nicht vollständig, oder stimmt da irgendwas nicht? :lol:
Danke für die Hilfe.

Grüße

Nullmann
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 139
Registriert: 21. Apr 2015 20:59

Re: Prim-lexikographisch?

Beitrag von Nullmann »

Wenn es zwei geich "schwere" Kanten zu einem Knoten gibt, dann wird diejenige Kante genommen, dessen Knoten zuerst in die Ergebnismenge hinzugefügt wurde.

In diesem Fall ist e sogar der Startknoten - er wurde also vor jedem anderen Knoten hinzugefügt und deshalb wird dort diese Kante verwendet.

(Im Algo von Prim ist es eigentlich egal, welche Kante man in so eienr Situation benutzt. Jedoch ist es in dieser Implementierung wie oben beschrieben.)

FloT
Neuling
Neuling
Beiträge: 6
Registriert: 25. Apr 2015 11:21

Re: Prim-lexikographisch?

Beitrag von FloT »

Ah gut zu wissen, danke sehr.

Nullmann
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 139
Registriert: 21. Apr 2015 20:59

Re: Prim-lexikographisch?

Beitrag von Nullmann »

Eine kleine Hilfestellung kann man sich dabei selbst geben: Wenn man die hinzugefügten Kanten untereinander einfügt (d.h. erste Kante ganz oben, letzte ganz unten), muss man in solch einem Fall einfach schauen, welcher Knoten weiter oben in der Liste steht. Dieser wurde dann natürlich zuerst hinzugefügt und man muss nicht im nachhinein nachvollziehen, welche Schritte man vorher unternommen hat.

Antworten

Zurück zu „Archiv“