Diferencia entre Kruskal y Prim

Kruskal vs Prim

En ciencias de la computación, 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 subgrafo de un gráfico de 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 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 posteriormente por el científico informático Robert C. Prim en 1957. Fue redescubierto por Edsger Dijkstra en 1959. El algoritmo se puede describir 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 de tiempo de O (V²).

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..

Dada la gráfica con n nodos y 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..

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 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 el gráfico no necesita estar conectado. El algoritmo de Kruskal tiene una complejidad de tiempo 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 desde un nodo a otro, mientras que el algoritmo de Kruskal selecciona los bordes de manera que la posición del borde no se base 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 de tiempo de O (V²), y la complejidad del tiempo de Kruskal es O (logV).