Alg. von Prim

[Hagbard]

hallo !

könnte mir jemand mal kurz den Alg. von Prim erklären ?
ich habs versucht aber mein Kopf ist zu voll gibts da vielleicht so ein einfaches rezept wie für Kruskal?

mfg Kurt http://hades.gothic.at/iforum/images/smilies/wallbash.gif

[tschurlo]

Also, ich versuchs mal:

Im Gegensatz zum Kruskal, suchst du dir hier einen Startknoten aus, von dem aus du deinen MST aufbaust.
Zweiter Unterschied: bei Kruskal sortierst du ja zuerst die Kanten und waehlst sie dann aufsteigend aus, wobei der Baum am Anfang gar nicht zusammenhaengend zu sein braucht. Beim Prim haengst du die Kanten immer an den bereits bestehenden Baum dran, d.h. du hast immer nur eine Zusammenhangskomponente.

Dann schaust mal, was fuer Kanten von deinem Startknoten weggehen, und haengst klarerweise die an, die die geringsten Kosten hat. Gut, weiter jetzt schaust dir alle Kanten an, die direkt mit deinen bisherigen zwei Knoten verbunden sind, und waehlst wieder die mit den gerinsten Kosten und haengst sie dran (also ich glaub d.h. du schaust dir von allen deinen Knoten die Menge N(v) an), usw.

Natuerlich, wie auch bei Kruskal, darfst du keine Kanten aufnehmen, die einen Kreis bilden wuerden. D.h. wenn die Kante mit den geringsten Kosten, dazu fuehren wuerde, dass ein Kreis entsteht, dann darfst du die natuerlich nicht nehmen, sondern musst dir eben die naechstkuerzere nehmen.

Hoffe, das war halbwegs korrekt und verstaendlich...

lg

[Hagbard]

danke tschurlo das hat geholfen is eh simpel wenn man's von einem profi erklärt bekommt
ich hau mich jetzt aufs ohr , wünsch noch einen netten abend und morgen alles gute

mfg Hagbard

[tschurlo]

is eh simpel wenn man's von einem profi erklärt bekommt
Danke fuer die Blumen! Das lass ich jetzt auf meine von AlgoDat langsam schon strapazierten Nerven einwirken.... :D
Ich hoffe, morgen frueh bin ich auch so schoen produktiv...

Ebenfalls viel Glueck morgen :thumb: