Kruskal contra Prim
En informática, los algoritmos de Prim y Kruskal son un algoritmo codicioso que encuentra un árbol de expansión mínimo para un gráfico no dirigido ponderado conectado. Un árbol de expansión es un subgráfico de un gráfico de modo que cada nodo del gráfico está conectado por una ruta, 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 más tarde de forma independiente por el científico 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 gráfico conectado con n nodos y el peso respectivo de cada borde, 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. Agregue el borde y el nodo en el otro extremo del árbol T y elimine el borde 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 conectado. La forma básica del algoritmo de Prim tiene una complejidad temporal de O (V 2).
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 simples pasos.
Dado el gráfico con n nodos y el peso respectivo de cada borde, 1. Seleccione el arco con el menor peso de todo el gráfico, añádalo al árbol y elimínelo del gráfico.
2. Del resto, 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 del paso 2.
En este método, el algoritmo comienza con el borde menos ponderado y continúa seleccionando cada borde en cada ciclo. Por tanto, en el algoritmo no es necesario conectar el gráfico. 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 van de un nodo a otro, mientras que el algoritmo de Kruskal selecciona los bordes de una 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 (V 2), y la complejidad temporal de Kruskal es O (logV).
