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

HOME

Ja sabem què és un graf; ara toca decidir com desar-lo en memòria. Hi ha dues representacions clàssiques —la matriu d'adjacència i la llista d'adjacència— i triar bé entre elles és una decisió d'enginyeria amb conseqüències directes en espai i temps, exactament el tipus d'anàlisi Big O que practiquem des del mòdul 1. En aquesta lliçó compararem totes dues, veurem per què per als grafs dispersos de TaskFlow guanya la llista d'adjacència (construïda amb els dict i set del mòdul 5), i implementarem la classe Graf que farem servir en tota la resta del mòdul.

Contingut

Matriu d'adjacència
Llista d'adjacència
Comparativa de costos: espai i temps
Quan convé cadascuna? Dens davant de dispers
La classe Graf del curs
El graf de dependències de TaskFlow amb la classe
Menció: la llista d'arestes

Matriu d'adjacència

La idea: numera els n vèrtexs de 0 a n-1 i crea una taula n × n on la cel·la [i][j] diu si existeix l'aresta i → j (amb 1/0, o amb el pes si el graf és ponderat).

# Vèrtexs, en ordre fix:
vertexs = ["migrar_bd", "configurar_servidor", "desplegar_api"]
# index: migrar_bd=0, configurar_servidor=1, desplegar_api=2

# Matriu 3x3 amb list de lists (com els arrays del mòdul 1):
matriu = [
    [0, 0, 1],   # migrar_bd -> desplegar_api
    [0, 0, 1],   # configurar_servidor -> desplegar_api
    [0, 0, 0],   # desplegar_api no desbloqueja res (encara)
]

# Existeix l'aresta migrar_bd -> desplegar_api?
print(matriu[0][2] == 1)   # True, en O(1): accés directe per índex

Explicació del fragment:

La fila i descriu les arestes que surten del vèrtex i; la columna j, les que entren a j. Per això matriu[0][2] = 1 codifica migrar_bd → desplegar_api amb la nostra convenció (la fletxa apunta al que es desbloqueja).
Consultar una aresta és un doble accés per índex: O(1), la gran virtut de la matriu.
En un graf no dirigit la matriu és simètrica (matriu[i][j] == matriu[j][i]); en un de ponderat, hi desaríem el pes en lloc d'1 (i un valor especial com None o float("inf") per a "no hi ha aresta").

El problema salta a la vista: amb només 3 vèrtexs i 2 arestes ja emmagatzemem 9 cel·les, gairebé totes a zero. Amb les 200 tasques d'un projecte gran de TaskFlow serien 40.000 cel·les per a potser 300 dependències: més del 99 % de zeros. La matriu ocupa O(n²) hi hagi les arestes que hi hagi.

Llista d'adjacència

L'alternativa: per a cada vèrtex, desa només els seus veïns (els destins de les seves arestes sortints). En Python, la parella natural és un dict el valor del qual és un set — les dues estructures del mòdul 5, amb la seva pertinença en O(1) mitjà:

adjacencia = {
    "migrar_bd": {"desplegar_api"},
    "configurar_servidor": {"desplegar_api"},
    "desplegar_api": set(),
}

# Existeix l'aresta? Dues consultes O(1) de taula hash:
print("desplegar_api" in adjacencia["migrar_bd"])   # True

# Veïns d'un vèrtex: directes, sense recórrer res
print(adjacencia["configurar_servidor"])            # {'desplegar_api'}

Explicació:

La clau és el vèrtex d'origen; el valor, el conjunt de destins. Un vèrtex sense arestes sortints desa un set() buit — però continua tenint la seva entrada al dict, que és el que el fa existir com a vèrtex.
L'espai total és O(n + a) (vèrtexs més arestes): paguem pel que hi ha, no pel que hi podria haver. Per a grafs dispersos, la diferència amb O(n²) és abismal.
Fer servir set en lloc de list per als veïns ens dóna existeix_aresta en O(1) mitjà en comptes d'O(grau); amb list mantindríem l'ordre d'inserció, però la consulta seria lineal. Per a grafs ponderats, el pas natural és un dict intern desti → pes, que conserva la consulta O(1) i hi afegeix el pes. És el que farà la nostra classe.

Comparativa de costos: espai i temps

Amb n vèrtexs i a arestes:

Operació	Matriu d'adjacència	Llista d'adjacència (`dict` de `set`/`dict`)
Espai	`O(n²)`	`O(n + a)`
Existeix l'aresta `u → v`?	`O(1)`	`O(1)` mitjà (hash)
Recórrer els veïns d'`u`	`O(n)` (fila sencera, zeros inclosos)	`O(grau(u))`
Afegir una aresta	`O(1)`	`O(1)` mitjà
Afegir un vèrtex	`O(n)` o pitjor (fila i columna noves)	`O(1)`
Grau de sortida d'`u`	`O(n)` (comptar la fila)	`O(1)` (`len`)
Grau d'entrada d'`u`	`O(n)` (comptar la columna)	`O(n + a)` (o mantenir un comptador a part)

Dues lectures importants de la taula:

L'operació que els algorismes de les properes lliçons executen milions de vegades és "dóna'm els veïns d'u". A la llista d'adjacència costa exactament el grau del vèrtex; a la matriu, sempre n. Per això BFS/DFS costaran O(n + a) amb llista però O(n²) amb matriu.
El grau d'entrada és incòmode en totes dues; quan el necessitem sovint (ordre topològic, 07-03), el precalcularem una vegada i el mantindrem en un dict a part.

Quan convé cadascuna? Dens davant de dispers

Situació	Representació recomanada
Graf dispers (`a ≈ n`): dependències, xarxes socials, mapes	Llista d'adjacència
Graf dens (`a ≈ n²`): tots contra tots, matrius de distàncies	Matriu d'adjacència
Consultes massives de "existeix l'aresta?" sobre un graf petit i estable	Matriu d'adjacència
Vèrtexs que apareixen i desapareixen dinàmicament	Llista d'adjacència

El graf de dependències de TaskFlow és el cas dispers de manual (cada tasca depèn d'un grapat), així que la nostra classe farà servir llista d'adjacència. La matriu reapareixerà de forma natural a Floyd-Warshall (07-04), que treballa precisament amb la taula de distàncies tots-a-tots.

La classe `Graf` del curs

Aquesta és la classe que farem servir en tot el mòdul. Decisions de disseny, abans del codi:

Llista d'adjacència amb dict extern (vèrtex → veïns) i dict intern (destí → pes). Per a grafs no ponderats el pes és simplement 1, així el mateix codi serveix per a la 07-03 (sense pesos) i la 07-04/07-05 (amb pesos).
dirigit opcional: per defecte True (dependències); amb False (per al MST de la 07-05), cada aresta es registra en tots dos sentits.
Els vèrtexs són els id de les tasques; els dict complets de cada tasca viuen en un índex a part, com al mòdul 5.

class Graf:
    """Graf amb llista d'adjacència: dict vertex -> dict desti -> pes."""

    def __init__(self, dirigit=True):
        self.dirigit = dirigit
        self.adjacencia = {}

    def afegir_vertex(self, v):
        # setdefault: crea l'entrada només si no existeix (idempotent)
        self.adjacencia.setdefault(v, {})

    def afegir_aresta(self, origen, desti, pes=1):
        self.afegir_vertex(origen)       # els extrems es donen d'alta sols
        self.afegir_vertex(desti)
        self.adjacencia[origen][desti] = pes
        if not self.dirigit:             # no dirigit: l'aresta va i ve
            self.adjacencia[desti][origen] = pes

    def veins(self, v):
        """Dict desti -> pes de les arestes que surten de v."""
        return self.adjacencia.get(v, {})

    def existeix_aresta(self, origen, desti):
        return desti in self.adjacencia.get(origen, {})

    def vertexs(self):
        return list(self.adjacencia)

    def grau_sortida(self, v):
        return len(self.adjacencia.get(v, {}))

    def grau_entrada(self, v):
        # O(n + a): recorre totes les llistes de veïns
        return sum(1 for destins in self.adjacencia.values() if v in destins)

    def graus_entrada(self):
        """Tots els graus d'entrada d'una passada: O(n + a) total."""
        graus = {v: 0 for v in self.adjacencia}
        for destins in self.adjacencia.values():
            for desti in destins:
                graus[desti] += 1
        return graus

Punts que convé entendre línia a línia:

afegir_aresta crida primer afegir_vertex per a tots dos extrems: així mai no hi ha arestes "penjant" de vèrtexs inexistents, i afegir l'aresta A → B d'una tirada crea A i B si calia.
veins retorna el dict intern desti → pes. Iterar-lo amb for desti in g.veins(v) dóna els destins; amb for desti, pes in g.veins(v).items(), també els pesos. Totes dues formes apareixeran constantment.
grau_entrada d'un sol vèrtex és car (O(n + a)); per això oferim graus_entrada(), que calcula tots alhora pel mateix preu. Kahn (07-03) farà servir aquesta segona.
Repetir afegir_aresta(origen, desti) no duplica res: el dict intern aixafa el pes anterior. Amb una list de veïns hauríem hagut de vigilar els duplicats a mà.

El graf de dependències de TaskFlow amb la classe

Construïm el DAG de la lliçó anterior. Recordatori de la convenció: afegir_aresta(A, B) significa "B depèn d'A" (acabar A acosta el desbloqueig de B).

tasques = {
    "dissenyar_esquema":   {"id": "dissenyar_esquema", "titol": "Dissenyar l'esquema de BD",
                            "prioritat": 2, "estat": "pendent", "hores": 3},
    "migrar_bd":           {"id": "migrar_bd", "titol": "Migrar la BD",
                            "prioritat": 1, "estat": "pendent", "hores": 2},
    "configurar_servidor": {"id": "configurar_servidor", "titol": "Configurar el servidor",
                            "prioritat": 2, "estat": "pendent", "hores": 1},
    "desplegar_api":       {"id": "desplegar_api", "titol": "Desplegar l'API",
                            "prioritat": 1, "estat": "pendent", "hores": 2},
    "dissenyar_ui":        {"id": "dissenyar_ui", "titol": "Dissenyar la interfície",
                            "prioritat": 3, "estat": "pendent", "hores": 5},
    "implementar_ui":      {"id": "implementar_ui", "titol": "Implementar la interfície",
                            "prioritat": 2, "estat": "pendent", "hores": 8},
    "proves_integracio":   {"id": "proves_integracio", "titol": "Proves d'integració",
                            "prioritat": 1, "estat": "pendent", "hores": 3},
    "llancament":          {"id": "llancament", "titol": "Llançament",
                            "prioritat": 1, "estat": "pendent", "hores": 1},
}

dependencies = Graf(dirigit=True)
for id_tasca in tasques:
    dependencies.afegir_vertex(id_tasca)   # també les tasques sense arestes

dependencies.afegir_aresta("dissenyar_esquema", "migrar_bd")
dependencies.afegir_aresta("migrar_bd", "desplegar_api")
dependencies.afegir_aresta("configurar_servidor", "desplegar_api")
dependencies.afegir_aresta("desplegar_api", "proves_integracio")
dependencies.afegir_aresta("dissenyar_ui", "implementar_ui")
dependencies.afegir_aresta("implementar_ui", "proves_integracio")
dependencies.afegir_aresta("proves_integracio", "llancament")

print(dependencies.veins("migrar_bd"))                 # {'desplegar_api': 1}
print(dependencies.existeix_aresta("dissenyar_ui", "llancament"))  # False (no hi ha aresta DIRECTA)
print(dependencies.grau_entrada("desplegar_api"))      # 2: espera dues tasques
print(dependencies.graus_entrada())
# {'dissenyar_esquema': 0, 'migrar_bd': 1, 'configurar_servidor': 0, 'desplegar_api': 2,
#  'dissenyar_ui': 0, 'implementar_ui': 1, 'proves_integracio': 2, 'llancament': 1}

El graf que acabem de construir:

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]

Fixa't en la sortida de graus_entrada(): els zeros (dissenyar_esquema, configurar_servidor, dissenyar_ui) són exactament les tasques que poden començar avui. Aquest diccionari és, literalment, el punt de partida de l'algorisme de Kahn de la propera lliçó.

Menció: la llista d'arestes

Existeix una tercera representació, la llista d'arestes: simplement una llista de tuples [(origen, desti, pes), ...]. És pèssima per consultar veïns (O(a) per consulta), però perfecta quan un algorisme necessita totes les arestes ordenades per pes — que és justament el que farà Kruskal a la lliçó 07-05. La citem aquí i la recuperarem llavors.

Errors Comuns i Consells

Oblidar els vèrtexs sense arestes. Si construeixes el graf només amb afegir_aresta, una tasca sense dependències ni dependents no existirà a adjacencia i els algorismes la ignoraran en silenci. Per això l'exemple dóna d'alta tots els vèrtexs primer.
Registrar l'aresta en un sol sentit en grafs no dirigits. Si oblides l'escriptura simètrica, "l'Anna coneix en Bruno" però en Bruno no coneix l'Anna, i BFS donarà resultats absurds. La nostra classe ho resol a afegir_aresta; si escrius la teva, no ho ometis.
Mutar el dict retornat per veins(). Retorna el diccionari intern real; si el modifiques des de fora, corromps el graf. Tracta'l com de només lectura (o retorna dict(...), una còpia, si prefereixes blindar-lo pagant-ne el cost).
Fer servir grau_entrada(v) dins d'un bucle sobre tots els vèrtexs. Això és O(n · (n + a)). Per a tots alhora, graus_entrada() ho fa en una sola passada.
Consell: els vèrtexs han de ser valors hashables (strings, números, tuples). Fem servir l'id de la tasca, mai el dict complet — els dict no poden ser claus d'un altre dict, com vam veure al mòdul 5.

Exercicis

Exercici 1: la matriu del mateix graf

Escriu (a mà o amb codi) la matriu d'adjacència del graf de TaskFlow d'aquesta lliçó, amb l'ordre de vèrtexs [dissenyar_esquema, migrar_bd, configurar_servidor, desplegar_api, dissenyar_ui, implementar_ui, proves_integracio, llancament]. Quantes cel·les té i quantes valen 1? Quin percentatge de la matriu és útil?

Exercici 2: `eliminar_aresta` i `eliminar_vertex`

Afegeix a la classe Graf els mètodes eliminar_aresta(origen, desti) i eliminar_vertex(v) (a TaskFlow: treure una dependència i esborrar una tasca). Compte: en eliminar un vèrtex han de desaparèixer també les arestes que hi arriben. Indica el cost de cada mètode.

Exercici 3: tasques executables

Escriu una funció tasques_executables(graf, tasques) que retorni els id amb grau d'entrada 0 l'estat dels quals sigui "pendent", ordenats per prioritat (1 primer). Prova-la amb el graf de la lliçó.

Solucions

Solució 1:

#                 d_e  mig  c_s  api  ui   imp  pro  lla
matriu = [
    [0,   1,   0,   0,   0,   0,   0,   0],   # dissenyar_esquema
    [0,   0,   0,   1,   0,   0,   0,   0],   # migrar_bd
    [0,   0,   0,   1,   0,   0,   0,   0],   # configurar_servidor
    [0,   0,   0,   0,   0,   0,   1,   0],   # desplegar_api
    [0,   0,   0,   0,   0,   1,   0,   0],   # dissenyar_ui
    [0,   0,   0,   0,   0,   0,   1,   0],   # implementar_ui
    [0,   0,   0,   0,   0,   0,   0,   1],   # proves_integracio
    [0,   0,   0,   0,   0,   0,   0,   0],   # llancament
]

64 cel·les, 7 a u: el 10,9 % és informació i el 89 % són zeros. I només hi ha 8 tasques; amb 200, la part útil rondaria el 0,7 %. És la imatge exacta de per què triem llista d'adjacència.

Solució 2:

def eliminar_aresta(self, origen, desti):
    # pop amb valor per defecte: no falla si l'aresta no existia
    self.adjacencia.get(origen, {}).pop(desti, None)
    if not self.dirigit:
        self.adjacencia.get(desti, {}).pop(origen, None)

def eliminar_vertex(self, v):
    self.adjacencia.pop(v, None)          # les seves arestes sortints: O(1)
    for destins in self.adjacencia.values():
        destins.pop(v, None)              # les que hi arribaven: O(n + a)

eliminar_aresta és O(1) mitjà. eliminar_vertex és O(n + a): no hi ha manera de localitzar les arestes entrants sense revisar totes les llistes de veïns — el mateix motiu pel qual grau_entrada era car.

Solució 3:

def tasques_executables(graf, tasques):
    graus = graf.graus_entrada()                         # una sola passada
    llista = [t for t, g in graus.items()
              if g == 0 and tasques[t]["estat"] == "pendent"]
    return sorted(llista, key=lambda t: tasques[t]["prioritat"])

print(tasques_executables(dependencies, tasques))
# ['dissenyar_esquema', 'configurar_servidor', 'dissenyar_ui']
# (prioritats 2, 2 i 3: les dues primeres empaten i conserven l'ordre estable)

sorted és estable (mòdul 1), així que els empats de prioritat respecten l'ordre previ. Aquesta funció és un avançament en miniatura de l'ordre topològic complet de la propera lliçó.

Conclusió

Tenim les dues representacions clàssiques mesurades i comparades: la matriu (O(n²), aresta en O(1), ideal en grafs densos) i la llista d'adjacència (O(n + a), veïns al preu just, l'elecció per a grafs dispersos com els de TaskFlow). I, sobretot, tenim la classe Graf —llista d'adjacència amb dict de dict, dirigit opcional, pesos incorporats— i el graf de dependències real construït amb ella. L'estructura ja és en memòria; ara cal recórrer-la. A la propera lliçó arriben per fi BFS i DFS sobre grafs: el recorregut per nivells del mòdul 6 generalitzat, la pila del mòdul 3 reapareix a DFS, i el set de visitats promès al mòdul 5 esdevé, amb els cicles, no ja útil sinó imprescindible.

Representació de Grafs

Contingut

Matriu d'adjacència

Llista d'adjacència

Comparativa de costos: espai i temps

Quan convé cadascuna? Dens davant de dispers

La classe `Graf` del curs

El graf de dependències de TaskFlow amb la classe

Menció: la llista d'arestes

Errors Comuns i Consells

Exercicis

Exercici 1: la matriu del mateix graf

Exercici 2: `eliminar_aresta` i `eliminar_vertex`

Exercici 3: tasques executables

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

Representació de Grafs

Contingut

Matriu d'adjacència

Llista d'adjacència

Comparativa de costos: espai i temps

Quan convé cadascuna? Dens davant de dispers

La classe Graf del curs

El graf de dependències de TaskFlow amb la classe

Menció: la llista d'arestes

Errors Comuns i Consells

Exercicis

Exercici 1: la matriu del mateix graf

Exercici 2: eliminar_aresta i eliminar_vertex

Exercici 3: tasques executables

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

La classe `Graf` del curs

Exercici 2: `eliminar_aresta` i `eliminar_vertex`