Time and Space Complexity
Lección 7 de 9 del curso Algoritmo de Prim - Algoritmos de grafos de Coddy.
Complejidad Temporal:
- La versión de escaneo de aristas aquí es O(V * E): V-1 rondas, cada una escaneando todas las E aristas. Con un montículo binario y listas de adyacencia, Prim se ejecuta en O((V + E) log V).
Complejidad Espacial:
- O(V) para el arreglo
inTree(más las aristas de entrada).
Resumen:
- Prim hace crecer un árbol, añadiendo siempre la arista más barata que sale de él, hasta que se incluyen todos los vértices.
- Produce el mismo peso total mínimo que Kruskal, utilizando una estrategia diferente.
Pruébalo tú mismo
Esta lección no incluye un desafío de código.
Ponte a pruebaEsta lección incluye un breve cuestionario. Empieza la lección para responderlo y registrar tu progreso.
Todas las lecciones de Algoritmo de Prim - Algoritmos de grafos
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity