Prims algoritm

Prims algoritm

Algoritm, grafalgoritm, girig algoritm

Anv­änd­ning	minimalt uppspännande träd, beslutsträd
Uppkallad efter	Robert C. Prim, Vojtěch Jarník
Upp­täc­ka­re eller upp­fin­na­re	Vojtěch Jarník, Robert C. Prim, Edsger Dijkstra
Tids­komp­lex­i­tet i värsta fall	$O(|E|+|V|\log |V|)$, $O((|V|+|E|)\log |V|)=O(|E|\log |V|)$, $O(|V|^{2})$

Prims algoritm är en girig algoritm för att skapa ett minimalt uppspännande träd från en godtycklig sammanhängande, viktad och oriktad graf.

Algoritmen finner i varje iteration den länk med lägst vikt som kan förbinda trädet med en nod som ännu inte finns med i trädet, varpå trädet utökas med denna länk (och den nod som den ansluter till). Iterationen fortsätter så länge det finns hörn som inte lagts till i trädet.

Pseudokod

algoritm  PRIM
indata:   graf, en sammanhängande, viktad och oriktad graf
          rot,  ett hörn i graf
resultat: Varje hörn i graf märks med sin förälder i ett minimalt
          uppspännande träd av graf med det angivna hörnet som rot
          samt med vikten av kanten till föräldern.

för varje hörn i graf
    hörn.vikt     ← ∞
    hörn.förälder ← ogiltig

rot.vikt ← 0
kö ← en prioritetskö bestående av alla hörn i graf,
     med minsta vikt som prioriteringsvärde

medan kö inte är tom
    u ← extrahera_minsta( kö )
    för varje hörn v som u ansluter till via en kant (u, v)
        om v finns i kö och vikten av kanten (u, v) < v.vikt
            v.förälder ← u
            v.vikt ← vikten av kanten (u, v)

Exempel

Bild	Beskrivning
	Målet är att finna ett träd som omfattar hörnen A–G där trädets kanter har så låg sammanlagd vikt som möjligt. Algoritmen börjar vid hörn D.
	Från hörn D finns 4 kanter (till hörnen A, B, E och F). Kanten DA till hörn A har lägst vikt och läggs därför till i trädet.
	Nästa hörn att anslutas är till antingen hörn D eller A. Möjliga kanter är AB, DB, DE, DF. Vikten för kanten DF är minst, så den läggs till.
	Hörn B ansluts via A. Kanten BD kommer inte att ingå i trädet, eftersom B och D redan är förbundna indirekt.
	E ansluts via B.
	C ansluts via E.
	G ansluts via E. Det finns inga fler hörn att ansluta. Trädet är fullständigt.

Tidskomplexitet

Prims algoritm har komplexitet O(E + V lg V), där E är antalet kanter och V är antalet hörn i den graf som trädet skapas från, under förutsättning att prioritetskön implementeras som en Fibonacciheap. (Om en binär heap används försämras komplexiteten till O(E lg V), vilket är asymptotiskt likvärdigt med Kruskals algoritm.)

Se även

• Kruskals algoritm