Árbol de expansión mínima
En resumen: Un árbol de expansión mínima conecta todos los vértices de un grafo con el menor coste total; el algoritmo de Kruskal toma las aristas por coste y salta cada arista que cerraría un ciclo.
Problema
La red más barata
La empresa de reparto tiene seis oficinas en la ciudad y quiere conectarlas con fibra. Cada oficina debe llegar a todas las demás, directamente o a través de otras oficinas. Cavar es caro: cada cable posible tiene un precio en miles de euros (mil €).
offices = ["Centro", "Norte", "Sur", "Este", "Oeste", "Aeropuerto"]cables = [ ("Centro", "Norte", 4), ("Centro", "Sur", 6), ("Centro", "Este", 8), ("Centro", "Oeste", 5), ("Norte", "Este", 9), ("Norte", "Oeste", 3), ("Sur", "Oeste", 7), ("Sur", "Aeropuerto", 11), ("Este", "Aeropuerto", 2),]Tender los nueve cables cuesta 55 mil €. Pero no hacen falta todos. Si tres oficinas están conectadas en anillo, un cable del anillo sobra: quítalo y todo sigue conectado. La red más barata no tiene ningún ciclo. Un grafo conexo sin ciclos es un árbol, y un árbol con V vértices tiene exactamente V − 1 aristas: aquí 5 cables.
¿Cuáles cinco? Buscas el árbol que abarca todas las oficinas al menor precio total. Eso es un árbol de expansión mínima (MST).
La idea
El cable más barato que no cierra un ciclo
El algoritmo de Kruskal (Joseph Kruskal, 1956):
- Ordena los cables por precio, el más barato primero.
- Para cada cable: si sus dos extremos aún no están conectados, tiéndelo. Si ya están conectados por cables tendidos, el cable cerraría un ciclo: sáltalo.
- Para cuando haya V − 1 cables.
Al principio cada oficina es un grupo aparte. Cada cable tendido fusiona dos grupos en uno. La pregunta «¿están conectados los dos extremos?» es exactamente la pregunta «¿están en un mismo grupo?», y hay una estructura para eso: Union-Find. union(a, b) fusiona los grupos y devuelve false si a y b ya están en un mismo grupo. Una comprobación en vez de una búsqueda por el mapa.
Míralo
Kruskal por dentro
La clase UnionFind es la misma que en la lección de Union-Find, sin cambios. Un cable es una tupla (oficina, oficina, precio), e index convierte el nombre de una oficina en un número, porque Union-Find trabaja con números.
def kruskal(offices, cables): index = {o: i for i, o in enumerate(offices)} groups = UnionFind(len(offices)) tree = [] for a, b, cost in sorted(cables, key=lambda c: c[2]): if not groups.union(index[a], index[b]): continue # un ciclo tree.append((a, b, cost)) if len(tree) == len(offices) - 1: break return treesorted con key=lambda c: c[2] ordena por el tercer elemento, el precio, y es estable.total = 0for a, b, cost in kruskal(offices, cables): print(f"{a} – {b}: {cost} mil €") total += costprint(f"Total: {total} mil €")Este – Aeropuerto: 2 mil €Norte – Oeste: 3 mil €Centro – Norte: 4 mil €Centro – Sur: 6 mil €Centro – Este: 8 mil €Total: 23 mil €def kruskal(offices, cables): index = {o: i for i, o in enumerate(offices)} groups = UnionFind(len(offices)) tree = [] for a, b, cost in sorted(cables, key=lambda c: c[2]): if not groups.union(index[a], index[b]): continue # un ciclo tree.append((a, b, cost)) if len(tree) == len(offices) - 1: break return treePaso a paso, en palabras
- Seis oficinas, nueve cables posibles, cada uno con un precio en miles de euros. La red tiene que conectar todas las oficinas lo más barato posible. A la derecha los cables se ordenan por precio: Kruskal los mira empezando por el más barato. Al principio cada oficina es un grupo aparte.
- Este – Aeropuerto, 2: grupos distintos. El cable se tiende y union fusiona los dos grupos en uno (el mismo color).
- Norte – Oeste, 3: otra vez grupos distintos. Aparece un segundo grupo, aparte: Kruskal construye varias piezas a la vez, no un único árbol que crece.
- Centro – Norte, 4: la oficina Centro entra en el grupo de Norte y Oeste.
- Centro – Oeste, 5: los dos extremos ya están en un mismo grupo, a través de Norte. Este cable cerraría un ciclo: union devuelve false y el cable se rechaza.
- Centro – Sur, 6: la oficina Sur está sola, así que el cable se tiende.
- Sur – Oeste, 7: Sur y Oeste ya están conectadas a través de Centro. Rechazado.
- Centro – Este, 8: el cable más barato entre los dos grupos. Los fusiona, y ya son cinco cables: seis oficinas, cinco cables, todo está conectado.
- El bucle termina: Norte – Este y Sur – Aeropuerto ni siquiera se miran. Total 23 mil €, frente a 55 de los nueve cables.
Dos grupos crecen por separado: el azul (Este, Aeropuerto) y el verde, que parte de Norte y Oeste. El cable Centro – Este es el más barato entre ellos y los fusiona. Los cables Norte – Este (9) y Sur – Aeropuerto (11) nunca se miran.
Pruébalo
Predice la salida
La autopista al aeropuerto resulta ser un problema: el cable Este – Aeropuerto ahora cuesta 12. ¿Cuánto cuesta la nueva red?
changed = cables[:-1] + [("Este", "Aeropuerto", 12)]total = sum(cost for _, _, cost in kruskal(offices, changed))print(f"Total: {total} mil €")Pruébalo
Completa
tree.append((a, b, cost))
if len(tree) == :
breakUn árbol con V oficinas tiene V − 1 cables. Cuando hay tantos, todo está conectado y cualquier cable más cerraría un ciclo, así que el bucle termina.
La idea
Por qué lo voraz acierta aquí
Kruskal es un algoritmo voraz: en cada paso toma la mejor opción del momento (el cable más barato que encaja) y nunca vuelve atrás. Lo voraz a menudo engaña: mira cuándo funciona lo voraz y cuándo falla. Aquí funciona, y la razón es la propiedad del corte.
Divide las oficinas en dos partes de cualquier manera, por ejemplo el grupo Este y todo lo demás. Los cables que van entre las dos partes son el corte. El cable más barato del corte está en el árbol mínimo. ¿Por qué? El árbol necesita al menos un cable que cruce el corte, o las dos partes no están conectadas. Si ese cable es más caro, cámbialo por el más barato: la red sigue conectada y el precio baja.
Cada cable que tiende Kruskal es el más barato del corte entre el grupo de uno de sus extremos y todo lo demás: todos los cables más baratos ya pasaron y están dentro de grupos. Centro – Este (8) es el más barato de Centro – Este, Norte – Este (9) y Sur – Aeropuerto (11), los cables entre los dos grupos.
Pruébalo
Encuentra el error
Un compañero decidió que union sobra y solo pregunta con find si los dos extremos están en un mismo grupo:
def kruskal(offices, cables): index = {o: i for i, o in enumerate(offices)} groups = UnionFind(len(offices)) tree = [] for a, b, cost in sorted(cables, key=lambda c: c[2]): if groups.find(index[a]) == groups.find(index[b]): continue tree.append((a, b, cost)) if len(tree) == len(offices) - 1: break return treetotal = 0for a, b, cost in kruskal(offices, cables): print(f"{a} – {b}: {cost} mil €") total += costprint(f"Total: {total} mil €")Este – Aeropuerto: 2 mil €Norte – Oeste: 3 mil €Centro – Norte: 4 mil €Centro – Oeste: 5 mil €Centro – Sur: 6 mil €Total: 20 mil €20 mil € en vez de 23, pero Este y Aeropuerto quedan aislados, y Centro, Norte y Oeste forman un anillo. ¿En qué línea está el error?
Elige la línea con el error.
find solo pregunta, no fusiona. Los grupos nunca se fusionan, cada cable une grupos «distintos» y entra hasta que hay cinco. Hace falta union: comprueba y fusiona a la vez.
La idea
Lo que cuesta
Ordenar E cables cuesta O(E log E). Después cada comprobación con Union-Find es casi O(1) (mira la lección de Union-Find). En total O(E log E): la ordenación es la parte cara.
Sin Union-Find, «¿están conectados?» se pregunta con la búsqueda en profundidad sobre los cables tendidos hasta ahora:
def connected(net, start, goal): stack = [start] seen = {start} while stack: office = stack.pop() if office == goal: return True for other in net[office]: if other not in seen: seen.add(other) stack.append(other) return False
def kruskal_slow(offices, cables): net = {office: [] for office in offices} tree = [] for a, b, cost in sorted(cables, key=lambda c: c[2]): if connected(net, a, b): continue net[a].append(b) net[b].append(a) tree.append((a, b, cost)) if len(tree) == len(offices) - 1: break return treeLa respuesta es la misma. Pero cada búsqueda puede recorrer todo el grupo, O(V), y se ejecuta para cada cable: O(E · V).
Ejecuta las dos versiones con oficinas en una cuadrícula: cada oficina puede unirse con su vecina de la derecha y la de abajo, a un precio de 1 a 1000. Se cuenta cada comparación de dos precios al ordenar, cada vecino que mira la búsqueda en profundidad y cada paso a un padre en find.
- Kruskal con DFS: una búsqueda por los cables tendidos
O(n²) - Kruskal con union-find
O(n log n)
| Algoritmo | n = 100 | n = 1000 | n = 10.000 | n = 100.000 |
|---|---|---|---|---|
| Kruskal con DFS: una búsqueda por los cables tendidos | 4945 | 677.351 | ≈ 67.735.100 | ≈ 6.773.510.000 |
| Kruskal con union-find | 1460 | 23.827 | 321.171 | 3.884.598 |
def kruskal(offices, cables): index = {o: i for i, o in enumerate(offices)} groups = UnionFind(len(offices)) tree = [] for a, b, cost in sorted(cables, key=lambda c: c[2]): if not groups.union(index[a], index[b]): continue # un ciclo tree.append((a, b, cost)) if len(tree) == len(offices) - 1: break return treeCon 1000 oficinas la búsqueda en profundidad da 677 351 pasos, Union-Find 23 827. Con 100 000 oficinas Union-Find hace 3 884 598, y la búsqueda en profundidad haría miles de millones: Bench no las ejecuta, sino que las estima a partir de la curva.
La idea
No es el camino más corto
En el árbol mínimo el camino de Sur a Aeropuerto es Sur – Centro – Este – Aeropuerto: 6 + 8 + 2 = 16. El cable directo Sur – Aeropuerto cuesta 11, pero no está en la red.
Un árbol de expansión mínima ahorra en el precio total de la red. No promete nada sobre el camino entre dos oficinas. Si el precio es el retraso y quieres el camino más rápido entre dos oficinas, es otro problema: Dijkstra.
Más precisamente, para curiosos
Prim es el otro algoritmo clásico para un árbol de expansión mínima. Parte de una oficina y cada vez añade el cable más barato del árbol a una oficina de fuera. La cola es una cola de prioridad, como en Dijkstra, solo que la prioridad es el precio del cable, no el camino desde el inicio. Con un montículo (heap) binario es O(E log V). Kruskal es más simple cuando los cables son una lista, Prim cuando el grafo viene dado por vecinos y es denso.
Si algunos cables tienen el mismo precio, puede haber varios árboles mínimos, todos con el mismo precio total. Kruskal devuelve uno de ellos, según el orden de los iguales.
Dónde más: redes eléctricas y de agua, carreteras entre pueblos, placas de circuitos. Si detienes Kruskal antes de que los grupos se vuelvan uno (digamos, con k grupos), obtienes un agrupamiento (clustering): los puntos de un grupo están cerca, y los grupos están lejos unos de otros.
Ejercicio
Un cable ya tendido
Resuélvelo en tu editor.
Un cable viejo. Ya hay un cable entre Norte y Este: no cuesta nada. Escribe un método que reciba también los cables tendidos y encuentre cuáles nuevos añadir. Imprime los cables tendidos y los nuevos, y el precio de los nuevos:
Ya tendido: Norte – EsteEste – Aeropuerto: 2 mil €Norte – Oeste: 3 mil €Centro – Norte: 4 mil €Centro – Sur: 6 mil €Cables nuevos: 15 mil €Pista: antes del bucle, fusiona en Union-Find los extremos de los cables tendidos. Para cuando quede un solo grupo.
Más tareas
- Los rechazados. Imprime también los cables rechazados, cada uno con el motivo: qué ciclo cerraría.
- Dos redes. La empresa quiere dos redes separadas. Detén Kruskal cuando haya dos grupos. ¿Qué oficinas comparten red?
- Imposible. Quita todos los cables al Aeropuerto. ¿Qué devuelve Kruskal? ¿Cómo notas que la red no conecta todas las oficinas?
Test