¿Cómo construyen Kruskal y Prim un árbol de expansión mínima?

Question

Accepted Answer

Un **árbol de expansión mínima (MST)** conecta todos los vértices de un grafo ponderado y conexo con el **peso total de aristas mínimo** y sin ciclos. **Kruskal** y **Prim** son dos algoritmos codiciosos clásicos.

## Kruskal (ordenar aristas, union-find)

Ordena todas las aristas por peso; añade la arista más barata que no forma un ciclo.

```python
def kruskal(n, edges):                 # edges: (weight, u, v)
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # path compression
            x = parent[x]
        return x
    mst, total = [], 0
    for w, u, v in sorted(edges):      # cheapest first
        ru, rv = find(u), find(v)
        if ru != rv:                   # no cycle -> take it
            parent[ru] = rv
            mst.append((u, v, w)); total += w
    return mst, total
```

## Prim (hacer crecer un árbol con min-heap)

Comienza desde cualquier vértice; añade repetidamente la arista más barata que sale del árbol actual.

## Comparación

| | Kruskal | Prim |
|---|--------|------||
| Enfoque | ordenar aristas + union-find | expandir desde nodo + heap |
| Tiempo | O(E log E) | O(E log V) |
| Mejor para | grafos dispersos | grafos densos |

## Cuándo usar / Trampas

Usa MST para **diseño de redes** — tendido de cables, tuberías de agua, clustering. Ambos son codiciosos y demostrablemente óptimos aquí. Kruskal necesita union-find para evitar ciclos eficientemente.

## Por qué es importante

MST minimiza el costo de conectar todo — directamente aplicable a infraestructura y diseño de redes.

Es un caso limpio donde el algoritmo codicioso es demostrablemente óptimo, reforzando el razonamiento de elección codiciosa.

Kruskal también muestra union-find, una estructura con amplio alcance algorítmico.