Motivation
Lección 2 de 9 del curso Algoritmo de Kruskal - Algoritmos de grafos de Coddy.
Kruskal mantiene el bosque creciente de aristas elegidas en una estructura union-find. Para añadir una arista de forma segura, comprueba si los dos extremos ya están en el mismo conjunto (eso formaría un ciclo).
¿Por qué aprender Kruskal?
- MSTs reales: diseño de redes, clustering y tendido de cables o carreteras al coste mínimo.
- Union-find: una estructura hermosa y reutilizable para rastrear la conectividad que aparece en toda la informática.
- Corrección voraz: otro ejemplo donde tomar siempre la opción segura más barata produce el óptimo global.
Todos los árboles de expansión mínima de un grafo utilizan el mismo multiconjunto de pesos de aristas, por lo que el peso total (y la arista más grande) 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.
