Overview
El algoritmo de Kruskal construye el árbol de expansión mínima (MST) añadiendo repetidamente la arista más barata que no forma un ciclo.
Analogy
Como conectar ciudades con el menor costo de carreteras: siempre construyes la carretera más barata que conecta dos ciudades no conectadas aún.
Step-by-step
- Ordena todas las aristas por peso ascendente
- Inicializa Union-Find para cada vértice
- Para cada arista (u, v, w) en orden:
- Si u y v están en componentes distintos: añade la arista al MST y únelos
- Para cuando el MST tenga V-1 aristas
Visual
Aristas ordenadas: (1,2,1),(3,4,2),(1,3,3)...
Añade (1,2,1) → no ciclo ✓
Añade (3,4,2) → no ciclo ✓
Añade (1,3,3) → no ciclo ✓
Common mistakes
- No usar Union-Find → ciclos de detección O(V) en lugar de O(α(V))
- Confundir MST (árbol de expansión mínima) con camino más corto
Practice questions
- Implementa Kruskal con Union-Find de compresión de ruta
- Compara con el algoritmo de Prim para grafos densos vs escasos
Time
O(E log E) — dominado por la ordenación
Space
O(V) — para Union-Find