Prims algoritm

Från Wikipedia
Hoppa till navigering Hoppa till sök

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[redigera | redigera wikitext]

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
 ← en prioritetskö bestående av alla nod i graf,
     med minsta kostnad som prioriteringsvärde

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

Exempel[redigera | redigera wikitext]

Bild Beskrivning
Prim Algorithm 0.svg
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.
Prim Algorithm 1.svg
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.
Prim Algorithm 2.svg
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.
Prim Algorithm 3.svg
Hörn B ansluts via A. Kanten BD kommer inte att ingå i trädet, eftersom B och D redan är förbundna indirekt.
Prim Algorithm 4.svg
E ansluts via B.
Prim Algorithm 5.svg
C ansluts via E.
Prim Algorithm 6.svg
G ansluts via E. Det finns inga fler nod att ansluta. Trädet är fullständigt.

Tidskomplexitet[redigera | redigera wikitext]

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.)[1]

Se även[redigera | redigera wikitext]

Referenser[redigera | redigera wikitext]

  1. ^ Cormen, T.H., Leiserson, E.L., Rivest, R.L., Stein, C (2001). Introductions to Algorithms (2 utgåvan). USA: MIT Press. sid. 570–573. ISBN 0-262-03293-7