Prims algoritm

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

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 kant med lägst vikt som kan förbinda trädet med ett hörn som ännu inte finns med i trädet, varpå trädet utökas med denna kant (och det hörn som den ansluter till). Iterationen fortsätter så länge det finns hörn som inte lagts till i trädet.

Pseudokod[redigera | redigera wikitext]

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

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

Exempel[redigera | redigera wikitext]

Bild Beskrivning
Prim Algorithm 0.svg
Målet är att finna ett träd som omfattar hörnen A–G där trädets kanter har så låg sammanlagd kostnad som möjligt. Algoritmen börjar vid hörn D.
Prim Algorithm 1.svg
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 pris och läggs därför till i trädet.
Prim Algorithm 2.svg
Nästa hörn att anslutas är det som har billigast kant till antingen hörn D eller A. Möjliga kanter är AB, DB, DE, DF. Kostnaden för kanten DF är billigast, 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 hörn 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 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.)[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