Kruskal contra Prim
En informàtica, els algorismes de Prim i Kruskal són un algorisme cobdiciós que troba un arbre d'abast mínim per a un gràfic no dirigit ponderat connectat. Un arbre spanning és un subgraf d'un graf de manera que cada node del gràfic està connectat per un camí, que és un arbre. Cada arbre allargat té un pes i els pesos/cost mínims possibles de tots els arbre spanning és l'arbre spanning mínim (MST).
Més sobre l'algoritme de Prim
L'algorisme va ser desenvolupat pel matemàtic txec Vojtěch Jarník el 1930 i més tard de manera independent pel científic informàtic Robert C. Prim el 1957. Va ser redescobert per Edsger Dijkstra el 1959. L'algoritme es pot afirmar en tres passos clau;
Donat el gràfic connectat amb n nodes i el pes respectiu de cada aresta, 1. Seleccioneu un node arbitrari del gràfic i afegiu-lo a l'arbre T (que serà el primer node)
2. Considereu els pesos de cada aresta connectada als nodes de l'arbre i seleccioneu el mínim. Afegiu l'aresta i el node a l' altre extrem de l'arbre T i traieu l'aresta del gràfic. (Seleccioneu qualsevol si n'hi ha dos o més mínims)
3. Repetiu el pas 2 fins que s'afegeixin n-1 vores a l'arbre.
En aquest mètode, l'arbre comença amb un únic node arbitrari i s'expandeix a partir d'aquest node amb cada cicle. Per tant, perquè l'algorisme funcioni correctament, el gràfic ha de ser un gràfic connectat. La forma bàsica de l'algorisme de Prim té una complexitat temporal de O(V2).
Més sobre l'algoritme de Kruskal
L'algorisme desenvolupat per Joseph Kruskal va aparèixer a les actes de la Societat Americana de Matemàtiques el 1956. L'algorisme de Kruskal també es pot expressar en tres passos senzills.
Donat el gràfic amb n nodes i el pes respectiu de cada aresta, 1. Seleccioneu l'arc amb el menor pes de tot el gràfic i afegiu-lo a l'arbre i suprimiu-lo del gràfic.
2. De la resta, seleccioneu la vora menys ponderada, de manera que no formi un cicle. Afegiu la vora a l'arbre i suprimiu-lo del gràfic. (Seleccioneu qualsevol si n'hi ha dos o més mínims)
3. Repetiu el procés del pas 2.
En aquest mètode, l'algorisme comença amb la vora menys ponderada i continua seleccionant cada vora a cada cicle. Per tant, en l'algorisme el gràfic no necessita estar connectat. L'algorisme de Kruskal té una complexitat temporal de O(logV)
Quina diferència hi ha entre l'algoritme de Kruskal i l'algoritme de Prim?
• L'algorisme de Prim s'inicia amb un node, mentre que l'algoritme de Kruskal s'inicia amb una vora.
• Els algorismes de Prim abasten d'un node a un altre, mentre que l'algoritme de Kruskal selecciona les arestes de manera que la posició de la vora no es basa en l'últim pas.
• A l'algorisme de prim, el gràfic ha de ser un gràfic connectat mentre que el de Kruskal també pot funcionar en gràfics desconnectats.
• L'algorisme de Prim té una complexitat temporal de O(V2) i la complexitat temporal de Kruskal és O(logV).
