Kruskal contra Prim
En informática, los algoritmos de Prim y Kruskal son algoritmos codiciosos que encuentran un árbol de expansión mínimo para un gráfico no dirigido ponderado conectado. Un árbol de expansión es un subgrafo de un grafo tal que cada nodo del grafo está conectado por un camino, que es un árbol. Cada árbol de expansión tiene un peso, y el peso/costo mínimo posible de todos los árboles de expansión es el árbol de expansión mínimo (MST).
Más sobre el algoritmo de Prim
El algoritmo fue desarrollado por el matemático checo Vojtěch Jarník en 1930 y luego de forma independiente por el informático Robert C. Prim en 1957. Fue redescubierto por Edsger Dijkstra en 1959. El algoritmo se puede establecer en tres pasos clave;
Dado el grafo conexo con n nodos y el peso respectivo de cada arista, 1. Seleccione un nodo arbitrario del gráfico y agréguelo al árbol T (que será el primer nodo)
2. Considere los pesos de cada borde conectado a los nodos en el árbol y seleccione el mínimo. Agrega la arista y el nodo en el otro extremo del árbol T y elimina la arista del gráfico. (Seleccione cualquiera si existen dos o más mínimos)
3. Repita el paso 2, hasta que se agreguen n-1 bordes al árbol.
En este método, el árbol comienza con un solo nodo arbitrario y se expande desde ese nodo en adelante con cada ciclo. Por lo tanto, para que el algoritmo funcione correctamente, el gráfico debe ser un gráfico conexo. La forma básica del algoritmo de Prim tiene una complejidad temporal de O(V2).
Más sobre el algoritmo de Kruskal
El algoritmo desarrollado por Joseph Kruskal apareció en las actas de la American Mathematical Society en 1956. El algoritmo de Kruskal también se puede expresar en tres sencillos pasos.
Dado el gráfico con n nodos y peso respectivo de cada arista, 1. Seleccione el arco con el menor peso de todo el gráfico y agréguelo al árbol y elimínelo del gráfico.
2. De los restantes, seleccione el borde menos ponderado, de manera que no forme un ciclo. Agregue el borde al árbol y elimínelo del gráfico. (Seleccione cualquiera si existen dos o más mínimos)
3. Repita el proceso en el paso 2.
En este método, el algoritmo comienza con el borde menos ponderado y continúa seleccionando cada borde en cada ciclo. Por lo tanto, en el algoritmo no es necesario que el gráfico esté conectado. El algoritmo de Kruskal tiene una complejidad temporal de O(logV)
¿Cuál es la diferencia entre el algoritmo de Kruskal y el de Prim?
• El algoritmo de Prim se inicializa con un nodo, mientras que el algoritmo de Kruskal se inicia con un borde.
• Los algoritmos de Prim abarcan de un nodo a otro, mientras que el algoritmo de Kruskal selecciona los bordes de manera que la posición del borde no se basa en el último paso.
• En el algoritmo de prim, el gráfico debe ser un gráfico conectado, mientras que el de Kruskal también puede funcionar en gráficos desconectados.
• El algoritmo de Prim tiene una complejidad temporal de O(V2), y la complejidad temporal de Kruskal es O(logV).
