Algoritme de Prim

Archiu:Minimum spanning tree.svg

El algoritme de Prim permet trobar un arbre recubridor mínim d'un grafo.

El algoritme de Prim és un algoritme pertanyent a la teoria dels grafos per a trobar un arbre recubridor mínim en un grafo conexo, no dirigit i que les seues arestes estan etiquetades.

En atres paraules, l'algoritme troba un subconjunt d'arestes que formen un arbre en tots els vèrtiços, a on el pes total de totes les arestes en l'arbre és el mínim possible. Si el grafo no és conexo, llavors l'algoritme trobarà l'arbre recubridor mínim para un dels components conexos que formen dit grafo no conexo.

l'algoritme va ser dissenyat en 1930 pel matemàtic Vojtech Jarnik i després de manera independent pel científic computacional Robert C. Prim en 1957 i redescubierto per Dijkstra en 1959. Per esta raó, l'algoritme és també conegut com a algoritme DJP o algoritme de Jarnik.

Descripció

L'algoritme incrementa contínuament el tamany d'un arbre, començant per un vèrtiç inicial al que se li van agregant successivament vèrtiços la distància dels quals als anteriors és mínima. Açò significa que en cada pas, les arestes a considerar són aquelles que incidixen en vèrtiços que ya pertanyen a l'arbre. Sempre se selecciona una aresta després el número més chicotet per a passar d'una aresta a una atra.

L'arbre recubridor mínim està completament construït quan no queden més vèrtiços per agregar.

L'algoritme podria ser informalmente descrit seguint els següents passos:

1. Inicializar un arbre en un únic vèrtiç, elegit arbitrariamente, del grafo.
2. Aumentar l'arbre per un costat. Cridem costat a l'unió entre dos vèrtiços: de les possibles unions que poden conectar l'arbre als vèrtiços que no estan encara en l'arbre, trobar el costat de menor distància i unir-ho a l'arbre.
3. Repetir el pas 2 (fins que tots els vèrtiços pertanyguen a l'arbre)

Per a fer-ho més en detalle, deu ser implementat el pseudocódigo següent.

1. Associar en cada vèrtiç v del grafo un número C[v] (el mínim cost de conexió a v) i a un costat I[v] (el costat que proveïx eixa conexió de mínim cost). Per a inicializar eixos valors, s'establixen tots els valors de C[v] iguals a +∞ (o a qualsevol número més gran que el màxim tamany d'un costat) i establim cada I[v] igual a un valor "flag"(bandera) que indica que no hi ha cap costat que conecte v a vèrtiços anteriors.
2. Inicializar un bosc buit F i establir Q vèrtiços que encara no han segut inclosos en F (inicialment, tots els vèrtiços).
3. Repetir els següents passos fins que Q estiga buit:
   1. Trobar i eliminar un vèrtiç v de Q tenint el mínim valor de C[v]
   2. Afegir v a F i, si I[v] no té el valor especial de "flag", afegir també I[v] a F
   3. Fer un bucle sobre els costats vw conectant v a atres vèrtiços w. Per a cada costat, si w encara pertany a Q i vw té tamany més chicotet que C[w], realisar els següents passos:
      1. Establir C[w] al cost del costat vw
      2. Establir I[w] apuntant al costat vw
4. Tornar F

Com s'ha descrit dalt, el vèrtiç inicial per a l'algoritme serà elegit arbitrariamente, perque la primera iteración del bucle principal de l'algoritme tindrà un número de vèrtiços en Q que tindran tots el mateix tamany, i l'algoritme escomençarà automàticament un nou arbre en F quan complete un arbre d'expansió a partir de cada vèrtiç conectat del grafo. L'algoritme deu ser modificat per a escomençar en qualsevol vèrtiç particular s per a configurar C[s] per a que siga un número més chicotet que els atres valors de C (per norma, zero), i deu ser modificat per a solament trobar un únic arbre d'expansió i no un bosc sancer d'expansió, parant quan trobe un atre vèrtiç en "flag" que no té cap costat associat.

Hi ha diferents variacions de l'algoritme que diferixen unes d'atres en cóm implementar Q: Com una única Llista enllaçada o un vector de vèrtiços, o com una estructura de senyes organisada en una coa de prioritats, més complexa. Esta elecció lidera les diferències en complexitat de temps de l'algoritme. En general, una coa de prioritats serà més ràpida trobant el vèrtiç v en el mínim cost, pero això comportarà actualisacions més costoses quan el valor de C[w] canvie.

Pseudocódigo de l'algoritme

• Estructura de senyes auxiliar: Coa de prioritat (es pot implementar en un heap)

   Prim (Grafo G)
       /* Inicializamos tots els nodos del grafo. 
       La distància la posem a infinit i el pare de cada nodo a NULL
        Encolamos, en una coa de prioritat 
                  a on la prioritat és la distància, 
               totes les parelles <nodo, distància> del grafo*/
       per cada o en V[G] fer
           distància[o] = INFINITO
           pare[o] = NULL
           Afegir(coa,<o, distància[o]>)
       distància[o]=0
       Actualisar(coa,<o, distància[o]>)
       mentres !esta_vacia(coa) fer
           // OJO: S'entén per major prioritat aquell nodo la distància del qual[o] és menor.
           o = extraure_minimo(coa) //torna el mínim i ho elimina de la coa.
           per cada v adjacent a 'o' fer
               si ((v ∈ coa) && (distància[v] > pes(o, v)) llavors
                   pare[v] = o
                   distància[v] = pes(o, v)
                   Actualisar(coa,<v, distància[v]>)

Vore també

• Algoritme de Dijkstra

Referències

• R. C. Prim: Shortest connection networks and some generalisations. In: Bell System Technical Journal, 36 (1957), pp. 1389–1401
• D. Cherition and R. E. Tarjan: Finding minimum spanning trees. In: SIAM Journal of Computing, 5 (Dec. 1976), pp. 724–741
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 23.2: The algorithms of Kruskal and Prim, pp.567–574.