Dado un grafo conexo y no dirigido , un árbol de expansión de ese grafo es un subgrafo que es un árbol y conecta todos los vértices entre sí. Un solo gráfico puede tener muchos árboles de expansión diferentes. Un árbol de expansión mínimo (MST) o un árbol de expansión de peso mínimo para un gráfico ponderado, conectado y no dirigido es un árbol de expansión con un peso menor o igual que el peso de cualquier otro árbol de expansión. El peso de un árbol de expansión es la suma de los pesos asignados a cada borde del árbol de expansión.
A continuación se muestran los pasos para encontrar MST usando el algoritmo de Kruskal
- Ordene todos los bordes en orden no decreciente de su peso.
- Elija el borde más pequeño. Compruebe si forma un ciclo con el árbol de expansión formado hasta ahora. Si el ciclo no está formado, incluya este borde. De lo contrario, deséchalo.
- Repita el paso 2 hasta que haya aristas (V-1) en el árbol de expansión.
Al igual que el algoritmo de Kruskal, el algoritmo de Prim también es un algoritmo Greedy. Comienza con un árbol de expansión vacío. La idea es mantener dos conjuntos de vértices. El primer conjunto contiene los vértices ya incluidos en el MST, el otro conjunto contiene los vértices aún no incluidos. En cada paso, considera todos los bordes que conectan los dos conjuntos y selecciona el borde de peso mínimo de estos bordes. Después de seleccionar el borde, mueve el otro extremo del borde al conjunto que contiene MST.
A continuación se muestran los pasos para encontrar MST utilizando el algoritmo de Prim.
- Cree un conjunto mstSet que realice un seguimiento de los vértices ya incluidos en MST.
- Asigne un valor clave a todos los vértices en el gráfico de entrada. Inicialice todos los valores clave como INFINITOS. Asigne el valor clave como 0 para el primer vértice para que se elija primero.
- Si bien mstSet no incluye todos los vértices
- Elija un vértice u que no esté en mstSet y tenga un valor de clave mínimo.
- Incluya u en mstSet.
- Actualice el valor clave de todos los vértices adyacentes de u. Para actualizar los valores clave, itere a través de todos los vértices adyacentes. Para cada vértice adyacente v, si el peso del borde uv es menor que el valor clave anterior de v, actualice el valor clave como el peso de uv
Tanto el algoritmo de Prim como el de Kruskal encuentran el árbol de expansión mínimo y siguen el enfoque codicioso de resolución de problemas, pero hay pocas diferencias importantes entre ellos .
| Algoritmo de Prim | Algoritmo de Kruskal |
|---|---|
| Comienza a construir el árbol de expansión mínimo desde cualquier vértice del gráfico. | Comienza a construir el árbol de expansión mínimo a partir del vértice que tiene el peso mínimo en el gráfico. |
| Atraviesa un Node más de una vez para obtener la distancia mínima. | Atraviesa un Node solo una vez. |
| El algoritmo de Prim tiene una complejidad de tiempo de O(V 2 ), siendo V el número de vértices y se puede mejorar hasta O(E log V) usando montones de Fibonacci. | La complejidad temporal del algoritmo de Kruskal es O(E log V), siendo V el número de vértices. |
| El algoritmo de Prim proporciona un componente conectado y funciona solo en un gráfico conectado. | El algoritmo de Kruskal puede generar bosques (componentes desconectados) en cualquier instante, así como también puede funcionar en componentes desconectados. |
| El algoritmo de Prim se ejecuta más rápido en gráficos densos. | El algoritmo de Kruskal se ejecuta más rápido en gráficos dispersos. |
| Genera el árbol de expansión mínimo a partir del vértice raíz. | Genera el árbol de expansión mínimo a partir del borde menos ponderado. |
| Las aplicaciones del algoritmo de prim son el problema del viajante, la red de carreteras y las vías férreas que conectan todas las ciudades, etc. | Las aplicaciones del algoritmo Kruskal son la conexión LAN, la red de TV, etc. |
| El algoritmo de Prim prefiere estructuras de datos de lista. | El algoritmo de Kruskal prefiere estructuras de datos en montón. |