Ninguna. Ambos algoritmos tienen sus propias ventajas. Aquí están sus complejidades de tiempo.
Kruskal:
- O (E lgV): teniendo en cuenta que está utilizando la heurística de unión por rango y compresión de ruta para la implementación forestal de conjunto disjunto.
Remilgado:
- Quiero comenzar un proyecto de programación. ¿Cuáles son algunas sugerencias al respecto?
- Cómo resolver este problema usando la descomposición de raíz cuadrada
- Cómo verificar si un árbol no binario está equilibrado en altura
- ¿Qué estructura de datos debo usar para completar esta tarea?
- ¿Por qué la notación O grande no se parece más a O (c) y O (cn) en lugar de a O (1) y O (n), esto último no tiene sentido?
- O (E + V lgV) tiempo amortizado – utilizando montones de Fibonacci.
- O (V ^ 2) – usando una matriz de adyacencia.
Ahora, comparemos los tiempos de ejecución. Primero exponga ambos en términos de vértices. Para un gráfico denso, digamos, E ~ V ^ 2:
Kruskal: O ((V ^ 2) lgV)
Prim: O (V ^ 2) (usando matriz de adyacencia)
Entonces, si tiene un gráfico denso con más relación de borde a vértice, elija Prim’s
de lo contrario, elija Kruskal, que funciona mejor para gráficos dispersos.
También,
- El algoritmo de Prim requiere que el gráfico esté conectado
- Kruskal, por otro lado, trabaja en una estructura de datos de conjunto disjunto, por lo que también funciona con un gráfico desconectado.
