Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenDonnerstag, 16. Juli 2020 

Algorithmus von Prim


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Der Algorithmus von Prim ist ein Algorithmus zur Berechnung von minimal spannenden Bäumen in zusammenhängenden ungerichteten kantengewichteten Graphen .

Der Algorithmus arbeitet folgendermaßen:

  • Wähle einen beliebigen Knoten als Startgraph T .
  • Solange T noch nicht alle Knoten enthält
    • suche eine Kante minimalen Gewichts die einen der nicht in T ist mit T verbindet und
    • füge diese Kante und den damit verbundenen zu T hinzu.

Zur effizienten Implementierung wird zu jedem die kürzeste Kante die ihn mit T verbindet (falls vorhanden) und ihr Gewicht einer geeigneten Priority Queue (z.B. in einem Fibonacci-Heap ) gespeichert. Dies ermöglicht schnell eine Kante Gewichts zu finden die einen Knoten der in T ist mit T verbindet. Mit Fibonacci-Heaps ergibt sich eine Laufzeit von <math>O(m+n\log{n})</math>.

Fibonacci-Heaps oder andere geeignete Priority Queues nicht ganz einfach zu implementieren. Daher verwendet statt des Algorithmus von Prim oft auch Algorithmus von Kruskal der das Problem aber nicht ganz effizent löst insbesondere bei dichten Graphen d.h. viele Kanten besitzen. Der Kruskal-Algorithmus arbeitet schneller die Kanten nach Gewichtungen vorsortiert sind.



Bücher zum Thema Algorithmus von Prim

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Algorithmus_von_Prim.html">Algorithmus von Prim </a>