minimaler Spannbaum

Berechnung des Minimalen Spannbaums

Dies geht einmal über KRUSKAL und einmal über PRIM

hier kurz die wichtigsten Unterschiede:
[später wird dieser Post noch um ein paar Details erweitert]

im wesentlichen:

Kruskal:

– man fängt am kleinsten kanten gewicht an.
– man geht zum nächst kleinen, und das immer so weiter. bis alle knoten einmal besucht worden.
– NUR knoten. nicht kanten. Die Kantengewichte dürfen keine Fläche bilden!

Prim:

– man sucht sich einfach irgendeinen punkt aus. dieser bleibt die ganze zeit über Ausgangspunkt.
– Man prüft immer wieder am aktuellen und allen alten (unbesuchten) kanten, wo ist die kleinste mögliche Kante zum laufen. Und dann wird dort neu verbunden. Das ganze solange bis alle Knoten besucht worden.
– Die Kantengewichte dürfen keine Fläche bilden!

Info Maximaler Spannbaum

Funktioniert im Endeffekt genauso. nur das man hierbei vom größt möglichen Punkt ausgeht, statt dem kleinsten.