El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Arbres d'Expansió Mínima

Següent ►
►

A la lliçó anterior vam minimitzar el cost d'una ruta entre dos punts. Aquesta lliçó canvia la pregunta per complet: donat un conjunt de nodes que cal connectar tots entre si, quines connexions triem perquè el cost total sigui mínim? La resposta és l'arbre d'expansió mínima (MST, Minimum Spanning Tree), un problema de grafs no dirigits que apareix sempre que es dissenya una xarxa: cablejar oficines, estendre fibra entre seus o —en la versió TaskFlow més d'"infraestructura" de tot el curs— decidir quins canals de coordinació mantenir entre equips. Veurem els dos algorismes clàssics, Prim (cosí germà de Dijkstra, un altre cop amb heapq) i Kruskal, que ens obligarà a construir una estructura auxiliar nova i deliciosa: Union-Find.

Contingut

  1. Què és un arbre d'expansió mínima
  2. MST davant de camins mínims: no confondre'ls
  3. El graf d'exemple: coordinar els equips de TaskFlow
  4. Prim: fer créixer l'arbre des d'un vèrtex
  5. Kruskal: arestes barates primer, sense formar cicles
  6. Union-Find: l'estructura que fa ràpid Kruskal
  7. Traça de Kruskal
  8. Prim davant de Kruskal

Què és un arbre d'expansió mínima

Donat un graf no dirigit, ponderat i connex, un arbre d'expansió és un subgraf que:

  • inclou tots els vèrtexs,
  • és connex (tot connectat amb tot, potser amb escales),
  • és acíclic — i per la lliçó 07-01 sabem que "connex + acíclic" = arbre, amb exactament n − 1 arestes.

De tots els arbres d'expansió possibles, el mínim és el de menor suma de pesos. La intuïció de per què n'hi ha prou amb un arbre: si una selecció d'arestes conté un cicle, es pot treure l'aresta més cara del cicle sense desconnectar res — per tant la solució òptima mai no té cicles.

Dues restriccions importants del problema:

  • Només grafs no dirigits. "Connectar" és simètric; en dirigits el problema anàleg (arborescències) és un altre i no el cobrim.
  • Només grafs connexos. Si hi ha illes, no existeix cap arbre que ho abasti tot; es calcula llavors un bosc d'expansió, un MST per component (Kruskal ho fa gratis, com veurem).

MST davant de camins mínims: no confondre'ls

Són els dos grans problemes d'optimització en grafs ponderats i es confonen amb facilitat:

Camins mínims (07-04) MST (aquesta lliçó)
Pregunta Ruta més barata d'A a B? Xarxa més barata que ho connecti tot?
Optimitza El cost de cada ruta des de l'origen El cost total de les arestes triades
Graf Dirigit o no No dirigit
Resultat Arbre de camins mínims des d'un origen Arbre sense origen privilegiat
Garantia que NO dóna — El camí entre dos nodes dins del MST pot no ser el seu camí mínim

L'últim punt és el que enganya: al MST, anar d'un node a un altre pot requerir una marrada més cara que el seu camí mínim directe al graf original. El MST estalvia en la factura total de la xarxa, no en cada trajecte.

El graf d'exemple: coordinar els equips de TaskFlow

Cinc equips fan servir TaskFlow: backend, frontend, dades, qa i disseny. Mantenir un canal de coordinació estable entre dos equips (reunions, integracions, documentació compartida) té un cost setmanal en hores, diferent per parella. Volem que la informació pugui fluir entre qualsevol parell d'equips (directament o a través d'altres) pagant el mínim total:

equips = Graf(dirigit=False)         # coordinar és simètric
equips.afegir_aresta("backend", "frontend", 4)
equips.afegir_aresta("backend", "dades", 2)
equips.afegir_aresta("backend", "qa", 7)
equips.afegir_aresta("dades", "qa", 3)
equips.afegir_aresta("frontend", "qa", 5)
equips.afegir_aresta("frontend", "disseny", 1)
equips.afegir_aresta("disseny", "qa", 6)
graph LR
    B[backend] ---|4| F[frontend]
    B ---|2| D[dades]
    B ---|7| Q[qa]
    D ---|3| Q
    F ---|5| Q
    F ---|1| S[disseny]
    S ---|6| Q

Amb 5 vèrtexs, el MST tindrà exactament 4 arestes. Avancem la solució per poder comprovar els dos algorismes: frontend–disseny (1), backend–dades (2), dades–qa (3) i backend–frontend (4), total 10 hores setmanals.

Prim: fer créixer l'arbre des d'un vèrtex

Prim construeix el MST com una taca d'oli: comença en un vèrtex qualsevol i, a cada pas, afegeix l'aresta més barata que connecta l'arbre actual amb un vèrtex de fora. "La més barata disponible"? Un altre cop heapq:

import heapq

def prim(graf, inici):
    """Retorna (arestes_del_mst, cost_total). Graf no dirigit i connex."""
    en_arbre = {inici}
    arestes_mst = []
    total = 0
    # (pes, origen, desti): el heap ordena per pes, com a Dijkstra
    monticle = [(pes, inici, desti)
                for desti, pes in graf.veins(inici).items()]
    heapq.heapify(monticle)              # monticle en O(n), mòdul 6

    while monticle and len(en_arbre) < len(graf.vertexs()):
        pes, origen, desti = heapq.heappop(monticle)
        if desti in en_arbre:
            continue                     # aresta obsoleta: ja és dins
        en_arbre.add(desti)              # incorporar el vèrtex nou
        arestes_mst.append((origen, desti, pes))
        total += pes
        for vei, p in graf.veins(desti).items():
            if vei not in en_arbre:      # ofertes del nouvingut
                heapq.heappush(monticle, (p, desti, vei))
    return arestes_mst, total

arestes, total = prim(equips, "backend")
print(arestes)
# [('backend', 'dades', 2), ('dades', 'qa', 3), ('backend', 'frontend', 4),
#  ('frontend', 'disseny', 1)]
print(total)   # 10

Si aquest codi et sona, és perquè és l'esquelet de Dijkstra amb una sola diferència: la prioritat. Dijkstra ordena el monticle per distància acumulada des de l'origen (dist + pes); Prim, per pes de l'aresta solta (pes). Dijkstra minimitza rutes; Prim minimitza la factura de connexió. Mateixa maquinària, diferent pregunta — val la pena comparar els dos codis costat a costat fins a veure la diferència d'una línia.

Traça des de backend (taca d'oli):

Pas Surt del monticle S'accepta? Arbre després del pas Total
1 (2, backend, dades) Sí {backend, dades} 2
2 (3, dades, qa) Sí + qa 5
3 (4, backend, frontend) Sí + frontend 9
4 (1, frontend, disseny) Sí + disseny: arbre complet 10

Observa el pas 4: en incorporar frontend entra al monticle la seva aresta barata cap a disseny (pes 1), que avança les ofertes cares pendents — (5, frontend, qa), (6, qa, disseny) i (7, backend, qa) es queden dins sense arribar a sortir, perquè amb els 5 vèrtexs incorporats el bucle acaba.

Cost: O(a · log n), com Dijkstra.

Kruskal: arestes barates primer, sense formar cicles

Kruskal ataca per l'altre flanc: ordena totes les arestes de menor a major pes (aquí brilla la llista d'arestes esmentada a la 07-02) i les va acceptant una a una, amb una única regla: rebutjar tota aresta els dos extrems de la qual ja estiguin connectats (formaria un cicle). S'atura en acceptar-ne n − 1.

La dificultat és a la regla: "ja estan connectats u i v?" s'ha de respondre milers de vegades, molt ràpid. BFS per consulta? O(n + a) cada vegada: massa. La resposta és una estructura nova.

Union-Find: l'estructura que fa ràpid Kruskal

Union-Find (o conjunts disjunts) manté una col·lecció de conjunts que només saben fer dues coses, totes dues gairebé en O(1):

  • trobar(x): quin és el representant del conjunt de x? (dos elements estan connectats si comparteixen representant),
  • unir(x, y): fusionar els conjunts de x i y.

La implementació és sorprenentment petita: cada element apunta a un "pare" i el representant és l'arrel d'aquesta cadena — internament és un bosc d'arbrets, una picada d'ullet més al mòdul 6. Dues optimitzacions la fan volar:

  • Compressió de camins: en buscar l'arrel, reenganxa cada node visitat directament a ella; la propera cerca serà gairebé instantània.
  • Unió per rang: en fusionar, l'arbre de menor alçada estimada (rang) es penja del major, evitant cadenes llargues.
class UnionFind:
    def __init__(self, elements):
        self.pare = {x: x for x in elements}     # cadascun, la seva pròpia arrel
        self.rang = {x: 0 for x in elements}

    def trobar(self, x):
        arrel = x
        while self.pare[arrel] != arrel:         # pujar fins a l'arrel
            arrel = self.pare[arrel]
        while self.pare[x] != arrel:             # compressió de camins:
            self.pare[x], x = arrel, self.pare[x]    # reenganxar directe a l'arrel
        return arrel

    def unir(self, x, y):
        rx, ry = self.trobar(x), self.trobar(y)
        if rx == ry:
            return False                         # ja estaven connectats
        if self.rang[rx] < self.rang[ry]:        # unió per rang:
            rx, ry = ry, rx                      # rx passa a ser el més alt
        self.pare[ry] = rx                       # el baix es penja de l'alt
        if self.rang[rx] == self.rang[ry]:
            self.rang[rx] += 1                   # només creix si empataven
        return True

Amb totes dues optimitzacions, una seqüència d'operacions costa a la pràctica temps gairebé constant per operació (tècnicament O(α(n)), on α és la inversa d'Ackermann: ≤ 4 per a qualsevol n imaginable). Fixa't en el detall de disseny: unir retorna False si ja estaven connectats — exactament la pregunta de Kruskal, resposta de passada.

def kruskal(graf):
    arestes = sorted(                        # llista d'arestes per pes
        {tuple(sorted((u, v))) + (p,)        # (u, v, p) sense duplicar u-v / v-u
         for u in graf.vertexs()
         for v, p in graf.veins(u).items()},
        key=lambda a: a[2])
    uf = UnionFind(graf.vertexs())
    mst, total = [], 0
    for u, v, p in arestes:
        if uf.unir(u, v):                    # False = formaria cicle: se salta
            mst.append((u, v, p))
            total += p
            if len(mst) == len(graf.vertexs()) - 1:
                break                        # arbre complet: n - 1 arestes
    return mst, total

print(kruskal(equips))
# ([('disseny', 'frontend', 1), ('backend', 'dades', 2), ('dades', 'qa', 3),
#   ('backend', 'frontend', 4)], 10)

Nota sobre la construcció d'arestes: com que el graf no dirigit desa cada aresta en tots dos sentits, tuple(sorted((u, v))) normalitza la parella i el set elimina el duplicat. Cost total de Kruskal: O(a · log a), dominat per l'ordenació.

Traça de Kruskal

Arestes ordenades: (disseny–frontend, 1), (backend–dades, 2), (dades–qa, 3), (backend–frontend, 4), (frontend–qa, 5), (disseny–qa, 6), (backend–qa, 7).

Aresta Extrems ja connectats? Decisió Conjunts després del pas
disseny–frontend (1) No Acceptar {disseny, frontend} {backend} {dades} {qa}
backend–dades (2) No Acceptar {disseny, frontend} {backend, dades} {qa}
dades–qa (3) No Acceptar {disseny, frontend} {backend, dades, qa}
backend–frontend (4) No Acceptar → 4 arestes: fi {tots}
frontend–qa (5) (no arriba a avaluar-se) — —

Mateix arbre i mateix total (10) que Prim — com ha de ser: quan els pesos no es repeteixen, el MST és únic. Observa la diferència d'estil: Prim manté un arbre que creix; Kruskal manté un bosc de fragments que es van fusionant (per això, en un graf no connex, Kruskal acaba amb un MST per illa sense canviar ni una línia).

Prim davant de Kruskal

Prim Kruskal
Estratègia Fer créixer un arbre des d'un vèrtex Acceptar arestes globalment barates
Estructura de suport heapq (mòdul 4) Ordenació + Union-Find
Cost O(a · log n) O(a · log a)
Còmode quan... Graf dens, llista d'adjacència Graf dispers, arestes ja com a llista
Graf no connex Només cobreix la component inicial Dóna el bosc complet gratis
S'assembla a Dijkstra (canvia la prioritat) Un filtre cobdiciós sobre arestes ordenades

Tots dos són algorismes cobdiciosos (greedy): prenen a cada pas l'opció localment més barata i, per a aquest problema —a diferència de tants altres—, això porta demostradament a l'òptim global.

Errors Comuns i Consells

  • Aplicar MST a un graf dirigit. El problema està definit per a no dirigits; construeix el graf amb Graf(dirigit=False) o els algorismes donaran resultats sense sentit.
  • Confondre MST amb camins mínims i fer servir l'arbre de Prim per respondre "ruta més barata d'A a B?". Repassa la taula de la secció 2: optimitzen coses diferents.
  • Oblidar el continue d'arestes obsoletes a Prim: acceptaries arestes cap a vèrtexs ja incorporats, creant cicles i sumant cost de més.
  • Implementar Union-Find sense compressió ni rang. Funciona, però els arbres interns degeneren en cadenes i trobar passa a O(n) — la mateixa degeneració que patia l'ABC sense equilibrar al mòdul 6.
  • Duplicar arestes a Kruskal en extreure-les d'un graf no dirigit (u–v i v–u): o normalitzes com vam fer, o l'algorisme ho avalua tot dues vegades (no trenca el resultat, però delata descuit).
  • Consell: Union-Find val molt més que Kruskal: connectivitat dinàmica, detecció de cicles al vol, agrupament... Als exercicis finals (07-07) l'alternativa BFS per a components connexes et farà apreciar quan brilla cadascuna.

Exercicis

Exercici 1: MST a mà

Afegeix un sisè equip: mobil, amb arestes mobil–frontend (2) i mobil–qa (4). Calcula el nou MST amb Kruskal a mà (taula de decisions) i el seu cost total.

Exercici 2: la marrada del MST

Al MST de la lliçó, quin és el camí entre disseny i qa i quant costa sumant les seves arestes? Compara'l amb l'aresta directa disseny–qa (6) i explica per què el MST "prefereix" la marrada.

Exercici 3: Union-Find com a detector de cicles

Fent servir només UnionFind (sense DFS), escriu te_cicle_no_dirigit(arestes, vertexs) que detecti si un graf no dirigit donat com a llista d'arestes conté algun cicle. Pista: què significa que unir retorni False?

Solucions

Solució 1: Arestes ordenades: 1 (disseny–frontend), 2 (backend–dades), 2 (mobil–frontend), 3 (dades–qa), 4 (backend–frontend), 4 (mobil–qa), 5, 6, 7. Decisions: acceptar 1, 2, 2, 3, 4 (backend–frontend uneix {disseny, frontend, mobil} amb {backend, dades, qa}); amb 5 arestes per a 6 vèrtexs, fi. mobil–qa (4) ja no s'avalua (connectats via frontend...backend...qa). Total: 1 + 2 + 2 + 3 + 4 = 12.

Solució 2: Al MST, de disseny a qa s'hi va per disseny–frontend–backend–dades–qa: 1 + 4 + 2 + 3 = 10, davant de 6 de l'aresta directa. El MST va descartar disseny–qa perquè quan li va arribar el torn els seus extrems ja estaven connectats: per a la factura total de la xarxa aquella aresta era redundant. És la demostració pràctica de l'advertiment de la secció 2: el MST no promet bons trajectes individuals, només la xarxa completa més barata.

Solució 3:

def te_cicle_no_dirigit(arestes, vertexs):
    uf = UnionFind(vertexs)
    for u, v in arestes:
        if not uf.unir(u, v):    # ja connectats: aquesta aresta tanca un cicle
            return True
    return False

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

Si unir retorna False, els extrems ja compartien conjunt: hi havia un camí entre ells i la nova aresta el tanca en cicle. És la tercera tècnica de detecció de cicles del curs (Floyd en llistes, blanc/gris/negre en dirigits, Union-Find en no dirigits), cadascuna al seu terreny.

Conclusió

El MST respon una pregunta diferent de la dels camins mínims —minimitzar la xarxa total, no cada trajecte— i només viu en grafs no dirigits. Prim el construeix com una taca d'oli amb el heapq de sempre (una línia el separa de Dijkstra); Kruskal ordena les arestes i filtra cicles amb Union-Find, la nova estructura auxiliar que amb compressió de camins i unió per rang respon "estan connectats?" en temps gairebé constant. Amb això ja és completa la caixa d'eines del mòdul: recorreguts, cicles, ordres, camins i xarxes. La propera lliçó no afegeix cap algorisme més: els posa tots a treballar junts — el planificador complet de TaskFlow (ordre, cicles, paral·lelisme i ruta crítica), suggeriments de col·laboradors a l'estil xarxa social i fins i tot un PageRank en miniatura.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2026. Tots els drets reservats