El algoritmo PRIM busca encontrar el árbol de expansión máximo o mínimo en un grafo, es decir encontrar un conjunto de aristas tal que todos los puntos estén unidos y la suma de pesos sea mínima. Se realiza esta tarea considerando todos los posibles caminos en orden del más pequeño al más grande mediante el uso de una cola de prioridad.
El algoritmo se puede resumir como sigue:
- Seleccionar un nodo inicial A
- Mandar los nodos vecinos no visitados a una cola de prioridad
- Sacar el primer nodo de la cola
- Repetir los pasos 2 y 3 hasta que la cola esté vacía
- Prim - C++