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

Exercicis amb Grafs

Següent ►
►

Tota la teoria del mòdul és sobre la taula: modelatge (07-01), la classe Graf (07-02), BFS/DFS/Kahn (07-03), Dijkstra i companyia (07-04), MST i Union-Find (07-05) i les seves aplicacions (07-06). Aquesta lliçó és íntegrament pràctica: sis exercicis progressius, sense teoria nova, al voltant d'un projecte real de TaskFlow — el llançament de la seva app mòbil. Intenta resoldre cadascun pel teu compte abans de mirar la solució; l'ordre importa, perquè cada exercici reutilitza peces de l'anterior. Necessitaràs la classe Graf i les funcions bfs, ordre_topologic i invertir de les lliçons anteriors.

Contingut

  1. El projecte de partida
  2. Exercici 1: construir i consultar el graf del projecte
  3. Exercici 2: el camí amb menys passos entre dues tasques
  4. Exercici 3: detectar i llistar el cicle de dependències
  5. Exercici 4: ordre d'execució amb desempat per prioritat
  6. Exercici 5: illes de tasques (projectes independents)
  7. Exercici 6: la graella com a graf implícit
  8. Solucions

El projecte de partida

L'equip planifica a TaskFlow el llançament de l'app mòbil. Aquestes són les tasques (amb la seva prioritat, 1 = màxima) i les seves dependències, en llenguatge natural:

Tasca Prioritat Depèn de
definir_abast 1 —
dissenyar_pantalles 2 definir_abast
triar_stack 1 definir_abast
implementar_login 2 dissenyar_pantalles, triar_stack
implementar_tauler 1 dissenyar_pantalles, triar_stack
connectar_api 1 implementar_login, implementar_tauler
proves_usabilitat 2 connectar_api
preparar_marqueting 3 —
publicar_botiga 1 proves_usabilitat, preparar_marqueting 
graph LR
    A[definir_abast] --> B[dissenyar_pantalles]
    A --> C[triar_stack]
    B --> D[implementar_login]
    C --> D
    B --> E[implementar_tauler]
    C --> E
    D --> F[connectar_api]
    E --> F
    F --> G[proves_usabilitat]
    M[preparar_marqueting] --> H
    G --> H[publicar_botiga]

Exercici 1: construir i consultar el graf del projecte

Construeix el graf mobil amb la classe Graf (recorda la convenció del mòdul: afegir_aresta(A, B) = "B depèn d'A") i un diccionari prioritats amb la prioritat de cada tasca. Després respon amb codi: (a) quines tasques poden començar ja (grau d'entrada 0)?; (b) quantes tasques desbloqueja directament triar_stack i quines són?; (c) és publicar_botiga l'única tasca "final" (grau de sortida 0)?

Exercici 2: el camí amb menys passos entre dues tasques

El cap de projecte pregunta: "quina és la cadena de dependències més curta que porta de definir_abast a publicar_botiga?". Escriu cami_minim_passos(graf, origen, desti) que retorni la llista de tasques del camí amb menys arestes (o None si no hi ha camí). Pista: BFS desant predecessors, i reconstrucció cap enrere com a Dijkstra (07-04) — però sense monticle: aquí no hi ha pesos.

Exercici 3: detectar i llistar el cicle de dependències

Un usuari despistat afegeix dues dependències noves: la retroalimentació dels usuaris arriba després de publicar (publicar_botiga → retro_usuaris) i, amb les presses, declara que el disseny de pantalles depèn d'aquesta retroalimentació (retro_usuaris → dissenyar_pantalles). El projecte queda bloquejat. hi_ha_cicle (07-03) només retorna True; per a un missatge d'error útil, TaskFlow necessita ensenyar el cicle. Escriu trobar_cicle(graf) que retorni la llista de vèrtexs del cicle (acabant amb el vèrtex inicial repetit), o None si no n'hi ha. Pista: al DFS blanc/gris/negre, mantén a més la llista cami de vèrtexs grisos; en topar amb un gris, el cicle és el tram de cami des d'aquell vèrtex.

Exercici 4: ordre d'execució amb desempat per prioritat

ordre_topologic (Kahn) tria arbitràriament entre les tasques disponibles. L'equip vol alguna cosa millor: entre les tasques executables a cada moment, primer la de major prioritat (menor número; a igual prioritat, ordre alfabètic). Escriu ordre_topologic_prioritat(graf, prioritats) substituint la deque de Kahn pel heapq del mòdul 4 amb tuples (prioritat, id). Aplica'l al graf mobil (sense les arestes de l'exercici 3) i compara la posició de preparar_marqueting amb la que li donaria una cua normal.

Exercici 5: illes de tasques (projectes independents)

Al graf mobil s'hi sumen les tasques d'un altre front de feina: redissenyar_logo → actualitzar_web i actualitzar_web → nota_premsa, més una tasca solta sense relacions, renovar_domini. Escriu illes_de_tasques(graf) que retorni les components connexes (ignorant el sentit de les fletxes, com a la 07-03) ordenades de major a menor mida, i fes-la servir per respondre: quants projectes independents conviuen al tauler i de quina mida?

Exercici 6: la graella com a graf implícit

L'oficina de TaskFlow estrena un robot de repartiment de paquets que es mou per un magatzem quadriculat: . és terra lliure, # una prestatgeria, S la sortida del robot i M la taula de destinació:

magatzem = [
    "S.#.",
    ".#..",
    "....",
    "#.#M",
]

Calcula el mínim nombre de moviments (amunt/avall/esquerra/dreta) d'S a M amb BFS... sense construir cap objecte Graf. La graella ja és un graf: cada cel·la lliure és un vèrtex i els seus veïns es calculen al vol mirant les quatre caselles contigües. Aquest patró de graf implícit és importantíssim: demostra que BFS necessita saber "dóna'm els veïns de v", no una estructura concreta.

Solucions

Solució 1

mobil = Graf(dirigit=True)
dependencies_mobil = [
    ("definir_abast", "dissenyar_pantalles"),
    ("definir_abast", "triar_stack"),
    ("dissenyar_pantalles", "implementar_login"),
    ("triar_stack", "implementar_login"),
    ("dissenyar_pantalles", "implementar_tauler"),
    ("triar_stack", "implementar_tauler"),
    ("implementar_login", "connectar_api"),
    ("implementar_tauler", "connectar_api"),
    ("connectar_api", "proves_usabilitat"),
    ("proves_usabilitat", "publicar_botiga"),
    ("preparar_marqueting", "publicar_botiga"),
]
for origen, desti in dependencies_mobil:
    mobil.afegir_aresta(origen, desti)

prioritats = {
    "definir_abast": 1, "dissenyar_pantalles": 2, "triar_stack": 1,
    "implementar_login": 2, "implementar_tauler": 1, "connectar_api": 1,
    "proves_usabilitat": 2, "preparar_marqueting": 3, "publicar_botiga": 1,
}

# (a) grau d'entrada 0: poden començar avui
graus = mobil.graus_entrada()
print([t for t, g in graus.items() if g == 0])
# ['definir_abast', 'preparar_marqueting']

# (b) desbloqueigs directes de triar_stack
print(mobil.grau_sortida("triar_stack"), list(mobil.veins("triar_stack")))
# 2 ['implementar_login', 'implementar_tauler']

# (c) tasques finals: grau de sortida 0
print([t for t in mobil.vertexs() if mobil.grau_sortida(t) == 0])
# ['publicar_botiga']  -> sí, és l'única

Comentaris: totes les tasques apareixen en alguna aresta, així que no va caldre afegir_vertex explícit — però revisa sempre aquesta suposició (aquí renovar_domini de l'exercici 5 la trencarà). Les respostes surten dels mètodes de la classe, sense cap algorisme: modelar bé ja respon preguntes.

Solució 2

from collections import deque

def cami_minim_passos(graf, origen, desti):
    if origen == desti:
        return [origen]
    predecessor = {origen: None}         # fa tambe de visitats (07-03)
    cua = deque([origen])
    while cua:
        actual = cua.popleft()
        for vei in graf.veins(actual):
            if vei not in predecessor:
                predecessor[vei] = actual
                if vei == desti:         # hi hem arribat: podem parar ja
                    cami = [desti]
                    while predecessor[cami[-1]] is not None:
                        cami.append(predecessor[cami[-1]])
                    return cami[::-1]    # es reconstrueix del reves, com a la 07-04
                cua.append(vei)
    return None                          # cua buida sense arribar-hi: inabastable

print(cami_minim_passos(mobil, "definir_abast", "publicar_botiga"))
# ['definir_abast', 'dissenyar_pantalles', 'implementar_login',
#  'connectar_api', 'proves_usabilitat', 'publicar_botiga']

Comentaris: el dict de predecessors compleix dos papers (marcar visitats i recordar el camí), igual que a Dijkstra però sense pesos ni monticle. Poder tallar tan bon punt s'arriba al destí és un luxe exclusiu de BFS: la primera visita garanteix el mínim d'arestes. Hi ha dos camins de 5 arestes (pel login o pel tauler); BFS retorna el primer que descobreix, i tots dos són correctes.

Solució 3

def trobar_cicle(graf):
    BLANC, GRIS, NEGRE = 0, 1, 2
    color = {v: BLANC for v in graf.vertexs()}
    cami = []                                    # els vertexs grisos, en ordre

    def visitar(v):
        color[v] = GRIS
        cami.append(v)
        for vei in graf.veins(v):
            if color[vei] == GRIS:               # aresta cap al camí actual
                inici = cami.index(vei)          # on comença el cicle
                return cami[inici:] + [vei]
            if color[vei] == BLANC:
                cicle = visitar(vei)
                if cicle:
                    return cicle                 # propagar la troballa cap amunt
        cami.pop()                               # backtracking: v deixa el camí
        color[v] = NEGRE
        return None

    for v in graf.vertexs():
        if color[v] == BLANC:
            cicle = visitar(v)
            if cicle:
                return cicle
    return None

mobil.afegir_aresta("publicar_botiga", "retro_usuaris")
mobil.afegir_aresta("retro_usuaris", "dissenyar_pantalles")
print(trobar_cicle(mobil))
# ['dissenyar_pantalles', 'implementar_login', 'connectar_api',
#  'proves_usabilitat', 'publicar_botiga', 'retro_usuaris', 'dissenyar_pantalles']

# netejar per als exercicis següents (eliminar_aresta: exercici 2 de la 07-02)
mobil.eliminar_aresta("publicar_botiga", "retro_usuaris")
mobil.eliminar_aresta("retro_usuaris", "dissenyar_pantalles")

Comentaris: l'única novetat sobre hi_ha_cicle (07-03) és la llista cami, que creix en pintar de gris i encongeix al backtracking — una pila explícita, mòdul 3, que retrata a cada moment la branca actual del DFS. En topar amb un gris, el tram des de la seva posició és exactament el cicle; s'afegeix el vèrtex repetit al final perquè el missatge a l'usuari es llegeixi com un cercle tancat. Amb aquesta llista, TaskFlow pot mostrar: "no puc afegir la dependència: dissenyar_pantalles → ... → retro_usuaris → dissenyar_pantalles".

Solució 4

import heapq

def ordre_topologic_prioritat(graf, prioritats):
    graus = graf.graus_entrada()
    monticle = [(prioritats[v], v) for v, g in graus.items() if g == 0]
    heapq.heapify(monticle)
    ordre = []
    while monticle:
        _, actual = heapq.heappop(monticle)      # l'executable mes prioritaria
        ordre.append(actual)
        for vei in graf.veins(actual):
            graus[vei] -= 1
            if graus[vei] == 0:
                heapq.heappush(monticle, (prioritats[vei], vei))
    if len(ordre) < len(graus):
        raise ValueError("Hi ha un cicle de dependències")
    return ordre

prioritats["retro_usuaris"] = 3          # va quedar com a vertex despres de l'exercici 3
print(ordre_topologic_prioritat(mobil, prioritats))
# ['definir_abast', 'triar_stack', 'dissenyar_pantalles', 'implementar_tauler',
#  'implementar_login', 'connectar_api', 'proves_usabilitat',
#  'preparar_marqueting', 'publicar_botiga', 'retro_usuaris']

Comentaris: és Kahn lletra per lletra amb la deque canviada per un monticle — la mateixa substitució cua→cua de prioritat que va convertir la Cua en SafataUrgencies al mòdul 4. Les tuples (prioritat, id) desempaten soles: primer per número, després alfabèticament, sense necessitat del comptador del mòdul 4 perquè els ids són strings comparables. Fixa't en preparar_marqueting: és executable des del minut u, però la seva prioritat 3 la relega fins al final (només surt quan és l'única opció); una cua FIFO l'hauria executada la segona o la tercera. L'ordre continua sent topològicament vàlid: el monticle només conté tasques amb totes les seves dependències complertes.

Solució 5

mobil.afegir_aresta("redissenyar_logo", "actualitzar_web")
mobil.afegir_aresta("actualitzar_web", "nota_premsa")
mobil.afegir_vertex("renovar_domini")            # sense arestes: alta explicita!

def illes_de_tasques(graf):
    nd = Graf(dirigit=False)                     # versio sense sentit de fletxes
    for v in graf.vertexs():
        nd.afegir_vertex(v)
        for desti in graf.veins(v):
            nd.afegir_aresta(v, desti)
    visitats, illes = set(), []
    for v in nd.vertexs():
        if v not in visitats:
            illa = bfs(nd, v)                    # tota la component de v
            visitats.update(illa)
            illes.append(illa)
    return sorted(illes, key=len, reverse=True)

for illa in illes_de_tasques(mobil):
    print(len(illa), illa)
# 9 ['definir_abast', ..., 'proves_usabilitat', 'publicar_botiga']
# 3 ['redissenyar_logo', 'actualitzar_web', 'nota_premsa']
# 1 ['retro_usuaris']
# 1 ['renovar_domini']

Comentaris: quatre illes — l'app mòbil (9 tasques), la campanya d'imatge (3) i dues tasques soltes. Sorprèn retro_usuaris? A l'exercici 3 en vam eliminar les dues arestes, però el vèrtex va continuar donat d'alta: ara apareix com a illa pròpia, un recordatori que V i E són conjunts independents (07-01). Dos detalls més a vigilar: la conversió a no dirigit abans de buscar components (amb les fletxes, publicar_botiga no "veuria" preparar_marqueting), i l'alta explícita de renovar_domini, que sense arestes no existiria al graf — l'error clàssic de la 07-02. Alternativa perfectament vàlida: UnionFind (07-05) unint els extrems de cada aresta; les arrels finals són les illes.

Solució 6

from collections import deque

def passos_minims(graella):
    files, columnes = len(graella), len(graella[0])
    for f in range(files):                       # localitzar S i M
        for c in range(columnes):
            if graella[f][c] == "S":
                sortida = (f, c)
            elif graella[f][c] == "M":
                meta = (f, c)

    visitats = {sortida}                         # el set de tuples del modul 5
    cua = deque([(sortida, 0)])                  # (cella, passos fins a ella)
    while cua:
        (f, c), passos = cua.popleft()
        if (f, c) == meta:
            return passos
        for df, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:   # les 4 direccions
            nf, nc = f + df, c + dc
            if (0 <= nf < files and 0 <= nc < columnes      # dins del tauler
                    and graella[nf][nc] != "#"              # no es prestatgeria
                    and (nf, nc) not in visitats):
                visitats.add((nf, nc))                      # marcar en encuar
                cua.append(((nf, nc), passos + 1))
    return None                                  # M inabastable

print(passos_minims(magatzem))   # 6

Comentaris: és el bfs de la 07-03 amb dos canvis cosmètics: els vèrtexs són tuples (fila, columna) —hashables, per això valen com a elements del set— i els "veïns" no es llegeixen de cap llista d'adjacència: es generen al vol sumant els quatre desplaçaments i filtrant límits i murs. Un camí òptim de 6 passos: (0,0) → (1,0) → (2,0) → (2,1) → (2,2) → (2,3) → (3,3); comprova-ho dibuixant sobre la graella. La lliçó de fons: BFS no necessita la classe Graf, només una funció de veïns. Mapes de jocs, estats d'un trencaclosques, versions d'un document: qualsevol cosa amb "estats i transicions" és un graf implícit i tot el mòdul li aplica.

Errors Comuns i Consells

  • Construir arestes amb la convenció invertida. Si escrius afegir_aresta("dissenyar_pantalles", "definir_abast") pensant "depèn de", tots els algorismes posteriors treballaran sobre un projecte del revés. Rellegeix cada aresta com "en acabar A es desbloqueja B" abans de continuar.
  • Oblidar els vèrtexs sense arestes (renovar_domini): no apareixen en illes, ordres ni recomptes. Alta explícita sempre.
  • cami.index(vei) en grafs enormes és O(longitud del camí); per a producció es desaria també la posició de cada vèrtex gris en un dict. Per entendre l'algorisme, la versió clara guanya.
  • Provar només el camí feliç. Executa cami_minim_passos amb destí inabastable, trobar_cicle sobre el graf net i el magatzem amb la meta tapiada: la meitat dels errors reals viuen als None.
  • Consell final del mòdul: quan un problema nou et desconcerti, pregunta't "què són aquí els vèrtexs i què les arestes?". És la pregunta que converteix robots en graelles, tasques en DAGs i usuaris en xarxes — i un cop resposta, els algorismes són sempre els mateixos sis d'aquest mòdul.

Conclusió

Sis exercicis i un projecte sencer després, els grafs han passat de concepte a eina: has construït i consultat el graf d'un llançament real, trobat la cadena de dependències més curta amb BFS i predecessors, convertit "hi ha un cicle" en un missatge d'error que ensenya el cicle, fet que Kahn respecti les prioritats amb el monticle del mòdul 4, separat el tauler en projectes independents i descobert que fins i tot un magatzem quadriculat és un graf si se li pregunta bé.

I amb això, una cosa més gran: TaskFlow és complet en estructures. Repassa el que s'ha construït al llarg del curs — el tauler sobre arrays i llistes enllaçades, el desfer amb piles, les notificacions i urgències amb cues i monticles, els índexs instantanis amb taules hash, les jerarquies amb arbres i, des d'aquest mòdul, les dependències, ordres i rutes amb grafs. No queda cap peça fonamental per conèixer. El que queda és criteri: davant d'un problema nou, quina estructura tries i per què? Aquest és exactament el tema del mòdul 8: mirar enrere amb perspectiva, aprendre a triar estructura amb arguments de cost i de disseny, i rematar el curs amb recursos per continuar i projectes finals que integrin tot l'après.

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