El algoritmo de Prim es un algoritmo de la teoría de los grafos para encontrar un árbol de expansión mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas.

En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol de expansión mínimo para uno de los componentes conexos que forman dicho grafo no conexo.

El algoritmo fue diseñado en 1930 por el matemático Vojtech Jarnik y luego de manera independiente por el científico computacional Robert C. Prim en 1957 y redescubierto por Dijkstra en 1959. Por esta razón, el algoritmo es también conocido como algoritmo DJP o algoritmo de Jarnik.

PRIM (Grafo G, nodo_fuente s)// inicializamos todos los nodos del grafo. La distancia la ponemos a infinito// y el padre de cada nodo a NULLfor each u ?  dodistancia[u = INFINITOpadre[u = NULLdistancia[s=0//encolamos todos los nodos del grafoEncolar(cola, )while cola != 0 do// OJO: Se extrae el nodo que tiene distancia mínima y se conserva la condición // de Cola de prioridadu = extraer_minimo(cola) for v ? adyacencia[u doif ((v ? cola) && (distancia[v > peso(u, v)) dopadre[v = udistancia[v = peso(u, v)

) {

=k;}}