Algorisme de Prim
En teoria de grafs, l'algorisme 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.
Descripció conceptual
[modifica]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ó
[modifica]| Imatge | Descripció | No vist | En el graf | A l'arbre |
|---|---|---|---|---|
|
Aquest é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 | D |
|
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, D |
|
El 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, F |
|
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, B |
|
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, E |
|
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, C |
|
G é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
[modifica]- R. C. Prim: Shortest connection networks and some generalisations. In: Bell System Technical Journal, 36 (1957), pp. 1389–1401
- D. Cherition i 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, i 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.
Enllaços externs
[modifica]