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

HOME

Aquesta és la lliçó on el curs cobra tots els seus deutes. Al mòdul 5 vam prometre que el patró "ja ho he vist?" amb set seria el visitats de BFS; al mòdul 6 vam dir que el recorregut per nivells amb deque "és un BFS que saltarà a grafs"; i des del mòdul 3 sabem que tota recursió amaga una pila. Aquí convergeixen les tres peces: BFS (cerca en amplada) i DFS (cerca en profunditat), els dos recorreguts fonamentals sobre grafs. Amb ells respondrem preguntes reals de TaskFlow: quines tasques es desbloquegen en acabar-ne una, si el projecte té cicles de dependències, i en quin ordre executar les tasques. Treballem sobre la classe Graf i el graf dependencies de la lliçó anterior.

Contingut

Per què visitats ara és imprescindible
BFS: cerca en amplada amb deque
Traça de BFS sobre el graf de dependències
DFS: cerca en profunditat, recursiva i iterativa
Traça de DFS i comparació BFS/DFS
Aplicació 1: què desbloqueja acabar una tasca? (abastables)
Aplicació 2: detecció de cicles amb estats blanc/gris/negre
Aplicació 3: ordre topològic (algorisme de Kahn)
Components connexes

Per què `visitats` ara és imprescindible

Al recorregut per nivells d'un arbre (mòdul 6) no portàvem cap conjunt de visitats. No calia: en un arbre cada node té un sol pare, així que només s'hi pot arribar per un camí i és impossible encuar-lo dues vegades. Els grafs trenquen aquesta garantia dues vegades:

Diversos pares: a desplegar_api s'hi arriba des de migrar_bd i des de configurar_servidor. Sense control, la processaríem dues vegades (i tot el que hi ha darrere, quatre; creixement exponencial).
Cicles: a A → B → C → A, un recorregut ingenu no acaba mai.

La solució és el patró del mòdul 5: un set anomenat visitats amb pertinença i inserció en O(1) mitjà. Regla d'or: marcar en encuar/apilar, no en desencuar — si esperes a marcar quan processes el vèrtex, pot colar-se dues vegades a la cua entremig.

BFS: cerca en amplada amb `deque`

BFS explora el graf per capes de distància: primer l'origen (distància 0), després els seus veïns (distància 1), després els veïns d'aquests (distància 2)... És literalment el recorregut per nivells del mòdul 6, amb deque com a cua (append per la dreta, popleft per l'esquerra, tots dos O(1), mòdul 4), més el visitats:

from collections import deque

def bfs(graf, origen):
    """Recorre el graf des d'origen per capes. Retorna l'ordre de visita."""
    visitats = {origen}           # marcat JA, abans d'entrar a la cua
    cua = deque([origen])
    ordre = []
    while cua:
        actual = cua.popleft()    # FIFO: surt el més antic -> per capes
        ordre.append(actual)
        for vei in graf.veins(actual):
            if vei not in visitats:       # el "ja ho he vist?" del mòdul 5
                visitats.add(vei)         # marcar en encuar
                cua.append(vei)
    return ordre

Cada vèrtex entra a la cua com a molt una vegada i cada aresta s'examina una vegada: cost O(n + a) en temps i O(n) en espai. Compara-ho amb l'arbre del mòdul 6: el codi és gairebé idèntic; només hi hem afegit tres línies de visitats. Aquesta és la continuïtat promesa.

La propietat estrella de BFS: com que avança per capes, la primera vegada que arriba a un vèrtex ho fa per un camí amb el mínim nombre d'arestes. En grafs no ponderats, BFS és l'algorisme de camí més curt (amb pesos ja no n'hi haurà prou: lliçó 07-04).

Traça de BFS sobre el graf de dependències

Executem bfs(dependencies, "dissenyar_esquema") pas a pas:

graph LR
    A[dissenyar_esquema] --> B[migrar_bd]
    B --> C[desplegar_api]
    S[configurar_servidor] --> C
    C --> D[proves_integracio]
    U[dissenyar_ui] --> I[implementar_ui]
    I --> D
    D --> L[llancament]

Pas	Surt de la cua	Veïns nous que entren	Cua després del pas	Visitats
1	dissenyar_esquema	migrar_bd	[migrar_bd]	{d_e, mig}
2	migrar_bd	desplegar_api	[desplegar_api]	+ api
3	desplegar_api	proves_integracio	[proves_integracio]	+ pro
4	proves_integracio	llancament	[llancament]	+ lla
5	llancament	—	[]	—

Resultat: ['dissenyar_esquema', 'migrar_bd', 'desplegar_api', 'proves_integracio', 'llancament']. Dues observacions:

BFS només visita allò abastable seguint les fletxes: ni configurar_servidor, ni dissenyar_ui, ni implementar_ui no hi apareixen, perquè cap fletxa no porta de dissenyar_esquema fins a elles. En un graf dirigit, "abastable" depèn de l'origen.
Les capes són les distàncies: migrar_bd a 1 aresta, desplegar_api a 2, etc.

DFS: cerca en profunditat, recursiva i iterativa

DFS pren la decisió contrària: en lloc d'esgotar la capa actual, es llança per un camí fins al fons i només retrocedeix (backtracking) quan no pot continuar. Versió recursiva, on la "pila" és la pila de crides del mòdul 3:

def dfs_recursiu(graf, origen, visitats=None, ordre=None):
    if visitats is None:
        visitats, ordre = set(), []
    visitats.add(origen)
    ordre.append(origen)
    for vei in graf.veins(origen):
        if vei not in visitats:
            dfs_recursiu(graf, vei, visitats, ordre)  # baixar un nivell
    return ordre

I la versió iterativa, aplicant l'equivalència recursió ↔ pila explícita del mòdul 3 (útil quan el graf és profund i la pila de crides de Python, limitada a ~1000 nivells, es queda curta):

def dfs_iteratiu(graf, origen):
    visitats = set()
    pila = [origen]               # una list com a pila: append/pop pel final
    ordre = []
    while pila:
        actual = pila.pop()       # LIFO: surt el més RECENT -> profunditat
        if actual in visitats:    # pot haver entrat dues vegades abans de sortir
            continue
        visitats.add(actual)
        ordre.append(actual)
        for vei in graf.veins(actual):
            if vei not in visitats:
                pila.append(vei)
    return ordre

Compara dfs_iteratiu amb bfs: són el mateix algorisme canviant l'estructura de suport. Cua (FIFO) → amplada; pila (LIFO) → profunditat. És la simetria pila↔DFS / cua↔BFS anunciada al mòdul 6, ara en codi real.

Traça de DFS i comparació BFS/DFS

dfs_recursiu(dependencies, "dissenyar_ui"): visita dissenyar_ui, baixa a implementar_ui, baixa a proves_integracio, baixa a llancament; sense veïns nous, desfà crides fins a l'origen. Resultat: ['dissenyar_ui', 'implementar_ui', 'proves_integracio', 'llancament'] — un camí en picat, davant de l'avanç per capes de BFS.

Criteri	BFS	DFS
Estructura de suport	Cua (`deque`, mòdul 4)	Pila (crides o `list`, mòdul 3)
Ordre d'exploració	Per capes de distància	Un camí fins al fons, després retrocedeix
Troba	El camí amb menys arestes	Exploració exhaustiva; camins, no necessàriament curts
Memòria en el pitjor cas	`O(n)` (una capa ampla)	`O(n)` (un camí llarg)
Cost en temps	`O(n + a)`	`O(n + a)`
Usos típics	Distàncies, "a N passos de", nivells	Cicles, ordre topològic, backtracking

Aplicació 1: què desbloqueja acabar una tasca? (abastables)

Pregunta de TaskFlow: "si acabo migrar_bd, quines tasques s'acosten al seu desbloqueig?" Amb la nostra convenció (la fletxa apunta al que es desbloqueja), són exactament els vèrtexs abastables des d'ella — BFS i treure l'origen:

def tasques_afectades(graf, id_tasca):
    """Tasques que depenen, directament o transitivament, d'id_tasca."""
    return bfs(graf, id_tasca)[1:]      # tot l'abastable, menys ella mateixa

print(tasques_afectades(dependencies, "migrar_bd"))
# ['desplegar_api', 'proves_integracio', 'llancament']

Endarrerir migrar_bd endarrereix potencialment aquestes tres tasques: acabem d'implementar l'anàlisi d'impacte d'un gestor de projectes en cinc línies.

Aplicació 2: detecció de cicles amb estats blanc/gris/negre

Al mòdul 2 vam detectar cicles en llistes enllaçades amb Floyd (dos punters a diferent velocitat). Aquella tècnica servia perquè en una llista només hi ha un camí possible; en un graf amb bifurcacions necessitem una altra idea, però el problema és el mateix: puc tornar a un lloc on ja sóc? La tècnica clàssica fa servir DFS amb tres estats per vèrtex:

Blanc: encara no visitat.
Gris: en procés — és al camí actual de la recursió (a la pila de crides).
Negre: acabat — ell i tots els seus descendents, explorats.

La clau: si DFS troba una aresta cap a un vèrtex gris, ha trobat una aresta que torna al camí actual: un cicle. Arribar a un de negre no és cicle, només un encreuament de camins (diversos pares).

def hi_ha_cicle(graf):
    BLANC, GRIS, NEGRE = 0, 1, 2
    color = {v: BLANC for v in graf.vertexs()}

    def visitar(v):
        color[v] = GRIS
        for vei in graf.veins(v):
            if color[vei] == GRIS:         # aresta cap al camí actual
                return True
            if color[vei] == BLANC and visitar(vei):
                return True
        color[v] = NEGRE                   # v tancat: res sota seu forma cicle
        return False

    # el graf pot no ser connex: cal intentar-ho des de cada vèrtex blanc
    return any(color[v] == BLANC and visitar(v) for v in graf.vertexs())

print(hi_ha_cicle(dependencies))    # False: el nostre projecte és un DAG

# Trenquem-lo a propòsit: "dissenyar_ui depèn de proves_integracio"
dependencies.afegir_aresta("proves_integracio", "dissenyar_ui")
print(hi_ha_cicle(dependencies))    # True
dependencies.eliminar_aresta("proves_integracio", "dissenyar_ui")  # ex. 2 de 07-02

Això és exactament el que TaskFlow ha d'executar abans d'acceptar una nova dependència: si en afegir-la hi_ha_cicle retorna True, es rebutja i s'avisa l'usuari. Als exercicis de la 07-07 anirem més lluny: no només detectar el cicle, sinó llistar-lo per mostrar-l'hi.

Aplicació 3: ordre topològic (algorisme de Kahn)

La gran pregunta del projecte: en quin ordre executo les tasques de manera que cap no comenci abans que les seves dependències? Aquest ordre s'anomena ordre topològic i només existeix en DAGs. L'algorisme de Kahn el construeix amb dues peces que ja tenim: els graus_entrada() de la 07-02 i una cua:

Calcula el grau d'entrada de cada vèrtex.
Posa a la cua els de grau 0 (executables ja).
Treu-ne un, afegeix-lo a l'ordre i "acaba'l": resta 1 al grau de cada veí. Si algun arriba a 0, cap a la cua.
Repeteix fins a buidar la cua.

def ordre_topologic(graf):
    graus = graf.graus_entrada()
    cua = deque(v for v, g in graus.items() if g == 0)
    ordre = []
    while cua:
        actual = cua.popleft()
        ordre.append(actual)
        for vei in graf.veins(actual):
            graus[vei] -= 1            # una dependència menys
            if graus[vei] == 0:        # totes complertes: executable
                cua.append(vei)
    if len(ordre) < len(graus):        # han quedat vèrtexs amb grau > 0
        raise ValueError("Hi ha un cicle de dependències: no existeix cap ordre vàlid")
    return ordre

print(ordre_topologic(dependencies))
# ['dissenyar_esquema', 'configurar_servidor', 'dissenyar_ui', 'migrar_bd',
#  'implementar_ui', 'desplegar_api', 'proves_integracio', 'llancament']

Detalls importants:

Aquí no hi ha visitats: el mateix comptador de graus en fa el paper — un vèrtex només entra a la cua quan el seu grau arriba exactament a 0, i això passa una sola vegada.
La comprovació final regala una segona detecció de cicles: si hi ha cicle, els seus vèrtexs mai no baixen a grau 0 i l'ordre surt incomplet. Kahn detecta cicles "de propina", sense colors.
L'ordre no és únic (els tres graus-0 inicials podien sortir en qualsevol ordre). A la 07-07 desempatarem per prioritat substituint la deque pel heapq del mòdul 4.
Cost: O(n + a), com tot el d'avui.

Components connexes

Última eina: detectar les "illes" del graf. Per fer-ho ignorem el sentit de les fletxes (dues tasques estan relacionades si comparteixen dependències en qualsevol direcció) i llancem BFS des de cada vèrtex encara sense visitar; cada llançament descobreix una component sencera:

def components_connexes(graf):
    # versió no dirigida del graf: cada aresta, en tots dos sentits
    nd = Graf(dirigit=False)
    for v in graf.vertexs():
        nd.afegir_vertex(v)
        for desti in graf.veins(v):
            nd.afegir_aresta(v, desti)

    visitats, components = set(), []
    for v in nd.vertexs():
        if v not in visitats:
            comp = bfs(nd, v)              # descobreix tota l'illa de v
            visitats.update(comp)
            components.append(comp)
    return components

dependencies.afegir_aresta("escriure_blog", "publicar_blog")  # mini-projecte a part
print(len(components_connexes(dependencies)))   # 2: el projecte principal i el blog

A TaskFlow, cada component és un subprojecte independent: es pot planificar, assignar i executar sense mirar les altres. Hi tornarem als exercicis (07-07) amb "illes de tasques".

Errors Comuns i Consells

Marcar com a visitat en desencuar en lloc de en encuar. L'algorisme acaba igual, però un mateix vèrtex pot entrar diverses vegades a la cua i el cost es dispara. En BFS, marca en encuar; en DFS iteratiu, el continue després del pop cobreix el cas equivalent.
Fer servir una list com a cua en BFS (pop(0)): és O(n) per extracció, com vam insistir al mòdul 4. deque.popleft() és O(1).
Detectar cicles comprovant "veí ja visitat" amb un sol set. En grafs dirigits, arribar a un vèrtex negre (acabat) per un altre camí no és un cicle, és un rombe de dependències perfectament legal. Sense l'estat gris, donaràs falsos positius.
Oblidar que el graf pot no ser connex. hi_ha_cicle i components_connexes iteren sobre tots els vèrtexs; si només llances des d'un, les illes queden sense explorar.
DFS recursiu sobre grafs enormes: la pila de crides de Python s'esgota (~1000 nivells, mòdul 3). Per a grafs profunds, la versió iterativa.
Consell: quan dubtis entre BFS i DFS, pregunta't què busques. Distàncies o "el més proper"? BFS. Cicles, ordres, explorar-ho tot sense que importi l'ordre? DFS sol ser més natural.

Exercicis

Exercici 1: BFS amb distàncies

Modifica bfs perquè retorni un dict vertex → distancia (nombre mínim d'arestes des de l'origen). Fes-lo servir per respondre: a quants "salts" de dissenyar_esquema és llancament?

Exercici 2: de què depèn aquesta tasca?

tasques_afectades mira cap endavant. Escriu prerequisits(graf, id_tasca) que retorni totes les tasques de les quals id_tasca depèn, directament o transitivament. Pista: o inverteixes el graf, o cerques des de cada vèrtex.

Exercici 3: traça de Kahn

Sense executar codi, traça l'ordre_topologic del graf de dependències en una taula (cua, extret, graus que canvien) i verifica que coincideix amb la sortida mostrada a la lliçó.

Solucions

Solució 1:

def bfs_distancies(graf, origen):
    distancies = {origen: 0}          # fa també de visitats
    cua = deque([origen])
    while cua:
        actual = cua.popleft()
        for vei in graf.veins(actual):
            if vei not in distancies:
                distancies[vei] = distancies[actual] + 1
                cua.append(vei)
    return distancies

print(bfs_distancies(dependencies, "dissenyar_esquema")["llancament"])  # 4

El dict de distàncies substitueix el set de visitats: ser-hi ja significa "vist". llancament és a 4 salts, com a la traça.

Solució 2:

def invertir(graf):
    inv = Graf(dirigit=True)
    for v in graf.vertexs():
        inv.afegir_vertex(v)
        for desti, pes in graf.veins(v).items():
            inv.afegir_aresta(desti, v, pes)   # la fletxa, del revés
    return inv

def prerequisits(graf, id_tasca):
    return bfs(invertir(graf), id_tasca)[1:]

print(prerequisits(dependencies, "desplegar_api"))
# ['migrar_bd', 'configurar_servidor', 'dissenyar_esquema']

Invertir el graf costa O(n + a) i converteix "qui depèn de mi?" en "de qui depenc?": el mateix BFS respon totes dues preguntes segons el sentit de les fletxes.

Solució 3:

Pas	Cua abans	Extret	Graus que baixen	Nous grau-0
1	[d_esquema, c_servidor, d_ui]	dissenyar_esquema	migrar_bd: 1→0	migrar_bd
2	[c_servidor, d_ui, migrar_bd]	configurar_servidor	desplegar_api: 2→1	—
3	[d_ui, migrar_bd]	dissenyar_ui	implementar_ui: 1→0	implementar_ui
4	[migrar_bd, implementar_ui]	migrar_bd	desplegar_api: 1→0	desplegar_api
5	[implementar_ui, desplegar_api]	implementar_ui	proves: 2→1	—
6	[desplegar_api]	desplegar_api	proves: 1→0	proves_integracio
7	[proves_integracio]	proves_integracio	llancament: 1→0	llancament
8	[llancament]	llancament	—	—

Ordre final: el de la lliçó. Observa com cap tasca no surt abans que totes les seves dependències hagin sortit: aquesta és la garantia de l'ordre topològic.

Conclusió

BFS i DFS són els dos motors d'exploració de grafs: mateixa maquinària, diferent estructura de suport (cua → capes i distàncies mínimes en arestes; pila → profunditat, cicles i ordres), tots dos en O(n + a) gràcies al visitats que el mòdul 5 va deixar preparat. Sobre ells hem construït les tres operacions que TaskFlow necessitava: anàlisi d'impacte (abastables), rebuig de dependències circulars (blanc/gris/negre, la germana graf de Floyd) i l'ordre d'execució del projecte (Kahn). Però BFS mesura camins en nombre d'arestes, i a la vida real les arestes no costen el mateix: passar per una tasca de 8 hores no és com passar per una d'1. Quan les arestes tenen pes, cal alguna cosa millor — i aquesta cosa, Dijkstra, reutilitza la cua de prioritat heapq del mòdul 4. És la propera lliçó.

Algorismes de Cerca en Grafs

Contingut

Per què `visitats` ara és imprescindible

BFS: cerca en amplada amb `deque`

Traça de BFS sobre el graf de dependències

DFS: cerca en profunditat, recursiva i iterativa

Traça de DFS i comparació BFS/DFS

Aplicació 1: què desbloqueja acabar una tasca? (abastables)

Aplicació 2: detecció de cicles amb estats blanc/gris/negre

Aplicació 3: ordre topològic (algorisme de Kahn)

Components connexes

Errors Comuns i Consells

Exercicis

Exercici 1: BFS amb distàncies

Exercici 2: de què depèn aquesta tasca?

Exercici 3: traça de Kahn

Solucions

Conclusió

Curs d'Estructures de Dades

Mòdul 1: Introducció a les Estructures de Dades

Mòdul 2: Llistes

Mòdul 3: Piles

Mòdul 4: Cues

Mòdul 5: Taules Hash i Diccionaris

Mòdul 6: Arbres

Mòdul 7: Grafs

Mòdul 8: Conclusions i Recursos Addicionals

Algorismes de Cerca en Grafs

Contingut

Per què visitats ara és imprescindible

BFS: cerca en amplada amb deque

Traça de BFS sobre el graf de dependències

DFS: cerca en profunditat, recursiva i iterativa

Traça de DFS i comparació BFS/DFS

Aplicació 1: què desbloqueja acabar una tasca? (abastables)

Aplicació 2: detecció de cicles amb estats blanc/gris/negre

Aplicació 3: ordre topològic (algorisme de Kahn)

Components connexes

Errors Comuns i Consells

Exercicis

Exercici 1: BFS amb distàncies

Exercici 2: de què depèn aquesta tasca?

Exercici 3: traça de Kahn

Solucions

Conclusió

Curs d'Estructures de Dades

Mòdul 1: Introducció a les Estructures de Dades

Mòdul 2: Llistes

Mòdul 3: Piles

Mòdul 4: Cues

Mòdul 5: Taules Hash i Diccionaris

Mòdul 6: Arbres

Mòdul 7: Grafs

Mòdul 8: Conclusions i Recursos Addicionals

Per què `visitats` ara és imprescindible

BFS: cerca en amplada amb `deque`