Diferencia entre Kruskal y Prim
Kruskal vs prim
En la 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 pesado conectado. Un árbol de expansión es una subgraph de un gráfico de tal manera que cada nodo del gráfico está conectado por una ruta, que es un árbol. Cada árbol de expansión tiene un peso, y los pesos/costos mínimos posibles 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 independientemente 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 retire el borde del gráfico. (Seleccione cualquiera si existen dos o más mínimos)
3. Repita el paso 2, hasta que se agregan los bordes N-1 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 de tiempo 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 pasos simples.
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 y agregue al árbol y elimine el gráfico.
2. Del restante selecciona el borde menos ponderado, de una manera que no forme un ciclo. Agregue el borde al árbol y elimine 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 un borde menos ponderado y continúa seleccionando cada borde en cada ciclo. Por lo tanto, en el algoritmo no es necesario conectar el gráfico. El algoritmo de Kruskal tiene una complejidad de tiempo de O (logv)
¿Cuál es la diferencia entre el algoritmo de Kruskal y Prim Primer??
• El algoritmo de Prim se inicializa con un nodo, mientras que el algoritmo de Kruskal se inicia con una ventaja.
• Los algoritmos de Prim se extienden de un nodo a otro, mientras que el algoritmo de Kruskal seleccione 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 los Kruskal también pueden funcionar en gráficos desconectados.
• El algoritmo de Prim tiene una complejidad de tiempo de O (V2), y la complejidad del tiempo de Kruskal es O (logv).
