Time and Space Complexity
Lección 7 de 9 del curso Algoritmo de Kruskal - Algoritmos de grafos de Coddy.
Complejidad temporal:
- Ordenar las E aristas es O(E log E); cada operación union-find es casi O(1) con compresión de caminos, por lo que el Kruskal clásico es O(E log E). La versión de selección mínima que construimos aquí es O(E2), lo cual es adecuado para grafos pequeños.
Complejidad espacial:
- O(V) para el arreglo parent (más las aristas de entrada).
Resumen:
- Kruskal expande un MST añadiendo la arista más barata que no forme ciclos en cada paso, utilizando union-find para detectar ciclos.
- Todos los MST comparten el mismo peso total, por lo que el resultado es único.
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 Kruskal - Algoritmos de grafos
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity