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

Representació de Grafs

Següent ►
►

Al final del mòdul anterior vam deixar un deute deliberat: cinc lliçons parlant de rutes, trams i "arestes" —la feromona de les formigues hi vivia literalment a sobre— sense definir formalment què és aquesta estructura. Ha arribat el moment de saldar-lo. En aquesta lliçó definim amb rigor què és un graf, aprenem les dues maneres clàssiques de representar-lo en memòria (matriu i llista d'adjacència), analitzem quan convé cadascuna, i presentem el graf canònic de la xarxa urbana de Rutalia, que serà el nostre camp de proves durant tot el mòdul 3, igual que la instància del TSP ho va ser al mòdul 2. Triar bé la representació no és un detall estètic: determina la complexitat de tots els algorismes que veurem després.

Contingut

  1. Definició formal: vèrtexs, arestes i variants
  2. Vocabulari essencial: grau, camins, cicles i connexió
  3. El graf canònic de la xarxa urbana de Rutalia
  4. Matriu d'adjacència
  5. Llista d'adjacència
  6. Comparativa: quan convé cada representació
  7. Grafs implícits: la quadrícula de 01-03 era un graf sense saber-ho
  8. Una nota sobre networkx

Definició formal: vèrtexs, arestes i variants

Un graf és un parell G = (V, E) on:

  • V és un conjunt finit de vèrtexs o nodes. A Rutalia: cruïlles, places, zones de la ciutat, punts de lliurament.
  • E és un conjunt d'arestes, cadascuna connectant un parell de vèrtexs. A Rutalia: trams de carrer transitables entre dos punts.

Sobre aquesta base mínima es construeixen les variants que necessitarem:

  • Graf no dirigit: les arestes són parells no ordenats {u, v}. Si es pot anar de la Plaça del Mercat al Magatzem, també a l'inrevés. Un carrer de doble sentit.
  • Graf dirigit (digraf): les arestes són parells ordenats (u, v); la relació va d'u cap a v. Un carrer de sentit únic. Les dependències entre tasques (03-02) i les xarxes de flux (03-05) són dirigides per naturalesa.
  • Graf ponderat: cada aresta porta associat un pes w(u, v): minuts de trajecte, quilòmetres, cost, capacitat. Sense pesos, tots els carrers "costen" el mateix; amb pesos, la ciutat es torna realista.
Variant Aresta Exemple a Rutalia
No dirigit, sense pesos {u, v} "Aquestes dues zones estan connectades per carrer"
No dirigit, ponderat {u, v}, w "El tram Mercat–Centre es fa en 5 minuts"
Dirigit, sense pesos (u, v) "La tasca escaneig ha d'anar abans que classificació"
Dirigit, ponderat (u, v), w "Per aquest carrer de sentit únic hi caben 12 paquets/hora"

Notació de mides que farem servir sempre: |V| = n (nombre de nodes) i |E| = m (nombre d'arestes). En un graf no dirigit sense arestes repetides, m pot arribar com a màxim a n(n−1)/2, és a dir, O(n²). Un graf amb m proper a n² s'anomena dens; amb m proper a n, dispers (sparse). Les xarxes de carrers reals són molt disperses: cada cruïlla connecta amb 3 o 4 carrers, no pas amb milers.

Vocabulari essencial: grau, camins, cicles i connexió

  • Adjacència: u i v són adjacents (veïns) si existeix l'aresta {u, v}.
  • Grau d'un vèrtex, deg(v): nombre d'arestes que hi incideixen. En dirigits se separa en grau d'entrada (arestes que arriben) i grau de sortida (arestes que surten). Propietat útil per detectar errors: en un graf no dirigit, la suma de tots els graus és exactament 2m (cada aresta hi aporta 2).
  • Camí: seqüència de vèrtexs v₀, v₁, …, vₖ on cada parell consecutiu està unit per una aresta. La seva longitud és el nombre d'arestes (k) o, en ponderats, la suma de pesos. Un camí és simple si no repeteix vèrtexs.
  • Cicle: camí que comença i acaba al mateix vèrtex sense repetir arestes. Un graf dirigit sense cicles s'anomena DAG (Directed Acyclic Graph); seran clau en l'ordenació topològica de 03-02.
  • Graf connex (no dirigit): existeix un camí entre qualsevol parell de vèrtexs. Si no ho és, es descompon en components connexes — trossos de ciutat incomunicats entre si. Ja vam calcular components a 01-04 amb union-find; a 03-02 ho farem també amb cerca i compararem.
  • Arbre: graf connex i sense cicles. Té exactament n−1 arestes. Els arbres d'expansió de 03-04 són això: l'esquelet mínim que ho manté tot connectat.

El graf canònic de la xarxa urbana de Rutalia

Igual que el mòdul 2 va fixar la seva instància canònica del TSP (9 parades + dipòsit, òptim 35,22 km), aquest mòdul fixa la seva xarxa urbana canònica: 9 zones de la ciutat i 15 trams de carrer de doble sentit, ponderats en minuts de furgoneta. Totes les dades són fictícies.

Codi Zona
ALM Magatzem Central de Rutalia
MER Plaça del Mercat
EST Estació Nord
UNI Ciutat Universitària
RIO Pont del Riu
CEN Centre Històric
IND Polígon Industrial
HOS Hospital General
PAR Parc de l'Oest 
graph LR
    ALM((ALM)) ---|3| RIO((RIO))
    ALM ---|4| MER((MER))
    ALM ---|7| EST((EST))
    ALM ---|12| CEN((CEN))
    MER ---|5| CEN
    MER ---|6| UNI((UNI))
    EST ---|3| UNI
    EST ---|9| IND((IND))
    UNI ---|8| CEN
    UNI ---|5| HOS((HOS))
    RIO ---|6| CEN
    RIO ---|8| PAR((PAR))
    CEN ---|4| HOS
    IND ---|6| HOS
    PAR ---|7| HOS

Detalls amb intenció, que explotarem a les properes lliçons:

  • L'aresta ALM–CEN amb pes 12 és la gran avinguda directa al Centre Històric: un sol tram, però congestionat. Avançament: anar pel Mercat (ALM→MER→CEN = 4+5 = 9 min) és més ràpid que la "línia recta". Aquesta tensió entre menys trams i menys minuts és exactament la diferència entre BFS (03-02) i Dijkstra (03-03).
  • El Polígon Industrial (IND) només té 2 connexions (grau 2): és la zona més fràgil davant dels talls de carrer.
  • El Centre Històric (CEN) és el node de grau més alt (5): el cor de la xarxa.

Comprovació ràpida de la propietat dels graus: 4+3+3+4+3+5+2+4+2 = 30 = 2·15 ✓.

Matriu d'adjacència

La matriu d'adjacència és una taula n×n on la cel·la [i][j] guarda el pes de l'aresta i→j (o un valor especial —0, None, inf— si no existeix). En un graf no dirigit, la matriu és simètrica: [i][j] == [j][i].

import math

# Ordre fix dels nodes: cadascun rep un index 0..8
NODES = ["ALM", "MER", "EST", "UNI", "RIO", "CEN", "IND", "HOS", "PAR"]
IDX = {nom: i for i, nom in enumerate(NODES)}  # "ALM" -> 0, "MER" -> 1, ...

ARESTES = [
    ("ALM", "RIO", 3), ("ALM", "MER", 4), ("ALM", "EST", 7), ("ALM", "CEN", 12),
    ("MER", "CEN", 5), ("MER", "UNI", 6), ("EST", "UNI", 3), ("EST", "IND", 9),
    ("UNI", "CEN", 8), ("UNI", "HOS", 5), ("RIO", "CEN", 6), ("RIO", "PAR", 8),
    ("CEN", "HOS", 4), ("IND", "HOS", 6), ("PAR", "HOS", 7),
]

n = len(NODES)
# math.inf significa "no hi ha carrer directe"; la diagonal val 0 (d'una zona a si mateixa)
matriu = [[math.inf] * n for _ in range(n)]
for i in range(n):
    matriu[i][i] = 0

for u, v, pes in ARESTES:
    i, j = IDX[u], IDX[v]
    matriu[i][j] = pes
    matriu[j][i] = pes   # no dirigit: el carrer funciona en tots dos sentits

print(matriu[IDX["ALM"]][IDX["CEN"]])  # 12  -> hi ha avinguda directa, triga 12 min
print(matriu[IDX["ALM"]][IDX["HOS"]])  # inf -> no hi ha tram directe ALM-HOS

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

  • IDX tradueix noms llegibles ("ALM") a índexs de matriu (0). És el mateix truc dict→índex que vam fer servir amb les taules de hash a 01-04.
  • [[math.inf] * n for _ in range(n)] crea n files independents. Compte amb l'error clàssic [[inf]*n]*n, que crea n referències a la mateixa fila (hi tornem a Errors Comuns).
  • Consultar si existeix una aresta és un accés directe: O(1). Aquesta és la gran virtut de la matriu.
  • El preu: O(n²) de memòria encara que el graf tingui poques arestes, i recórrer els veïns d'un node obliga a escanejar tota la seva fila: O(n).

Llista d'adjacència

La llista d'adjacència guarda, per a cada node, només la llista dels seus veïns (amb el pes). En Python la manera més natural és un diccionari de diccionaris:

from collections import defaultdict

def construir_graf(arestes, dirigit=False):
    """Construeix una llista d'adjacencia: {node: {vei: pes}}."""
    graf = defaultdict(dict)
    for u, v, pes in arestes:
        graf[u][v] = pes
        if not dirigit:
            graf[v][u] = pes  # doble sentit
    return dict(graf)

XARXA = construir_graf(ARESTES)

print(XARXA["ALM"])   # {'RIO': 3, 'MER': 4, 'EST': 7, 'CEN': 12}
print(XARXA["IND"])   # {'EST': 9, 'HOS': 6}

# Hi ha tram directe MER-UNI? Acces per hash, O(1) esperat:
print("UNI" in XARXA["MER"])          # True
print(XARXA["MER"].get("HOS"))        # None -> no hi ha carrer directe

# Recorrer els veins d'un node: proporcional al seu grau, no a n
for vei, minuts in XARXA["CEN"].items():
    print(f"CEN -> {vei}: {minuts} min")

Observacions:

  • defaultdict(dict) evita comprovar "existeix ja la clau?" a cada inserció; al final el convertim a dict normal per congelar l'estructura.
  • Fem servir {vei: pes} en lloc d'una llista de tuples [(vei, pes), ...] perquè així la consulta "hi ha aresta u–v?" també és O(1) esperat gràcies al hash (llavor de 01-04). Amb llistes de tuples seria O(grau).
  • Memòria: O(n + m) — exactament proporcional al que existeix. Per a la xarxa de Rutalia tant se val (9 nodes), però per a la xarxa de carrers completa d'una gran ciutat (centenars de milers de cruïlles, grau mitjà ~3) la matriu seria inviable: 10⁵ nodes ⇒ 10¹⁰ cel·les.

Comparativa: quan convé cada representació

Operació Matriu d'adjacència Llista d'adjacència (dict de dicts)
Memòria O(n²) O(n + m)
Existeix l'aresta (u,v)? O(1) O(1) esperat (hash)
Pes de (u,v) O(1) O(1) esperat
Recórrer els veïns d'u O(n) O(deg(u))
Recórrer totes les arestes O(n²) O(n + m)
Afegir una aresta O(1) O(1) esperat
Afegir un node O(n²) (redimensionar) O(1)

Regla pràctica:

  • Llista d'adjacència: l'opció per defecte, i la ideal en grafs dispersos com les xarxes viàries. Gairebé tots els algorismes del mòdul (BFS, DFS, Dijkstra, Kruskal, Prim, flux) la fan servir perquè la seva feina dominant és "recórrer veïns".
  • Matriu: guanya quan el graf és dens, quan n és petit, o quan l'algorisme consulta pesos entre parells arbitraris constantment. Floyd-Warshall (03-03) treballa directament sobre la matriu — de fet, és programació dinàmica sobre ella.

Et sona, la matriu? A 02-02, la instància canònica del TSP es recolzava en una matriu de distàncies entre les 10 parades. Allò era una matriu d'adjacència d'un graf complet (tot connectat amb tot): dens al màxim, i per això la matriu hi era l'elecció correcta.

Grafs implícits: la quadrícula de 01-03 era un graf sense saber-ho

No sempre cal construir l'estructura en memòria. Un graf implícit és aquell els nodes i arestes del qual es calculen sota demanda amb una funció veins(estat).

L'exemple el tenim al mateix curs: a 01-03 vam resoldre el cost mínim per creuar la quadrícula de la ciutat amb programació dinàmica. Cada casella (i, j) era un node; els moviments permesos (dreta, avall) eren arestes dirigides amb pes igual al cost de la casella destinació. Mai no vam emmagatzemar "el graf": el generàvem en moure'ns.

def veins_quadricula(casella, files, columnes):
    """Graf implicit: les arestes es generen quan es demanen, no s'emmagatzemen."""
    i, j = casella
    if j + 1 < columnes:
        yield (i, j + 1)   # moure a la dreta
    if i + 1 < files:
        yield (i + 1, j)   # moure avall

Aquesta idea escala a espais enormes (estats d'un trencaclosques, configuracions d'una flota) on materialitzar el graf seria impossible; la cerca en espais d'estats de 04-03 en viu. L'important: tots els algorismes d'aquest mòdul només necessiten saber demanar "els veïns d'u" — tant els fa que vinguin d'un dict o d'una funció.

Una nota sobre networkx

En un entorn professional rarament reimplementaràs aquestes estructures: la llibreria networkx ofereix grafs dirigits/no dirigits/ponderats amb desenes d'algorismes ja provats.

import networkx as nx

G = nx.Graph()                       # nx.DiGraph() per a dirigits
G.add_weighted_edges_from(ARESTES)   # accepta (u, v, pes) directament
print(G["ALM"])                      # vista d'adjacencia, com el nostre dict
print(nx.is_connected(G))            # True

En aquest curs implementem l'essencial a mà —és l'única manera d'entendre de debò els costos i les fallades de cada algorisme—, i farem servir llibreries (networkx, scipy) com a verificació o com a eina final, igual que vam fer amb scipy.optimize.linprog a 02-01.

Errors Comuns i Consells

  • Crear la matriu amb [[inf] * n] * n: la multiplicació externa duplica referències a la mateixa llista; en escriure matriu[0][3] canvien "totes les files". Fes servir sempre la comprensió [[inf] * n for _ in range(n)].
  • Oblidar l'aresta inversa en grafs no dirigits: si només insereixes graf[u][v], el teu "carrer de doble sentit" es torna de sentit únic i BFS/Dijkstra donaran resultats absurds. Centralitza la construcció en una funció (com construir_graf) i no insereixis arestes a mà.
  • Nodes aïllats invisibles: amb defaultdict, un node sense arestes no apareix com a clau. Si el teu problema admet zones sense connexió, inicialitza explícitament totes les claus o guarda a part el conjunt V.
  • Confondre dens i dispers en triar estructura: abans de programar, estima m davant de n². Xarxa viària ⇒ dispersa ⇒ llista. Matriu de distàncies tot-amb-tot (TSP, Floyd-Warshall) ⇒ densa ⇒ matriu.
  • Mutar un defaultdict en consultar-lo: XARXA["ZONA_INEXISTENT"] sobre un defaultdict crea la clau buida com a efecte secundari. Per això el convertim a dict en acabar la construcció.
  • Consell: acostuma't a validar invariants barats després de construir el graf (suma de graus = 2m, pesos positius si l'algorisme ho exigeix). Cinc línies d'assert estalvien hores de depuració.

Exercicis

  1. Graus de la xarxa canònica. Escriu una funció graus(graf) que, a partir de la llista d'adjacència XARXA, retorni un dict {node: grau}. Fes-la servir per verificar que la suma de graus és 2m i per trobar la zona més ben connectada i la més fràgil de Rutalia.
  2. Conversió entre representacions. Escriu llista_a_matriu(graf, nodes) que converteixi la llista d'adjacència en matriu (amb math.inf per a les absències i 0 a la diagonal) i matriu_a_llista(matriu, nodes) amb la conversió inversa. Comprova que l'anada i tornada retornen el graf original.
  3. Versió dirigida. Rutalia descobreix que el tram RIO→CEN passa a ser de sentit únic (només de RIO cap a CEN) per obres. Construeix la xarxa com a graf dirigit (cada carrer de doble sentit són dues arestes dirigides, i RIO–CEN només una) i escriu una funció que retorni el grau d'entrada i de sortida de cada zona. Quina zona perd accessibilitat?

Solucions

Exercici 1:

def graus(graf):
    return {node: len(veins) for node, veins in graf.items()}

g = graus(XARXA)
assert sum(g.values()) == 2 * len(ARESTES)          # 30 == 2 * 15
print(max(g, key=g.get))   # CEN (grau 5): la mes ben connectada
print(min(g, key=g.get))   # IND o PAR (grau 2): les mes fragils

Com que cada veí de la llista d'adjacència correspon exactament a una aresta incident, len(veins) és directament el grau. max(g, key=g.get) retorna la clau el valor de la qual és màxim.

Exercici 2:

import math

def llista_a_matriu(graf, nodes):
    idx = {nom: i for i, nom in enumerate(nodes)}
    n = len(nodes)
    M = [[math.inf] * n for _ in range(n)]
    for i in range(n):
        M[i][i] = 0
    for u, veins in graf.items():
        for v, pes in veins.items():
            M[idx[u]][idx[v]] = pes
    return M

def matriu_a_llista(M, nodes):
    graf = {node: {} for node in nodes}
    for i, u in enumerate(nodes):
        for j, v in enumerate(nodes):
            if i != j and M[i][j] != math.inf:
                graf[u][v] = M[i][j]
    return graf

M = llista_a_matriu(XARXA, NODES)
assert matriu_a_llista(M, NODES) == XARXA

Nota: com que la llista d'adjacència ja guarda cada aresta no dirigida en tots dos sentits, no cal simetritzar res: la matriu surt simètrica tota sola.

Exercici 3:

def construir_dirigit(arestes, sentit_unic):
    graf = {n: {} for n in NODES}
    for u, v, p in arestes:
        if (u, v) in sentit_unic:
            graf[u][v] = p          # nomes u -> v
        elif (v, u) in sentit_unic:
            graf[v][u] = p
        else:
            graf[u][v] = p          # doble sentit: dues arestes dirigides
            graf[v][u] = p
    return graf

D = construir_dirigit(ARESTES, sentit_unic={("RIO", "CEN")})

grau_sortida = {n: len(vs) for n, vs in D.items()}
grau_entrada = {n: 0 for n in NODES}
for u, vs in D.items():
    for v in vs:
        grau_entrada[v] += 1

print(grau_entrada["RIO"], grau_sortida["RIO"])  # 2, 3

RIO perd accessibilitat d'entrada: abans s'hi podia arribar des d'ALM, CEN i PAR (grau 3); ara des de CEN ja no (grau d'entrada 2), tot i que des de RIO se segueixi podent sortir cap als tres. En dirigits, entrada i sortida expliquen històries diferents.

Conclusió

El deute està saldat: les rutes de Rutalia ja són matemàtiques de primera classe. Un graf és un parell (V, E), amb variants dirigides i ponderades; es representa amb matriu d'adjacència (O(n²) de memòria, consulta O(1), ideal per a grafs densos com la matriu del TSP) o amb llista d'adjacència (O(n+m), recorregut de veïns proporcional al grau, l'opció per defecte en xarxes disperses com el mapa de carrers d'una ciutat). I a vegades ni tan sols s'emmagatzema: la quadrícula de 01-03 era un graf implícit. Sobre la taula queda el graf canònic de Rutalia: 9 zones, 15 trams en minuts, amb una avinguda parany (ALM–CEN, 12 min) que ja insinua la pregunta de la propera lliçó. Perquè tenir la xarxa en memòria no serveix de res si no sabem recórrer-la: a 03-02 aprendrem BFS i DFS, els dos ordres fonamentals d'exploració, i amb ells respondrem preguntes operatives reals: quines zones queden abastables si es talla un carrer?, a quants trams és el punt de lliurament més llunyà?

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