En teoria de grafs, lalgorisme de Prim és un algorisme que serveix per trobar un arbre generador minimal en un graf connex, no dirigit i amb arestes etiquetades. En altres paraules, l'algorisme troba el subconjunt d'arestes que formen l'arbre amb tots els vèrtexs en què el pes total de les arestes de l'arbre és el mínim possible. Si el graf no és connex, llavors l'algorisme trobarà l'arbre generador mínim per a un dels components connexos del seu subgraf connex. L'algorisme va ser dissenyat l'any 1930 pel matemàtic txec Vojtěch Jarník i posteriorment i de manera independent pel científic computacional Robert C. Prim el 1957 i redescobert per Edsger Dijkstra el 1959. Per aquesta raó, l'algorisme és també conegut com a algorisme DJP o algorisme de Jarnik.

L'algorisme incrementa contínuament la mida de l'arbre, partint d'un vèrtex inicial al qual se li van agregant successivament vèrtexs que tenen una distància mínima amb els anteriors. Això significa que en cada pas, les arestes a considerar són aquelles que incideixen en vèrtexs que ja pertanyen a l'arbre.

L'arbre generador mínim està completament construït quan no queden més vèrtexs per agregar.

Exemple d'execució Imatge Descripció No vist En el graf A l'arbre200pxAquest és el graf ponderat de partida. No és un arbre, ja que per a ser-ho cal que no hi hagi cicles, i en aquest cas sí que n'hi ha. Els números a prop de les arestes indiquen el pes. Cap aresta està marcada, i el vèrtex D ha estat elegit arbitràriament com a punt de partida. C, G A, B, E, F D200px El segon vèrtex és el més proper a D: A està a 5 de distància, B a 9, E a 15 i F a 6. D'aquests valors, 5 és el més petit, així que marquem l'aresta DA. C, G B, E, F A, D200pxEl següent vèrtex a elegir és el més proper a D o A. B és a 9 de distància de D i a 7 d'A, E es troba a 15 i F està a 6. 6 és el valor més petit, així que marquem el vèrtex F i l'aresta DF. C B, E, G A, D, F200px L'algorisme continua. El vèrtex B, que està a una distància de 7 respecte A, és el següent marcat. En aquest punt, l'aresta DB és marcada en vermell perque els dos extrems ja estan a l'arbre i, per tant, no podrà ser usat. null C, E, G A, D, F, B200px Aquí s'ha d'elegir entre C, E i G. C està a 8 de distància de B, E està a 7 de distància de B, i G està a 11 de distància de F. E està més a prop, llavors marquem el vèrtex E i l'aresta EB. S'han marcat en vermell dues altres arestes perquè ambdós vèrtexs que uneixen s'han agregat a l'arbre. null C, G A, D, F, B, E200px Només queden disponibles C i G. C està a 5 de distància de E, i G a 9 de distància d'E. S'elegeix C, i es marca amb l'arc EC. L'arc BC també es marca en vermell. null G A, D, F, B, E, C200pxG és l'únic vèrtex pendent, i està més a prop d'E que d'F, així que s'agrega EG a l'arbre. Tots els vèrtexs estan ja marcats, l'arbre generador mínim es mostra en verd. En aquest pas amb un pes de 39. null null A, D, F, B, E, C, G

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

Enllaços externs

Create and Solve Mazes by Kruskal's and Prim's algorithms Exemple animat de l'algorisme de Prim Codi de l'algorisme de Prim

Categoria:Algorismes de grafs