El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència

HOME

Ja tenim la xarxa urbana de Rutalia en memòria com a llista d'adjacència. La pregunta natural és: com es recorre? Gairebé tot el que farem amb grafs en aquest mòdul —camins mínims, flux, aparellaments— es recolza en dues formes fonamentals d'exploració: la cerca en amplada (BFS), que avança per capes com una ona expansiva, i la cerca en profunditat (DFS), que s'endinsa per un camí fins a esgotar-lo abans de recular. Amb només aquestes dues eines respondrem preguntes operatives reals de Rutalia: a quants trams és el punt de lliurament més llunyà, quines zones queden incomunicades si unes obres tallen un carrer, i en quin ordre s'han d'executar les tasques del magatzem.

Contingut

BFS: exploració per nivells amb una cua
Distàncies en arestes i reconstrucció del camí amb pare
DFS: recursiu i iteratiu
Taula comparativa BFS vs DFS
Detecció de cicles
Components connexes: BFS davant de l'union-find de 01-04
Ordenació topològica en DAGs: l'algorisme de Kahn
Aplicacions a Rutalia: talls de carrer i excentricitat

BFS: exploració per nivells amb una cua

BFS parteix d'un node origen i visita primer tots els seus veïns (nivell 1), després els veïns d'aquests (nivell 2), i així successivament. L'estructura que imposa aquest ordre és una cua FIFO: els nodes es processen en el mateix ordre en què es descobreixen.

from collections import deque

# Graf canonic de Rutalia (03-01): {node: {vei: minuts}}
XARXA = {
    "ALM": {"RIO": 3, "MER": 4, "EST": 7, "CEN": 12},
    "MER": {"ALM": 4, "CEN": 5, "UNI": 6},
    "EST": {"ALM": 7, "UNI": 3, "IND": 9},
    "UNI": {"MER": 6, "EST": 3, "CEN": 8, "HOS": 5},
    "RIO": {"ALM": 3, "CEN": 6, "PAR": 8},
    "CEN": {"ALM": 12, "MER": 5, "UNI": 8, "RIO": 6, "HOS": 4},
    "IND": {"EST": 9, "HOS": 6},
    "HOS": {"UNI": 5, "CEN": 4, "IND": 6, "PAR": 7},
    "PAR": {"RIO": 8, "HOS": 7},
}

def bfs(graf, origen):
    """Retorna (dist, pare): distancia en ARESTES des de l'origen i arbre de pares."""
    dist = {origen: 0}
    pare = {origen: None}
    cua = deque([origen])
    while cua:
        u = cua.popleft()               # FIFO: surt el mes antic
        for v in graf[u]:
            if v not in dist:           # encara no descobert
                dist[v] = dist[u] + 1   # es una capa mes lluny que u
                pare[v] = u
                cua.append(v)
        # els pesos (minuts) s'IGNOREN expressament: BFS compta trams
    return dist, pare

dist, pare = bfs(XARXA, "ALM")
print(dist)
# {'ALM': 0, 'RIO': 1, 'MER': 1, 'EST': 1, 'CEN': 1,
#  'PAR': 2, 'UNI': 2, 'IND': 2, 'HOS': 2}

Claus del codi:

Marquem un node com a descobert en encuar-lo, no en desencuar-lo. Si es marqués tard, un mateix node podria entrar diverses vegades a la cua.
dist[v] = dist[u] + 1 funciona perquè la cua processa els nivells en ordre: quan traiem u, tots els nodes a distància menor ja han sortit. Aquesta és la garantia central de BFS: en grafs sense pesos (o amb totes les arestes iguals), dist[v] és la longitud del camí més curt en nombre d'arestes.
Complexitat: cada node entra i surt de la cua una vegada, i cada aresta s'examina dues vegades (una per extrem): O(n + m) amb llista d'adjacència. Amb matriu seria O(n²), una altra raó per a l'elecció de 03-01.

Lectura operativa immediata: des del Magatzem, tota la ciutat és com a molt a 2 trams. L'excentricitat d'ALM és 2. Però compte: "2 trams" no vol dir "poc temps" — ho veurem al final.

Distàncies en arestes i reconstrucció del camí amb `pare`

pare guarda, per a cada node, des de quin node va ser descobert. Aquest diccionari defineix un arbre BFS arrelat a l'origen, i permet reconstruir el camí més curt caminant enrere — la mateixa tècnica de reconstrucció que vam usar a la PD de 01-03:

def reconstruir(pare, desti):
    cami = []
    while desti is not None:
        cami.append(desti)
        desti = pare[desti]        # reculem un pas cap a l'origen
    return cami[::-1]              # estava del reves

print(reconstruir(pare, "HOS"))    # ['ALM', 'CEN', 'HOS']

BFS proposa anar a l'Hospital per l'avinguda directa: ALM→CEN→HOS, 2 trams. En minuts són 12 + 4 = 16. Tanmateix, ALM→MER→CEN→HOS són 3 trams però 4 + 5 + 4 = 13 minuts. BFS optimitza trams, no minuts: quan els pesos importen, cal una altra cosa (03-03). Guarda't aquest exemple: és la motivació exacta de Dijkstra.

DFS: recursiu i iteratiu

DFS explora "cap endins": des d'un node tria un veí, des d'aquest un altre, i només quan no pot avançar més recula (backtracking — literalment el mateix esquema explorar/desfer de 02-03, aplicat a grafs).

Versió recursiva, la més natural:

def dfs_recursiu(graf, u, visitats=None, ordre=None):
    if visitats is None:
        visitats, ordre = set(), []
    visitats.add(u)
    ordre.append(u)                      # moment de DESCOBRIMENT
    for v in graf[u]:
        if v not in visitats:
            dfs_recursiu(graf, v, visitats, ordre)
    return ordre

print(dfs_recursiu(XARXA, "ALM"))
# ['ALM', 'RIO', 'CEN', 'MER', 'UNI', 'EST', 'IND', 'HOS', 'PAR']

Segueix el rastre: d'ALM baixa a RIO, de RIO a CEN, de CEN a MER, de MER a UNI, d'UNI a EST, d'EST a IND, d'IND a HOS, d'HOS a PAR. Un sol fil que s'enfonsa fins al fons; els retrocessos (per exemple, de PAR de tornada fins a ALM) no visiten res de nou.

Versió iterativa amb pila explícita (LIFO), imprescindible en grafs grans on la recursió desbordaria (el límit per defecte de Python volta les 1.000 crides imbricades):

def dfs_iteratiu(graf, origen):
    visitats, ordre = set(), []
    pila = [origen]
    while pila:
        u = pila.pop()                   # LIFO: surt el mes recent
        if u in visitats:
            continue                     # pot haver entrat diverses vegades a la pila
        visitats.add(u)
        ordre.append(u)
        # reversed() per imitar l'ordre de la versio recursiva
        for v in reversed(list(graf[u])):
            if v not in visitats:
                pila.append(v)
    return ordre

Diferències subtils que convé interioritzar:

L'única diferència estructural amb BFS és cua → pila. Aquest canvi d'estructura transforma l'ona expansiva en un descens en profunditat. (Avançament: a 03-03, canviar la pila per un heap donarà Dijkstra. Tota aquesta família d'algorismes és "la mateixa plantilla amb agenda diferent".)
En la versió iterativa, un node pot ser diverses vegades a la pila; per això es comprova visitats en treure'l, no en posar-lo.
DFS no calcula distàncies mínimes: l'ordre de descobriment depèn de l'ordre dels veïns i pot arribar a un node per un camí llarguíssim.

Taula comparativa BFS vs DFS

	BFS	DFS
Estructura	Cua (FIFO)	Pila (LIFO) o recursió
Ordre de visita	Per nivells (proximitat)	En profunditat (un fil fins al fons)
Complexitat	O(n + m)	O(n + m)
Memòria en el pitjor cas	O(n) (frontera ampla)	O(n) (camí profund)
Camí més curt sense pesos	Sí (en arestes)	No
Detecció de cicles	Sí	Sí (la formulació més còmoda en dirigits)
Components connexes	Sí	Sí
Ordenació topològica	Kahn (variant BFS)	Ordre de finalització invertit
Usos típics a Rutalia	Distàncies en trams, zones abastables, capes de servei	Dependències de tasques, detecció de cicles, backtracking

Detecció de cicles

En grafs no dirigits: hi ha cicle si durant la cerca trobem un veí ja visitat que no és el pare del node actual (el pare no compta: l'aresta d'anada i tornada no és un cicle).

def te_cicle_no_dirigit(graf):
    visitats = set()
    def dfs(u, pare):
        visitats.add(u)
        for v in graf[u]:
            if v not in visitats:
                if dfs(v, u):
                    return True
            elif v != pare:       # visitat i no es d'on venim: cicle
                return True
        return False
    return any(u not in visitats and dfs(u, None) for u in graf)

print(te_cicle_no_dirigit(XARXA))   # True (p. ex. ALM-MER-CEN-ALM)

En grafs dirigits no n'hi ha prou amb "visitat abans": cal distingir si el node segueix al camí actual. S'usen tres estats: blanc (sense visitar), gris (en curs, encara a la pila de recursió) i negre (acabat). Trobar un veí gris delata un cicle dirigit:

def te_cicle_dirigit(graf):
    BLANC, GRIS, NEGRE = 0, 1, 2
    color = {u: BLANC for u in graf}
    def dfs(u):
        color[u] = GRIS
        for v in graf[u]:
            if color[v] == GRIS:              # aresta cap al cami actual
                return True
            if color[v] == BLANC and dfs(v):
                return True
        color[u] = NEGRE
        return False
    return any(color[u] == BLANC and dfs(u) for u in graf)

Això importa a Rutalia: si el pla de tasques del magatzem tingués un cicle de dependències ("carregar requereix etiquetar, etiquetar requereix carregar"), cap ordre de treball no seria vàlid. Verificar que el graf és un DAG és el pas previ a ordenar-lo.

Components connexes: BFS davant de l'union-find de 01-04

Escenari Rutalia: unes obres tallen simultàniament els trams EST–IND i HOS–IND. Queda alguna zona sense servei? N'hi ha prou de llançar BFS des de cada node encara no visitat; cada llançament descobreix una component completa:

def components(graf):
    visitats, comps = set(), []
    for inici in graf:
        if inici in visitats:
            continue
        comp, cua = set(), deque([inici])
        visitats.add(inici)
        while cua:
            u = cua.popleft()
            comp.add(u)
            for v in graf[u]:
                if v not in visitats:
                    visitats.add(v)
                    cua.append(v)
        comps.append(comp)
    return comps

retallada = {u: {v: p for v, p in vs.items()
                 if {u, v} not in [{"EST", "IND"}, {"HOS", "IND"}]}
             for u, vs in XARXA.items()}
print(components(retallada))
# [{'ALM','RIO','MER','EST','UNI','CEN','HOS','PAR'}, {'IND'}]

El Polígon Industrial queda aïllat — coherent amb el que vam anticipar a 03-01: amb grau 2, era la zona més fràgil.

I l'union-find de 01-04? Resol el mateix: es recorre la llista d'arestes fent union(u, v), i dues zones són a la mateixa component si find retorna el mateix representant. Comparació honesta:

	BFS/DFS	Union-find
Cost	O(n + m) una vegada	O(m · α(n)) ≈ lineal
Graf estàtic	Ideal	Correcte però sense avantatge
Arestes que s'afegeixen en viu	Cal rellançar la cerca	Ideal: actualització O(α(n)) per aresta
Arestes que s'eliminen	Rellançar	També necessita reconstruir
Extres	Dona camins, distàncies, arbre	Només pertinença a component

Regla pràctica: per a una foto fixa, BFS; per a un graf que creix aresta a aresta (exactament el que farà Kruskal a 03-04), union-find.

Ordenació topològica en DAGs: l'algorisme de Kahn

El magatzem de Rutalia prepara cada furgoneta amb tasques encadenades: no es pot classificar el que no està escanejat ni carregar el que no té ruta assignada. Modelem cada dependència com una aresta dirigida "abans → després":

graph LR
    recepcio --> escaneig
    escaneig --> classificacio
    escaneig --> etiquetatge
    classificacio --> assignacio_ruta
    etiquetatge --> carrega
    assignacio_ruta --> carrega
    carrega --> sortida

Una ordenació topològica és una llista dels nodes on tota aresta apunta cap endavant: un ordre d'execució vàlid. Només existeix si el graf és un DAG. L'algorisme de Kahn és BFS amb una idea extra: només pot començar una tasca el grau d'entrada pendent de la qual sigui 0.

from collections import deque

def kahn(graf):
    entrada = {u: 0 for u in graf}
    for u in graf:
        for v in graf[u]:
            entrada[v] += 1

    cua = deque(u for u in graf if entrada[u] == 0)  # tasques llestes d'entrada
    ordre = []
    while cua:
        u = cua.popleft()
        ordre.append(u)
        for v in graf[u]:
            entrada[v] -= 1          # u ja no bloqueja v
            if entrada[v] == 0:
                cua.append(v)        # v queda desbloquejada

    if len(ordre) < len(graf):       # han quedat nodes bloquejats entre si
        raise ValueError("Hi ha un cicle de dependències: no existeix cap ordre vàlid")
    return ordre

TASQUES = {
    "recepcio": ["escaneig"],
    "escaneig": ["classificacio", "etiquetatge"],
    "classificacio": ["assignacio_ruta"],
    "etiquetatge": ["carrega"],
    "assignacio_ruta": ["carrega"],
    "carrega": ["sortida"],
    "sortida": [],
}
print(kahn(TASQUES))
# ['recepcio', 'escaneig', 'classificacio', 'etiquetatge',
#  'assignacio_ruta', 'carrega', 'sortida']

Dos detalls valuosos:

L'ordre no és únic (classificacio i etiquetatge són intercanviables: són tasques paral·lelitzables — informació útil en si mateixa per al cap de magatzem).
Kahn detecta cicles de franc: si en acabar ordre no conté tots els nodes, els que falten formen part d'un cicle (o en depenen). És la versió "constructiva" del detector de cicles gris/negre.

Aplicacions a Rutalia: talls de carrer i excentricitat

Recapitulem les dues preguntes operatives promeses, ja amb resposta:

Quines zones queden abastables si es talla un carrer? Eliminar les arestes afectades i rellançar BFS des d'ALM: els nodes sense distància assignada estan incomunicats. Amb el tall doble sobre IND hem vist que el Polígon queda aïllat; un tall simple (per exemple només EST–IND) no aïlla res perquè IND conserva la sortida per HOS. Aquesta anàlisi de robustesa, sistematitzada sobre grafs gegants, reapareixerà a 06-02.
A quants trams és el punt de lliurament més llunyà? max(dist.values()) després de BFS des d'ALM: 2 trams (UNI, IND, PAR i HOS empaten). És l'excentricitat del magatzem: útil per dimensionar "salts" logístics, però enganyosa com a mesura de temps — HOS és a 2 trams i 16 minuts per aquell camí, quan n'existeix un de 13.

Aquesta esquerda —trams ≠ minuts— és exactament el que obre la porta de la lliçó següent.

Errors Comuns i Consells

Marcar visitat en desencuar a BFS: permet que un node entri a la cua moltes vegades i, pitjor, pot assignar-li una distància incorrecta. A BFS es marca en encuar; a DFS iteratiu, en canvi, el còmode és comprovar en treure. No barregis els dos patrons sense pensar.
Usar list.pop(0) com a cua: desplaça tota la llista i converteix BFS en O(n·m). Fes servir collections.deque amb popleft(), que és O(1).
Creure que BFS dona el camí més ràpid en minuts: dona el mínim en arestes. L'exemple ALM→HOS (2 trams/16 min davant de 3 trams/13 min) t'hauria de vacunar per sempre.
Recursió sense límit a DFS: un graf-camí de 10.000 nodes rebenta la pila de Python. Per a producció, versió iterativa o sys.setrecursionlimit amb molta cura.
Detectar cicles en dirigits amb un simple visitats: dos camins diferents cap al mateix node no són un cicle. En dirigits calen els tres colors (o Kahn).
Consell: quan depuris una cerca, imprimeix la cua/pila a cada iteració amb un graf de 5 nodes. El "vídeo mental" de com avança la frontera val més que qualsevol definició.

Exercicis

Zones per capes de servei. Rutalia vol agrupar les zones per "anells" de proximitat al magatzem: anell 0 = ALM, anell 1 = a un tram, etc. Escriu anells(graf, origen) que retorni una llista de conjunts, un per nivell BFS, i aplica-la a la xarxa canònica.
Tall crític? Escriu es_critica(graf, u, v) que indiqui si eliminar l'aresta {u, v} desconnecta el graf (pista: treu-la i compara el nombre de components). Troba totes les arestes crítiques (ponts) de la xarxa canònica provant-les una a una. El resultat encaixa amb els graus que vas calcular a 03-01?
Pla de magatzem amb imprevist. Afegeix al DAG de tasques la dependència sortida → recepcio (un error de configuració) i comprova que kahn llança l'excepció. Després, escriu una variant kahn_parallel(graf) que retorni les tasques agrupades per "onades" executables en paral·lel (totes les desbloquejades alhora formen una onada).

Solucions

Exercici 1:

def anells(graf, origen):
    dist, _ = bfs(graf, origen)
    nivells = [set() for _ in range(max(dist.values()) + 1)]
    for node, d in dist.items():
        nivells[d].add(node)
    return nivells

print(anells(XARXA, "ALM"))
# [{'ALM'}, {'RIO', 'MER', 'EST', 'CEN'}, {'PAR', 'UNI', 'IND', 'HOS'}]

Reutilitzem bfs i només reagrupem per distància: els anells són les capes de l'ona expansiva.

Exercici 2:

def sense_aresta(graf, u, v):
    return {a: {b: p for b, p in vs.items() if {a, b} != {u, v}}
            for a, vs in graf.items()}

def es_critica(graf, u, v):
    return len(components(sense_aresta(graf, u, v))) > len(components(graf))

critiques = [(u, v) for u in XARXA for v in XARXA[u] if u < v and es_critica(XARXA, u, v)]
print(critiques)   # [] -> cap aresta aillada no desconnecta la xarxa

La xarxa canònica no té ponts: tota zona té almenys dues sortides, així que cap tall simple no aïlla res (coherent amb l'exercici del tall doble sobre IND, que va necessitar dues arestes). El filtre u < v evita examinar cada aresta dues vegades.

Exercici 3:

TASQUES_MAL = dict(TASQUES, sortida=["recepcio"])
try:
    kahn(TASQUES_MAL)
except ValueError as e:
    print(e)   # Hi ha un cicle de dependencies: no existeix cap ordre valid

def kahn_parallel(graf):
    entrada = {u: 0 for u in graf}
    for u in graf:
        for v in graf[u]:
            entrada[v] += 1
    llestos = [u for u in graf if entrada[u] == 0]
    onades = []
    while llestos:
        onades.append(llestos)
        seguents = []
        for u in llestos:
            for v in graf[u]:
                entrada[v] -= 1
                if entrada[v] == 0:
                    seguents.append(v)
        llestos = seguents
    return onades

print(kahn_parallel(TASQUES))
# [['recepcio'], ['escaneig'], ['classificacio', 'etiquetatge'],
#  ['assignacio_ruta'], ['carrega'], ['sortida']]

En lloc d'una cua node a node, processem generacions completes: cada onada conté tasques sense dependències mútues, executables en paral·lel. Fixa't que etiquetatge ha d'esperar assignacio_ruta... no: només espera escaneig; qui espera totes dues branques és carrega. El DAG fa visible el paral·lelisme real del magatzem.

Conclusió

BFS i DFS són la mateixa plantilla amb agenda diferent: una cua produeix una ona per nivells que dona distàncies mínimes en arestes i camins reconstruïbles amb pare; una pila produeix un descens en profunditat ideal per a cicles, dependències i backtracking. Amb elles hem detectat cicles (amb tres colors en dirigits), calculat components connexes (i delimitat quan convé l'union-find de 01-04), ordenat topològicament les tasques del magatzem amb Kahn i respost als talls de carrer de Rutalia. Però la lliçó deixa una espina clavada: BFS jura que l'Hospital és "a 2 trams" per una avinguda de 16 minuts, quan hi ha un camí de 13. Comptar arestes no basta quan les arestes pesen. A 03-03 substituirem la cua pel heap que vam deixar sembrat a 01-04 —és hora de collir aquella llavor— i obtindrem Dijkstra, l'algorisme de camins mínims per excel·lència, al costat de Bellman-Ford i Floyd-Warshall.

Cerca en Grafs: BFS i DFS

Contingut

BFS: exploració per nivells amb una cua

Distàncies en arestes i reconstrucció del camí amb `pare`

DFS: recursiu i iteratiu

Taula comparativa BFS vs DFS

Detecció de cicles

Components connexes: BFS davant de l'union-find de 01-04

Ordenació topològica en DAGs: l'algorisme de Kahn

Aplicacions a Rutalia: talls de carrer i excentricitat

Errors Comuns i Consells

Exercicis

Solucions

Conclusió

Algorismes Avançats

Mòdul 1: Introducció als Algorismes Avançats

Mòdul 2: Algorismes d'Optimització

Mòdul 3: Algorismes en Grafs

Mòdul 4: Algorismes de Cerca i Ordenació

Mòdul 5: Algorismes d'Aprenentatge Automàtic

Mòdul 6: Casos d'Estudi i Aplicacions

Mòdul 7: Projecte Final

Cerca en Grafs: BFS i DFS

Contingut

BFS: exploració per nivells amb una cua

Distàncies en arestes i reconstrucció del camí amb pare

DFS: recursiu i iteratiu

Taula comparativa BFS vs DFS

Detecció de cicles

Components connexes: BFS davant de l'union-find de 01-04

Ordenació topològica en DAGs: l'algorisme de Kahn

Aplicacions a Rutalia: talls de carrer i excentricitat

Errors Comuns i Consells

Exercicis

Solucions

Conclusió

Algorismes Avançats

Mòdul 1: Introducció als Algorismes Avançats

Mòdul 2: Algorismes d'Optimització

Mòdul 3: Algorismes en Grafs

Mòdul 4: Algorismes de Cerca i Ordenació

Mòdul 5: Algorismes d'Aprenentatge Automàtic

Mòdul 6: Casos d'Estudi i Aplicacions

Mòdul 7: Projecte Final

Distàncies en arestes i reconstrucció del camí amb `pare`