Al final del módulo anterior dejamos una deuda deliberada: cinco lecciones hablando de rutas, tramos y "aristas" —la feromona de las hormigas vivía literalmente sobre ellas— sin definir formalmente qué es esa estructura. Ha llegado el momento de saldarla. En esta lección definimos con rigor qué es un grafo, aprendemos las dos formas clásicas de representarlo en memoria (matriz y lista de adyacencia), analizamos cuándo conviene cada una, y presentamos el grafo canónico de la red urbana de Rutalia, que será nuestro campo de pruebas durante todo el módulo 3, igual que la instancia del TSP lo fue en el módulo 2. Elegir bien la representación no es un detalle estético: determina la complejidad de todos los algoritmos que veremos después.

1. Definición formal: vértices, aristas y variantes
2. Vocabulario esencial: grado, caminos, ciclos y conexión
3. El grafo canónico de la red urbana de Rutalia
4. Matriz de adyacencia
5. Lista de adyacencia
6. Comparativa: cuándo usar cada representación
7. Grafos implícitos: la cuadrícula de 01-03 era un grafo sin saberlo
8. Una nota sobre networkx

Un grafo es un par G = (V, E) donde:

• V es un conjunto finito de vértices o nodos. En Rutalia: cruces, plazas, zonas de la ciudad, puntos de entrega.
• E es un conjunto de aristas, cada una conectando un par de vértices. En Rutalia: tramos de calle transitables entre dos puntos.

Sobre esta base mínima se construyen las variantes que necesitaremos:

• Grafo no dirigido: las aristas son pares no ordenados {u, v}. Si se puede ir de la Plaza del Mercado al Almacén, también al revés. Una calle de doble sentido.
• Grafo dirigido (digrafo): las aristas son pares ordenados (u, v); la relación va de u hacia v. Una calle de sentido único. Las dependencias entre tareas (03-02) y las redes de flujo (03-05) son dirigidas por naturaleza.
• Grafo ponderado: cada arista lleva asociado un peso w(u, v): minutos de trayecto, kilómetros, coste, capacidad. Sin pesos, todas las calles "cuestan" lo mismo; con pesos, la ciudad se vuelve realista.

Notación de tamaños que usaremos siempre: |V| = n (número de nodos) y |E| = m (número de aristas). En un grafo no dirigido sin aristas repetidas, m puede llegar como máximo a n(n−1)/2, es decir, O(n²). Un grafo con m cercano a n² se llama denso; con m cercano a n, disperso (sparse). Las redes de calles reales son muy dispersas: cada cruce conecta con 3 o 4 calles, no con miles.

• Adyacencia: u y v son adyacentes (vecinos) si existe la arista {u, v}.
• Grado de un vértice, deg(v): número de aristas que inciden en él. En dirigidos se separa en grado de entrada (aristas que llegan) y grado de salida (aristas que salen). Propiedad útil para detectar errores: en un grafo no dirigido, la suma de todos los grados es exactamente 2m (cada arista aporta 2).
• Camino: secuencia de vértices v₀, v₁, …, vₖ donde cada par consecutivo está unido por una arista. Su longitud es el número de aristas (k) o, en ponderados, la suma de pesos. Un camino es simple si no repite vértices.
• Ciclo: camino que empieza y termina en el mismo vértice sin repetir aristas. Un grafo dirigido sin ciclos se llama DAG (Directed Acyclic Graph); serán clave en la ordenación topológica de 03-02.
• Grafo conexo (no dirigido): existe un camino entre cualquier par de vértices. Si no lo es, se descompone en componentes conexas — trozos de ciudad incomunicados entre sí. Ya calculamos componentes en 01-04 con union-find; en 03-02 lo haremos también con búsqueda y compararemos.
• Árbol: grafo conexo y sin ciclos. Tiene exactamente n−1 aristas. Los árboles de expansión de 03-04 son esto: el esqueleto mínimo que mantiene todo conectado.

Igual que el módulo 2 fijó su instancia canónica del TSP (9 paradas + depósito, óptimo 35,22 km), este módulo fija su red urbana canónica: 9 zonas de la ciudad y 15 tramos de calle de doble sentido, ponderados en minutos de furgoneta. Todos los datos son ficticios.

Detalles con intención, que explotaremos en las próximas lecciones:

• La arista ALM–CEN con peso 12 es la gran avenida directa al Centro Histórico: un solo tramo, pero congestionado. Adelanto: ir por Mercado (ALM→MER→CEN = 4+5 = 9 min) es más rápido que la "línea recta". Esta tensión entre menos tramos y menos minutos es exactamente la diferencia entre BFS (03-02) y Dijkstra (03-03).
• El Polígono Industrial (IND) solo tiene 2 conexiones (grado 2): es la zona más frágil ante cortes de calle.
• El Centro Histórico (CEN) es el nodo de mayor grado (5): el corazón de la red.

Comprobación rápida de la propiedad de los grados: 4+3+3+4+3+5+2+4+2 = 30 = 2·15 ✓.

La matriz de adyacencia es una tabla n×n donde la celda [i][j] guarda el peso de la arista i→j (o un valor especial —0, None, inf— si no existe). En un grafo no dirigido, la matriz es simétrica: [i][j] == [j][i].

Puntos que conviene entender línea a línea:

• IDX traduce nombres legibles ("ALM") a índices de matriz (0). Es el mismo truco dict→índice que usamos con las tablas hash en 01-04.
• [[math.inf] * n for _ in range(n)] crea n filas independientes. Cuidado con el error clásico [[inf]*n]*n, que crea n referencias a la misma fila (lo retomamos en Errores Comunes).
• Consultar si existe una arista es un acceso directo: O(1). Esa es la gran virtud de la matriz.
• El precio: O(n²) de memoria aunque el grafo tenga pocas aristas, y recorrer los vecinos de un nodo obliga a escanear toda su fila: O(n).

La lista de adyacencia guarda, para cada nodo, solo la lista de sus vecinos (con el peso). En Python la forma más natural es un diccionario de diccionarios:

Observaciones:

• defaultdict(dict) evita comprobar "¿existe ya la clave?" en cada inserción; al final lo convertimos a dict normal para congelar la estructura.
• Usamos {vecino: peso} en lugar de una lista de tuplas [(vecino, peso), ...] porque así la consulta "¿hay arista u–v?" también es O(1) esperado gracias al hash (semilla de 01-04). Con listas de tuplas sería O(grado).
• Memoria: O(n + m) — exactamente proporcional a lo que existe. Para la red de Rutalia da igual (9 nodos), pero para el callejero completo de una gran ciudad (cientos de miles de cruces, grado medio ~3) la matriz sería inviable: 10⁵ nodos ⇒ 10¹⁰ celdas.

Regla práctica:

• Lista de adyacencia: la opción por defecto, y la ideal en grafos dispersos como las redes viarias. Casi todos los algoritmos del módulo (BFS, DFS, Dijkstra, Kruskal, Prim, flujo) la usan porque su trabajo dominante es "recorrer vecinos".
• Matriz: gana cuando el grafo es denso, cuando n es pequeño, o cuando el algoritmo consulta pesos entre pares arbitrarios constantemente. Floyd-Warshall (03-03) trabaja directamente sobre la matriz — de hecho, es programación dinámica sobre ella.

¿Te suena la matriz? En 02-02, la instancia canónica del TSP se apoyaba en una matriz de distancias entre las 10 paradas. Aquello era una matriz de adyacencia de un grafo completo (todo conectado con todo): denso al máximo, y por eso la matriz era la elección correcta allí.

No siempre hace falta construir la estructura en memoria. Un grafo implícito es aquel cuyos nodos y aristas se calculan bajo demanda con una función vecinos(estado).

El ejemplo lo tenemos en el propio curso: en 01-03 resolvimos el coste mínimo para cruzar la cuadrícula de la ciudad con programación dinámica. Cada celda (i, j) era un nodo; los movimientos permitidos (derecha, abajo) eran aristas dirigidas con peso igual al coste de la celda destino. Nunca almacenamos "el grafo": lo generábamos al movernos.

Esta idea escala a espacios enormes (estados de un puzle, configuraciones de una flota) donde materializar el grafo sería imposible; la búsqueda en espacios de estados de 04-03 vive de ella. Lo importante: todos los algoritmos de este módulo solo necesitan saber pedir "los vecinos de u" — les da igual que vengan de un dict o de una función.

En un entorno profesional rara vez reimplementarás estas estructuras: la librería networkx ofrece grafos dirigidos/no dirigidos/ponderados con decenas de algoritmos ya probados.

En este curso implementamos lo esencial a mano —es la única forma de entender de verdad los costes y los fallos de cada algoritmo—, y usaremos librerías (networkx, scipy) como verificación o como herramienta final, igual que hicimos con scipy.optimize.linprog en 02-01.

• Crear la matriz con [[inf] * n] * n: la multiplicación externa duplica referencias a la misma lista; al escribir matriz[0][3] cambian "todas las filas". Usa siempre la comprensión [[inf] * n for _ in range(n)].
• Olvidar la arista inversa en grafos no dirigidos: si solo insertas grafo[u][v], tu "calle de doble sentido" se vuelve de sentido único y BFS/Dijkstra darán resultados absurdos. Centraliza la construcción en una función (como construir_grafo) y no insertes aristas a mano.
• Nodos aislados invisibles: con defaultdict, un nodo sin aristas no aparece como clave. Si tu problema admite zonas sin conexión, inicializa explícitamente todas las claves o guarda aparte el conjunto V.
• Confundir denso y disperso al elegir estructura: antes de programar, estima m frente a n². Red viaria ⇒ dispersa ⇒ lista. Matriz de distancias todo-con-todo (TSP, Floyd-Warshall) ⇒ densa ⇒ matriz.
• Mutar un defaultdict al consultarlo: RED["ZONA_INEXISTENTE"] sobre un defaultdict crea la clave vacía como efecto secundario. Por eso lo convertimos a dict al terminar la construcción.
• Consejo: acostúmbrate a validar invariantes baratos tras construir el grafo (suma de grados = 2m, pesos positivos si el algoritmo lo exige). Cinco líneas de assert ahorran horas de depuración.

1. Grados de la red canónica. Escribe una función grados(grafo) que, a partir de la lista de adyacencia RED, devuelva un dict {nodo: grado}. Úsala para verificar que la suma de grados es 2m y para encontrar la zona mejor conectada y la más frágil de Rutalia.
2. Conversión entre representaciones. Escribe lista_a_matriz(grafo, nodos) que convierta la lista de adyacencia en matriz (con math.inf para ausencias y 0 en la diagonal) y matriz_a_lista(matriz, nodos) con la conversión inversa. Comprueba que ida y vuelta devuelven el grafo original.
3. Versión dirigida. Rutalia descubre que el tramo RIO→CEN pasa a ser de sentido único (solo de RIO hacia CEN) por obras. Construye la red como grafo dirigido (cada calle de doble sentido son dos aristas dirigidas, y RIO–CEN solo una) y escribe una función que devuelva el grado de entrada y salida de cada zona. ¿Qué zona pierde accesibilidad?

Ejercicio 1:

Como cada vecino de la lista de adyacencia corresponde a exactamente una arista incidente, len(vecinos) es directamente el grado. max(g, key=g.get) devuelve la clave cuyo valor es máximo.

Ejercicio 2:

Nota: como la lista de adyacencia ya guarda cada arista no dirigida en ambos sentidos, no hace falta simetrizar nada: la matriz sale simétrica sola.

Ejercicio 3:

RIO pierde accesibilidad de entrada: antes se podía llegar desde ALM, CEN y PAR (grado 3); ahora desde CEN ya no (grado de entrada 2), aunque desde RIO se siga pudiendo salir hacia los tres. En dirigidos, entrada y salida cuentan historias distintas.

La deuda está saldada: las rutas de Rutalia ya son matemáticas de primera clase. Un grafo es un par (V, E), con variantes dirigidas y ponderadas; se representa con matriz de adyacencia (O(n²) de memoria, consulta O(1), ideal para grafos densos como la matriz del TSP) o con lista de adyacencia (O(n+m), recorrido de vecinos proporcional al grado, la opción por defecto en redes dispersas como un callejero). Y a veces ni siquiera se almacena: la cuadrícula de 01-03 era un grafo implícito. Sobre la mesa queda el grafo canónico de Rutalia: 9 zonas, 15 tramos en minutos, con una avenida trampa (ALM–CEN, 12 min) que ya insinúa la pregunta de la próxima lección. Porque tener la red en memoria no sirve de nada si no sabemos recorrerla: en 03-02 aprenderemos BFS y DFS, los dos órdenes fundamentales de exploración, y con ellos responderemos a preguntas operativas reales: ¿qué zonas quedan alcanzables si se corta una calle?, ¿a cuántos tramos está el punto de entrega más lejano?