Árbol de expansión mínima de Kruskal
Añada las aristas más baratas sin crear ciclos
Árbol de expansión mínima de Kruskal es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 3 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
Qué es un MST
Un árbol de expansión mínima conecta todos los vértices con el menor peso total posible de sus aristas y sin ciclos. Piense en cablear una ciudad al menor coste. 🌲
Idea central de Kruskal
El algoritmo de Kruskal aplica un enfoque totalmente voraz: añade continuamente la arista más barata que no cree un ciclo, hasta conectar todo el grafo.
Paso uno: ordenar las aristas
Primero, ordene todas las aristas por peso, de menor a mayor. Preferir vorazmente las aristas baratas es lo que hace mínimo el total final.
edges.sort() # (weight, u, v)Por qué DSU encaja a la perfección
Añadir una arista forma un ciclo únicamente si sus dos extremos ya están conectados. DSU responde a esta prueba de conectividad en tiempo casi constante. 🤝
Recorrer las aristas ordenadas
Recorra las aristas desde la más barata hasta la más costosa. Para cada una, compruebe si sus dos extremos ya comparten una raíz en DSU.
for w, u, v in edges:
ru, rv = find(u), find(v)Aceptar o rechazar
Si las raíces son distintas, la arista conecta dos partes separadas, así que acéptela y únalas. Si las raíces coinciden, omítala para evitar un ciclo.
if ru != rv:
union(u, v)
total += wSaber cuándo detenerse
Un árbol de expansión de n vértices tiene exactamente n menos 1 aristas. Cuando haya aceptado esa cantidad, puede detenerse antes.
Detectar la desconexión
Si termina de procesar todas las aristas con menos de n menos 1 aceptadas, el grafo está desconectado y no existe ningún árbol de expansión.
El coste temporal
La ordenación domina el coste, por lo que Kruskal se ejecuta en O(E log E). Las operaciones de DSU son tan rápidas que apenas aumentan ese total.
Por qué el enfoque voraz es correcto
La propiedad del corte garantiza que la arista más ligera que cruza cualquier división se puede añadir sin riesgo; por eso elegir primero las más baratas nunca falla.
Cuándo recurrir a Kruskal
Kruskal destaca en grafos dispersos proporcionados como una lista de aristas, el formato que suelen entregar directamente la mayoría de los problemas de concursos. ⚡
Comprobación rápida
Determine qué hace que Kruskal rechace una arista.
Repaso
Construyó el MST de Kruskal: ordenar las aristas, añadir mediante DSU la más barata que una dos componentes y detenerse al llegar a n menos 1 aristas. 🎉
Preguntas frecuentes
¿La lección «Árbol de expansión mínima de Kruskal» es gratis?
Sí — el texto completo de «Árbol de expansión mínima de Kruskal» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Árbol de expansión mínima de Kruskal»?
Añada las aristas más baratas sin crear ciclos Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 3 de 4.
¿Cuánto tiempo toma la lección «Árbol de expansión mínima de Kruskal»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- DSU con compresión de caminos
- Unión por rango y componentes
- Árbol de expansión mínima de Kruskal
- MST de Prim con un heap