El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Árboles de Expansión Mínima

Siguiente ►
►

En la lección anterior minimizamos el coste de una ruta entre dos puntos. Esta lección cambia la pregunta por completo: dado un conjunto de nodos que hay que conectar todos entre sí, ¿qué conexiones elegimos para que el coste total sea mínimo? La respuesta es el árbol de expansión mínima (MST, Minimum Spanning Tree), un problema de grafos no dirigidos que aparece siempre que se diseña una red: cablear oficinas, tender fibra entre sedes o —en la versión TaskFlow más de "infraestructura" de todo el curso— decidir qué canales de coordinación mantener entre equipos. Veremos los dos algoritmos clásicos, Prim (primo hermano de Dijkstra, otra vez con heapq) y Kruskal, que nos obligará a construir una estructura auxiliar nueva y deliciosa: Union-Find.

Contenido

  1. Qué es un árbol de expansión mínima
  2. MST frente a caminos mínimos: no confundirlos
  3. El grafo de ejemplo: coordinar los equipos de TaskFlow
  4. Prim: crecer el árbol desde un vértice
  5. Kruskal: aristas baratas primero, sin formar ciclos
  6. Union-Find: la estructura que hace rápido a Kruskal
  7. Traza de Kruskal
  8. Prim frente a Kruskal

Qué es un árbol de expansión mínima

Dado un grafo no dirigido, ponderado y conexo, un árbol de expansión es un subgrafo que:

  • incluye todos los vértices,
  • es conexo (todo conectado con todo, quizá con escalas),
  • es acíclico — y por la lección 07-01 sabemos que "conexo + acíclico" = árbol, con exactamente n − 1 aristas.

De todos los árboles de expansión posibles, el mínimo es el de menor suma de pesos. La intuición de por qué basta un árbol: si una selección de aristas contiene un ciclo, se puede quitar la arista más cara del ciclo sin desconectar nada — luego la solución óptima nunca tiene ciclos.

Dos restricciones importantes del problema:

  • Solo grafos no dirigidos. "Conectar" es simétrico; en dirigidos el problema análogo (arborescencias) es otro y no lo cubrimos.
  • Solo grafos conexos. Si hay islas, no existe árbol que lo abarque todo; se calcula entonces un bosque de expansión, un MST por componente (Kruskal lo hace gratis, como veremos).

MST frente a caminos mínimos: no confundirlos

Son los dos grandes problemas de optimización en grafos ponderados y se confunden con facilidad:

Caminos mínimos (07-04) MST (esta lección)
Pregunta ¿Ruta más barata de A a B? ¿Red más barata que conecte todo?
Optimiza El coste de cada ruta desde el origen El coste total de las aristas elegidas
Grafo Dirigido o no No dirigido
Resultado Árbol de caminos mínimos desde un origen Árbol sin origen privilegiado
Garantía que NO da — El camino entre dos nodos dentro del MST puede no ser su camino mínimo

El último punto es el que engaña: en el MST, ir de un nodo a otro puede requerir un rodeo más caro que su camino mínimo directo en el grafo original. El MST ahorra en la factura total de la red, no en cada trayecto.

El grafo de ejemplo: coordinar los equipos de TaskFlow

Cinco equipos usan TaskFlow: backend, frontend, datos, qa y diseno. Mantener un canal de coordinación estable entre dos equipos (reuniones, integraciones, documentación compartida) tiene un coste semanal en horas, distinto por pareja. Queremos que la información pueda fluir entre cualquier par de equipos (directamente o a través de otros) pagando el mínimo total:

equipos = Grafo(dirigido=False)      # coordinar es simétrico
equipos.anadir_arista("backend", "frontend", 4)
equipos.anadir_arista("backend", "datos", 2)
equipos.anadir_arista("backend", "qa", 7)
equipos.anadir_arista("datos", "qa", 3)
equipos.anadir_arista("frontend", "qa", 5)
equipos.anadir_arista("frontend", "diseno", 1)
equipos.anadir_arista("diseno", "qa", 6)
graph LR
    B[backend] ---|4| F[frontend]
    B ---|2| D[datos]
    B ---|7| Q[qa]
    D ---|3| Q
    F ---|5| Q
    F ---|1| S[diseno]
    S ---|6| Q

Con 5 vértices, el MST tendrá exactamente 4 aristas. Adelantamos la solución para poder comprobar los dos algoritmos: frontend–diseno (1), backend–datos (2), datos–qa (3) y backend–frontend (4), total 10 horas semanales.

Prim: crecer el árbol desde un vértice

Prim construye el MST como una mancha de aceite: empieza en un vértice cualquiera y, en cada paso, añade la arista más barata que conecta el árbol actual con un vértice de fuera. ¿"La más barata disponible"? Otra vez heapq:

import heapq

def prim(grafo, inicio):
    """Devuelve (aristas_del_mst, coste_total). Grafo no dirigido y conexo."""
    en_arbol = {inicio}
    aristas_mst = []
    total = 0
    # (peso, origen, destino): el heap ordena por peso, como en Dijkstra
    monticulo = [(peso, inicio, destino)
                 for destino, peso in grafo.vecinos(inicio).items()]
    heapq.heapify(monticulo)             # montículo en O(n), módulo 6

    while monticulo and len(en_arbol) < len(grafo.vertices()):
        peso, origen, destino = heapq.heappop(monticulo)
        if destino in en_arbol:
            continue                     # arista obsoleta: ya está dentro
        en_arbol.add(destino)            # incorporar el vértice nuevo
        aristas_mst.append((origen, destino, peso))
        total += peso
        for vecino, p in grafo.vecinos(destino).items():
            if vecino not in en_arbol:   # ofertas del recién llegado
                heapq.heappush(monticulo, (p, destino, vecino))
    return aristas_mst, total

aristas, total = prim(equipos, "backend")
print(aristas)
# [('backend', 'datos', 2), ('datos', 'qa', 3), ('backend', 'frontend', 4),
#  ('frontend', 'diseno', 1)]
print(total)   # 10

Si este código te suena, es porque es el esqueleto de Dijkstra con una sola diferencia: la prioridad. Dijkstra ordena el montículo por distancia acumulada desde el origen (dist + peso); Prim, por peso de la arista suelta (peso). Dijkstra minimiza rutas; Prim minimiza la factura de conexión. Misma maquinaria, distinta pregunta — merece la pena comparar ambos códigos lado a lado hasta ver la diferencia de una línea.

Traza desde backend (mancha de aceite):

Paso Sale del montículo ¿Se acepta? Árbol tras el paso Total
1 (2, backend, datos) Sí {backend, datos} 2
2 (3, datos, qa) Sí + qa 5
3 (4, backend, frontend) Sí + frontend 9
4 (1, frontend, diseno) Sí + diseno: árbol completo 10

Observa el paso 4: al incorporar frontend entra en el montículo su arista barata hacia diseno (peso 1), que adelanta a las ofertas caras pendientes — (5, frontend, qa), (6, qa, diseno) y (7, backend, qa) se quedan dentro sin llegar a salir, porque con los 5 vértices incorporados el bucle termina.

Coste: O(a · log n), como Dijkstra.

Kruskal: aristas baratas primero, sin formar ciclos

Kruskal ataca por el otro flanco: ordena todas las aristas de menor a mayor peso (aquí brilla la lista de aristas mencionada en 07-02) y las va aceptando una a una, con una única regla: rechazar toda arista cuyos dos extremos ya estén conectados (formaría un ciclo). Se detiene al aceptar n − 1.

La dificultad está en la regla: "¿están ya conectados u y v?" hay que responderla miles de veces, muy rápido. ¿BFS por consulta? O(n + a) cada vez: demasiado. La respuesta es una estructura nueva.

Union-Find: la estructura que hace rápido a Kruskal

Union-Find (o conjuntos disjuntos) mantiene una colección de conjuntos que solo saben hacer dos cosas, ambas casi en O(1):

  • encontrar(x): ¿cuál es el representante del conjunto de x? (dos elementos están conectados si comparten representante),
  • unir(x, y): fusionar los conjuntos de x e y.

La implementación es sorprendentemente pequeña: cada elemento apunta a un "padre" y el representante es la raíz de esa cadena — internamente es un bosque de arbolitos, un guiño más al módulo 6. Dos optimizaciones la hacen volar:

  • Compresión de caminos: al buscar la raíz, reengancha cada nodo visitado directamente a ella; la próxima búsqueda será casi instantánea.
  • Unión por rango: al fusionar, el árbol de menor altura estimada (rango) se cuelga del mayor, evitando cadenas largas.
class UnionFind:
    def __init__(self, elementos):
        self.padre = {x: x for x in elementos}   # cada uno, su propia raíz
        self.rango = {x: 0 for x in elementos}

    def encontrar(self, x):
        raiz = x
        while self.padre[raiz] != raiz:          # subir hasta la raíz
            raiz = self.padre[raiz]
        while self.padre[x] != raiz:             # compresión de caminos:
            self.padre[x], x = raiz, self.padre[x]   # reenganchar directo a la raíz
        return raiz

    def unir(self, x, y):
        rx, ry = self.encontrar(x), self.encontrar(y)
        if rx == ry:
            return False                         # ya estaban conectados
        if self.rango[rx] < self.rango[ry]:      # unión por rango:
            rx, ry = ry, rx                      # rx pasa a ser el más alto
        self.padre[ry] = rx                      # el bajo se cuelga del alto
        if self.rango[rx] == self.rango[ry]:
            self.rango[rx] += 1                  # solo crece si empataban
        return True

Con ambas optimizaciones, una secuencia de operaciones cuesta en la práctica tiempo casi constante por operación (técnicamente O(α(n)), donde α es la inversa de Ackermann: ≤ 4 para cualquier n imaginable). Fíjate en el detalle de diseño: unir devuelve False si ya estaban conectados — exactamente la pregunta de Kruskal, respondida de paso.

def kruskal(grafo):
    aristas = sorted(                        # lista de aristas por peso
        {tuple(sorted((u, v))) + (p,)        # (u, v, p) sin duplicar u-v / v-u
         for u in grafo.vertices()
         for v, p in grafo.vecinos(u).items()},
        key=lambda a: a[2])
    uf = UnionFind(grafo.vertices())
    mst, total = [], 0
    for u, v, p in aristas:
        if uf.unir(u, v):                    # False = formaría ciclo: se salta
            mst.append((u, v, p))
            total += p
            if len(mst) == len(grafo.vertices()) - 1:
                break                        # árbol completo: n - 1 aristas
    return mst, total

print(kruskal(equipos))
# ([('diseno', 'frontend', 1), ('backend', 'datos', 2), ('datos', 'qa', 3),
#   ('backend', 'frontend', 4)], 10)

Nota sobre la construcción de aristas: como el grafo no dirigido guarda cada arista en ambos sentidos, tuple(sorted((u, v))) normaliza la pareja y el set elimina el duplicado. Coste total de Kruskal: O(a · log a), dominado por la ordenación.

Traza de Kruskal

Aristas ordenadas: (diseno–frontend, 1), (backend–datos, 2), (datos–qa, 3), (backend–frontend, 4), (frontend–qa, 5), (diseno–qa, 6), (backend–qa, 7).

Arista ¿Extremos ya conectados? Decisión Conjuntos tras el paso
diseno–frontend (1) No Aceptar {diseno, frontend} {backend} {datos} {qa}
backend–datos (2) No Aceptar {diseno, frontend} {backend, datos} {qa}
datos–qa (3) No Aceptar {diseno, frontend} {backend, datos, qa}
backend–frontend (4) No Aceptar → 4 aristas: fin {todos}
frontend–qa (5) (no llega a evaluarse) — —

Mismo árbol y mismo total (10) que Prim — como debe ser: cuando los pesos no se repiten, el MST es único. Observa la diferencia de estilo: Prim mantiene un árbol que crece; Kruskal mantiene un bosque de fragmentos que se van fusionando (por eso, en un grafo no conexo, Kruskal termina con un MST por isla sin cambiar ni una línea).

Prim frente a Kruskal

Prim Kruskal
Estrategia Crecer un árbol desde un vértice Aceptar aristas globalmente baratas
Estructura de apoyo heapq (módulo 4) Ordenación + Union-Find
Coste O(a · log n) O(a · log a)
Cómodo cuando... Grafo denso, lista de adyacencia Grafo disperso, aristas ya como lista
Grafo no conexo Solo cubre la componente inicial Da el bosque completo gratis
Parecido a Dijkstra (cambia la prioridad) Un filtro codicioso sobre aristas ordenadas

Ambos son algoritmos codiciosos (greedy): toman en cada paso la opción localmente más barata y, para este problema —a diferencia de tantos otros—, eso lleva demostradamente al óptimo global.

Errores Comunes y Consejos

  • Aplicar MST a un grafo dirigido. El problema está definido para no dirigidos; construye el grafo con Grafo(dirigido=False) o los algoritmos darán resultados sin sentido.
  • Confundir MST con caminos mínimos y usar el árbol de Prim para responder "¿ruta más barata de A a B?". Repasa la tabla de la sección 2: optimizan cosas distintas.
  • Olvidar el continue de aristas obsoletas en Prim: aceptarías aristas hacia vértices ya incorporados, creando ciclos y sumando coste de más.
  • Implementar Union-Find sin compresión ni rango. Funciona, pero los árboles internos degeneran en cadenas y encontrar pasa a O(n) — la misma degeneración que sufría el ABB sin equilibrar en el módulo 6.
  • Duplicar aristas en Kruskal al extraerlas de un grafo no dirigido (u–v y v–u): o normalizas como hicimos, o el algoritmo evalúa todo dos veces (no rompe el resultado, pero delata descuido).
  • Consejo: Union-Find vale mucho más que Kruskal: conectividad dinámica, detección de ciclos al vuelo, agrupamiento... En los ejercicios finales (07-07) la alternativa BFS para componentes conexas te hará apreciar cuándo brilla cada una.

Ejercicios

Ejercicio 1: MST a mano

Añade un sexto equipo: movil, con aristas movil–frontend (2) y movil–qa (4). Calcula el nuevo MST con Kruskal a mano (tabla de decisiones) y su coste total.

Ejercicio 2: el rodeo del MST

En el MST de la lección, ¿cuál es el camino entre diseno y qa y cuánto cuesta sumando sus aristas? Compáralo con la arista directa diseno–qa (6) y explica por qué el MST "prefiere" el rodeo.

Ejercicio 3: Union-Find como detector de ciclos

Usando solo UnionFind (sin DFS), escribe tiene_ciclo_no_dirigido(aristas, vertices) que detecte si un grafo no dirigido dado como lista de aristas contiene algún ciclo. Pista: ¿qué significa que unir devuelva False?

Soluciones

Solución 1: Aristas ordenadas: 1 (diseno–frontend), 2 (backend–datos), 2 (movil–frontend), 3 (datos–qa), 4 (backend–frontend), 4 (movil–qa), 5, 6, 7. Decisiones: aceptar 1, 2, 2, 3, 4 (backend–frontend une {diseno, frontend, movil} con {backend, datos, qa}); con 5 aristas para 6 vértices, fin. movil–qa (4) ya no se evalúa (conectados vía frontend...backend...qa). Total: 1 + 2 + 2 + 3 + 4 = 12.

Solución 2: En el MST, de diseno a qa se va por diseno–frontend–backend–datos–qa: 1 + 4 + 2 + 3 = 10, frente a 6 de la arista directa. El MST descartó diseno–qa porque cuando le llegó el turno sus extremos ya estaban conectados: para la factura total de la red esa arista era redundante. Es la demostración práctica de la advertencia de la sección 2: el MST no promete buenos trayectos individuales, solo la red completa más barata.

Solución 3:

def tiene_ciclo_no_dirigido(aristas, vertices):
    uf = UnionFind(vertices)
    for u, v in aristas:
        if not uf.unir(u, v):    # ya conectados: esta arista cierra un ciclo
            return True
    return False

print(tiene_ciclo_no_dirigido(
    [("a", "b"), ("b", "c")], ["a", "b", "c"]))          # False
print(tiene_ciclo_no_dirigido(
    [("a", "b"), ("b", "c"), ("c", "a")], ["a", "b", "c"]))  # True

Si unir devuelve False, los extremos ya compartían conjunto: había un camino entre ellos y la nueva arista lo cierra en ciclo. Es la tercera técnica de detección de ciclos del curso (Floyd en listas, blanco/gris/negro en dirigidos, Union-Find en no dirigidos), cada una en su terreno.

Conclusión

El MST responde una pregunta distinta a la de los caminos mínimos —minimizar la red total, no cada trayecto— y solo vive en grafos no dirigidos. Prim lo construye como una mancha de aceite con el heapq de siempre (una línea lo separa de Dijkstra); Kruskal ordena las aristas y filtra ciclos con Union-Find, la nueva estructura auxiliar que con compresión de caminos y unión por rango responde "¿están conectados?" en tiempo casi constante. Con esto ya está completa la caja de herramientas del módulo: recorridos, ciclos, órdenes, caminos y redes. La próxima lección no añade ningún algoritmo más: los pone todos a trabajar juntos — el planificador completo de TaskFlow (orden, ciclos, paralelismo y ruta crítica), sugerencias de colaboradores al estilo red social y hasta un PageRank en miniatura.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2026. Todos los derechos reservados