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, kostnadad och oriktad graf.

Algoritmen finner i varje iteration den länk med lägst kostnad 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 noder som inte lagts till i trädet.

Pseudokod

algoritm  PRIM
indata:   graf, en sammanhängande, kostnadad och oriktad graf
          rot,  ett nod i graf
resultat: Varje nod i graf märks med sin förälder i ett minimalt
          uppspännande träd av graf med det angivna nodet som rot
          samt med kostnaden av länken till föräldern.

för varje nod i graf
    nod.kostnad     ← ∞
    nod.förälder ← ogiltig

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

medan kö inte är tom
    u ← extrahera_minsta( kö )
    för varje nod v som u ansluter till via en länk (u, v)
        om v finns i kö och kostnaden av länken (u, v) < v.kostnad
            v.förälder ← u
            v.kostnad ← kostnaden av länken (u, v)

Exempel

Bild	Beskrivning
	Målet är att finna ett träd som omfattar noden A–G där trädets länker har så låg sammanlagd kostnad som möjligt. Algoritmen börjar vid nod D.
	Från nod D finns 4 länker (till noden A, B, E och F). Kanten DA till nod A har lägst kostnad och läggs därför till i trädet.
	Nästa nod att anslutas är till antingen nod D eller A. Möjliga länker är AB, DB, DE, DF. Vikten för länken 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 nod att ansluta. Trädet är fullständigt.

Tidskomplexitet

Prims algoritm har komplexitet O(E + V lg V), där E är antalet länker och V är antalet nod 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