kruskal - prim algorithm python
Kruskal vs Prim (10)
El mejor momento para Kruskal es O (E logV). Para que Prim use montones fib, podemos obtener O (E + V lgV). Por lo tanto, en un gráfico denso, Prim es mucho mejor.
Me preguntaba cuándo se debe usar el algoritmo de Prim y cuándo Kruskal''s para encontrar el árbol de expansión mínimo. Ambos tienen lógicas sencillas, los mismos peores casos, y la única diferencia es la implementación, que podría implicar estructuras de datos un poco diferentes. Entonces, ¿cuál es el factor decisivo?
En el algoritmo 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 o no estar cerca de ningún lado. Ejemplo
gráfico como este _____________ | | | | | | | __________ | | Dar nombre a cualquier vértice a, b, c, d, e, f.
Encontré un hilo muy bonito 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 la próxima ventaja más barata, siempre que no cree un ciclo.
El algoritmo de Prim generará una solución desde un vértice aleatorio agregando el siguiente vértice más barato, el vértice que no está actualmente en la solución pero conectado a él por el borde más barato.
Aquí adjunto hay una hoja interesante sobre ese tema.
Si implementa Kruskal y Prim, en su forma óptima: con un descubrimiento 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 de gráfico y los nodos de pila. Con Union Find, es todo lo contrario, la estructura es simple e incluso puede producir directamente el mst casi sin costo adicional.
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 bordes a vértices es alto.
Prim es mejor para gráficos más densos, y en esto tampoco tenemos que prestar mucha atención a los ciclos añadiendo una ventaja, ya que estamos tratando principalmente con nodos. Prim es más rápido que Kruskal en el caso de gráficos complejos.
Sé que no solicitó esto, pero si tiene más unidades de procesamiento, siempre debe considerar el algoritmo de Borůvka , porque podría ser fácilmente paralelizado, por lo tanto, tiene una ventaja de rendimiento sobre el algoritmo de Kruskal y Jarník-Prim.
Si detenemos el algoritmo en el algoritmo de middle prim siempre genera árbol conectado, pero kruskal por otro lado puede dar árbol o bosque desconectado
Una aplicación importante del algoritmo de Kruskal es la agrupación de enlaces individuales .
Considere n vértices y tenga un gráfico completo. Para obtener clusters ak de esos n puntos. Ejecute el algoritmo de Kruskal sobre los primeros n- (k-1) bordes del conjunto de bordes ordenados. Obtiene k-cluster del gráfico con un máximo espaciado.
Usa el algoritmo de Prim cuando tienes un gráfico con muchos bordes.
Para un gráfico con V vértices 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 Heap 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 usa estructuras de datos más simples.
El peor caso de complejidad de tiempo de Kruskal es O (E log E) , esto porque necesitamos ordenar los bordes. El peor caso de complejidad de tiempo primordial 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, es decir, un pequeño número de aristas, como E = O (V), cuando los bordes ya están ordenados o si podemos ordenarlos 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²).