Utilidad del algoritmo de Prim

El algoritmo de Prim se aplica sobre un grafo para conseguir el árbol parcial mínimo, el cual es aquel que logra acceder a todos los nodos utilizando el camino de menor coste.

Explicación general del algoritmo

1. Partimos tomando un nodo de forma aleatoria en el grafo
2. Activamos las aristas que rodean al nodo seleccionado
3. Entre las aristas activadas seleccionamos la que menor coste tenga y activamos el nodo al que nos conduce
4. Activamos las aristas que nos rodean al nodo que llegamos
5. Repetimos el proceso hasta acceder a todos los nodos que contiene el grafo.

Durante el proceso nos podemos topar con los siguientes casos particulares:

• En caso de toparnos con dos o más aristas con el mismo coste mínimo, entonces elegimos de manera arbitraria por cual continuar
• Las conexiones se hacen siempre entre un nodo seleccionado y uno no seleccionado, cuando logramos acceder a un nuevo nodo y vemos que este tiene otras aristas activadas que lo direccionan entonces podemos “desactivarlas” ya que logramos acceder a él por una arista menso costosa.

Al finalizar este proceso vamos tener el árbol parcial mínimo.

Ejemplo de aplicación de Prim detallada

A continuación voy aplicar el algoritmo de Prim sobre un grafo y detallar que se hace en cada uno de los pasos, tener en cuenta que los pasos aplicados no siempre se hacen en el mismo orden, los siguientes aplican solo para este grafo y con estos valores.

1- Se toma un nodo de manera aleatoria y “activamos” todas las aristas que salen de él

En este caso de ejemplo, se comienza con el nodo C y se activan todas las aristas que salen de él

2- De las aristas activadas, elegimos la que menor peso tenga para conectarnos con el nodo que corresponde

De las 3 aristas que fueron activadas la de menor peso es {C-K} con el valor de 5

3- Activamos las aristas del nuevo nodo al que llegamos

Como llegamos al nodo K, activamos todas las aristas que rodean a este nodo