WS09 - Aufgabe 7d) Prims Algorithmus

Bachelor Algorithmen und Datenstrukturen
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

WS09 - Aufgabe 7d) Prims Algorithmus
Hallo,

Zu WS09-Aufgabe 7d)/Prims Algorithmus.
gegeben ist dieser ungerichteter Graph aus den Knoten A bis H mit folgenden Gewichten:

AB = 4
AC = 2
BC = 1
BF = 1
CD = 5
DE = 3
EF = 1
EG = 1
FH = 4
GH = 1

Wird der Algorithmus von Prim ausgehen von D angewendet, erhält man nach einigen Iterationen einen Teilgraphen (die vier fetten Kanten).

Welche Kanten werden vom Algorithmus als nächstes in Betracht gezogen?
Die FSI-Lösung gibt die Kanten EG, HF, BA, CA und DC an. Warum wird hier DC aufgeführt? Ist das der Fall da diese Kante “betrachtet” aber nicht hinzugefügt wird?
Warum wird dann nicht auch die Kante GH “betrachtet”?

Liebe Grüße
Speedy

P.S. wie beschreibt man hier im Forum am besten Graphen?
Gibt es eine Seite auf der man Graphen schnell erstellen und dann auf hier verlinken kann?

3

Emfehle nochmal mal selbst prim zu machen und auf den unterschied zum kruskal zu achten
Deine Frage ist über das grundlegenste wie prim funktioniert

4

Die Antwort ist natürlich ganz simpel falls jemand mal auf dem selben Schlauch sitzt:

  1. Zuerst schaut sich der Algorithmus von Prim alle Kanten an die zu Knoten führen, also auch DC.
  2. DC führt allerdings nicht zu einem neuen Knoten und wird deshalb nicht gewählt, trotzdem aber zuerst angekuckt.

LG
Speedy

5

GH gehört aber nicht zu diesen, weil?

Weder g noch h bisher erreicht wurden!

6

Hab bei einem Onlinetool mal den Graph visualisiert:
http://graphonline.ru/en/?graph=atLJYAACiowTZbmg

Leider kann man da nicht den Algorithmus für den kleinsten Spannbaum Schritt für Schritt aufschlüsseln, aber vielleicht hilft es.

Man sieht auf jeden fall eindeutig, dass DC nicht im Graphen vorkommen darf.

Folgende Pfade werden der Reihe nach gewählt:

  1. Kruskal:

https://sequencediagram.org/index.html#initialData=C4S2BsFMAIGkCcCuBnA1gQ3AKCwB3fKAMYj4B2w0AgngcaehdAEK2EgnmUDCb9X0ACJ8ODJgFERnRpQBiUsZQDiCgQAkc+eNCxKAtAD41ALgCMWYAAt4kdABMs4w0rMXrth04OzXVm-axmQx9zPw9Aw25XSDIHZGB4DmAsKkjjACYsQUNxYwBmLBi7IA

(Pfeilrichtung egal)

  1. Prim (Ausgehend von D):
    https://sequencediagram.org/index.html#initialData=C4S2BsFMAIAUCcQFsBQKAOBDeoDGIsA7YaAQQ2zwM2OgCEKcR8iSBhRq16AEU+eq0AovxY0SAMVGCSAcWncAEmh4BaAHxCAXAGZG0FEI2ytARhSyNisymAALeJEwATA0fUSbEjXRt0NbDaQhM4obBqkWgBMQA

(Pfeilrichtung zeigt auf neuen Knoten des Teilbaumes)

1 „Gefällt mir“