Prims algoritm
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 PRIMindata: graf, en sammanhängande, vägd och oriktad graf rot, en nod i grafresultat: 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 ← ogiltigrot.kostnad ← 0kö ← en prioritetskö bestående av alla nod i graf, med minsta kostnad som prioriteringsvärdemedan 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.)[1]