Árboles de expansión mínima: Kruskal

El mismo MST que Prim, estrategia opuesta. Ordena las aristas de más barata a más cara; agrega cada una que no forme un ciclo.

Fusiona un bosque, no hagas crecer un árbol

• Inicio: V árboles separados de un nodo
• Ordena todas las aristas por peso
• Para cada una: ¿árboles distintos? agrégala + fusiona. ¿Mismo árbol? sáltala (ciclo)
• Detente en V−1 aristas — el bosque ya es un solo árbol

Mira cómo se fusiona el bosque

Color del nodo = en qué árbol está. Naranja = aceptada (los colores se fusionan) · rojo punteado = rechazada (ciclo). Siete colores se juntan en uno → total 15 (igual que Prim).

El costo de Kruskal es el sort

250K aristas: Kruskal completo 133ms, pero la pasada de union-find sola <2ms. El sort es el 98%.

Union-find es (casi) gratis

• Un union por arista; O(α(V)) amortizado — α ≤ 4 para cualquier entrada real
• Compresión de caminos + unión por rango (del tier de árboles)
• Pre-ordenado / pesos enteros → Kruskal baja a ~lineal y le gana a Prim
• Kruskal se paraleliza; Prim gana en grafos densos con adyacencia

Para llevar

Un algoritmo = una estrategia (propiedad del corte) + una estructura de datos (union-find). La calidad de la estructura de datos ES el costo del algoritmo. Sigue: componentes fuertemente conexos — de vuelta a DFS, donde empezó el tier.