Me preguntaba cuándo se debería usar el algoritmo de Prim y cuándo Kruskal para encontrar el árbol de expansión mínimo. Ambos tienen lógicas fáciles, los mismos peores casos, y la única diferencia es la implementación que podría involucrar estructuras de datos un poco diferentes. Entonces, ¿cuál es el factor decisivo?
Use el algoritmo de Prim cuando tenga un gráfico con muchos bordes.
Para un gráfico con vértices V y bordes E , el algoritmo de Kruskal se ejecuta en tiempo O (E log V) y el algoritmo de Prim puede ejecutarse en tiempo amortizado O (E + V log V) , si utiliza un montón de Fibonacci .
El algoritmo de Prim es significativamente más rápido en el límite cuando tienes un gráfico realmente denso con muchos más bordes que vértices. Kruskal funciona mejor en situaciones típicas (gráficos dispersos) porque utiliza estructuras de datos más simples.
Encontré un hilo muy agradable en la red que explica la diferencia de una manera muy directa: http://www.thestudentroom.co.uk/showthread.php?t=232168 .
El algoritmo de Kruskal desarrollará una solución desde el borde más barato al agregar el siguiente borde más barato, siempre que no cree un ciclo.
El algoritmo de Prim desarrollará una solución a partir de un vértice aleatorio agregando el siguiente vértice más barato, el vértice que actualmente no está en la solución pero que está conectado a él por el borde más barato.
Aquí se adjunta una hoja interesante sobre ese tema.
Si implementa Kruskal y Prim, en su forma óptima: con un hallazgo de unión y un montón de finbonacci respectivamente, notará cómo Kruskal es fácil de implementar en comparación con Prim.
Prim es más difícil con un montón de Fibonacci principalmente porque debe mantener una tabla de contabilidad para registrar el enlace bidireccional entre los nodos del gráfico y los nodos del montón. Con Union Find, es todo lo contrario, la estructura es simple e incluso puede producir directamente el material sin casi ningún costo adicional.
fuente
V-1bordes.Sé que no solicitó esto, pero si tiene más unidades de procesamiento, siempre debe considerar el algoritmo de Borůvka , ya que podría ser fácilmente paralelo; por lo tanto, tiene una ventaja de rendimiento sobre el algoritmo Kruskal y Jarník-Prim.
fuente
Kruskal puede tener un mejor rendimiento si los bordes se pueden ordenar en tiempo lineal o si ya están ordenados.
Prim es mejor si el número de aristas a vértices es alto.
fuente
El peor caso de la complejidad del tiempo de Kruskal es O (E log E) , esto porque necesitamos ordenar los bordes. El peor caso de la complejidad del tiempo primario es O (E log V) con cola de prioridad o incluso mejor, O (E + V log V) con Fibonacci Heap . Deberíamos usar Kruskal cuando el gráfico es escaso, con un número pequeño de aristas, como E = O (V), cuando las aristas ya están ordenadas o si podemos ordenarlas en tiempo lineal. Deberíamos usar Prim cuando el gráfico es denso, es decir, el número de aristas es alto, como E = O (V²).
fuente
Si detenemos el algoritmo en el algoritmo de middle prim siempre genera un árbol conectado, pero kruskal por otro lado puede dar un árbol o bosque desconectado
fuente
Una aplicación importante del algoritmo de Kruskal es la agrupación en un solo enlace .
Considere n vértices y tendrá un gráfico completo. Para obtener ak agrupaciones de esos n puntos. Ejecute el algoritmo de Kruskal sobre los primeros n- (k-1) bordes del conjunto ordenado de bordes. Obtenga el k-cluster de la gráfica con el máximo espaciado.
fuente
El mejor momento para Kruskal es O (E logV). Para Prim usando montones de fib podemos obtener O (E + V lgV). Por lo tanto, en un gráfico denso, Prim es mucho mejor.
fuente
Prim es mejor para gráficos más densos, y en esto tampoco tenemos que prestar mucha atención a los ciclos agregando un borde, ya que estamos tratando principalmente con nodos. Prim es más rápido que Kruskal en el caso de gráficos complejos.
fuente
En el algoritmo de kruskal tenemos un número de aristas y un número de vértices en un gráfico dado, pero en cada borde tenemos algún valor o peso en nombre del cual podemos preparar un nuevo gráfico que no debe ser cíclico ni estar cerca de ningún lado. Por ejemplo
gráfico como este _____________ | El | El | El | El | El | | __________ | El | Dé nombre a cualquier vértice a, b, c, d, e, f.
fuente