Grafo: lista de adyacencia y matriz
En resumen: Un grafo es un conjunto de vértices y aristas; en un programa se guarda como lista de adyacencia con O(V + E) de memoria o como matriz de adyacencia con O(V²).
Problema
La tabla que no cabe
Una empresa de mensajería guarda la red de calles de la ciudad en una tabla: una fila y una columna por cada cruce, y la celda vale 1 si hay una calle entre los dos. Cuando la empresa trabajaba en un solo barrio con 300 cruces, la tabla tenía 90 000 celdas y nadie se quejaba.
Luego la empresa cubrió toda la ciudad: 40 000 cruces. La tabla pasó a ser de 40 000 × 40 000 = 1600 millones de celdas. Incluso con un byte por celda son 1,6 GB, y el servidor empezó a caerse cada vez que cargaba el mapa.
Lo más irritante es que casi todo en la tabla es 0. De un cruce salen tres o cuatro calles, no 40 000. ¿Cómo guardas solo las calles que existen?
La idea
Paradas y calles: un grafo
El mapa de reparto se describe con dos cosas: paradas (cruces, almacenes, direcciones) y las calles entre ellas. Eso se llama grafo. Las paradas son sus vértices y las calles son sus aristas. El número de vértices se escribe V y el de aristas E.
- Grafo no dirigido: la calle va en los dos sentidos. Si hay camino de Estación a Plaza, hay uno de vuelta.
- Grafo dirigido: calles de un solo sentido. Una arista Estación → Plaza no da camino Plaza → Estación.
- Grafo ponderado: cada arista lleva un número: longitud en metros, minutos, un precio en €.
Esta es nuestra ciudad: 8 paradas y 9 calles de doble sentido. El río la divide en dos partes, unidas por dos puentes. Así llega el grafo desde el sistema de la empresa: una lista de las paradas y una lista de las calles (un par de nombres por fila).
stops = [ "Almacén", "Estación", "Mercado", "Plaza", "Parque", "Cine", "Hospital", "Estadio",]streets = [ ("Almacén", "Estación"), ("Almacén", "Mercado"), ("Estación", "Plaza"), ("Mercado", "Plaza"), ("Mercado", "Parque"), ("Plaza", "Cine"), ("Cine", "Hospital"), ("Parque", "Estadio"), ("Hospital", "Estadio"),]Necesitarás la misma ciudad en todo el módulo: para la ruta más corta, para las islas tras cerrar un puente y, más adelante, para Dijkstra.
La idea
Dos formas de guardarlo
Matriz de adyacencia. Numeras las paradas de 0 a V − 1. La tabla es V × V, y la celda [i][j] dice si hay una calle de i a j. Es la tabla del problema.
Lista de adyacencia. Para cada parada guardas solo la lista de sus vecinos. En código es un diccionario de un nombre a una lista: un dict de nombre a lista. No hay huecos vacíos: una calle que no existe no ocupa nada.
Las dos se construyen a partir de la misma lista de calles, en el mismo bucle.
Míralo
Una calle, dos entradas
graph = {stop: [] for stop in stops}index = {stop: i for i, stop in enumerate(stops)}matrix = [[False] * len(stops) for _ in stops]for a, b in streets: graph[a].append(b) graph[b].append(a) i, j = index[a], index[b] matrix[i][j] = matrix[j][i] = TruePaso a paso, en palabras
- Ocho paradas, todavía sin calles. Cada una recibe una lista vacía y un número: su fila y su columna en la matriz de 8 × 8, toda con ceros.
- La primera calle, Almacén – Estación: Estación entra en la lista de Almacén, y Almacén en la lista de Estación. En la matriz dos celdas pasan a 1: [0][1] y [1][0].
- Almacén – Mercado: Mercado va después de Estación en la lista de Almacén. El orden en una lista es el orden de las calles.
- Una calle de doble sentido se anota dos veces: en las dos listas y en las dos celdas. Por eso la matriz es simétrica respecto a la diagonal.
- Mercado – Parque y Plaza – Cine cruzan el río. Mercado y Plaza ya tienen tres vecinos cada una; las demás, dos.
- Las últimas calles de la otra orilla. Cada lista crece solo con sus calles reales.
- 9 calles: 18 entradas en las listas, 64 celdas en la matriz, 46 de ellas con cero. Con 40 000 cruces son unas 120 000 entradas frente a 1600 millones de celdas.
El programa completo imprime las listas y la matriz:
for stop in stops: print(stop + ": " + ", ".join(graph[stop]))for row in matrix: print(" ".join("1" if cell else "0" for cell in row))Almacén: Estación, MercadoEstación: Almacén, PlazaMercado: Almacén, Plaza, ParquePlaza: Estación, Mercado, CineParque: Mercado, EstadioCine: Plaza, HospitalHospital: Cine, EstadioEstadio: Parque, Hospital0 1 1 0 0 0 0 01 0 0 1 0 0 0 01 0 0 1 1 0 0 00 1 1 0 0 1 0 00 0 1 0 0 0 0 10 0 0 1 0 0 1 00 0 0 0 0 1 0 10 0 0 0 1 0 1 0La lista de cada parada sigue el orden en que llegaron las calles. La matriz es simétrica: la fila 2 y la columna 2 son iguales, porque cada calle va en los dos sentidos.
Pruébalo
Predice la salida
Tres calles alrededor de Plaza, en otro orden. ¿Qué imprime el programa?
streets = [ ("Mercado", "Plaza"), ("Plaza", "Cine"), ("Estación", "Plaza"),]graph = {stop: [] for stop in stops}for a, b in streets: graph[a].append(b) graph[b].append(a)print(", ".join(graph["Plaza"]))Pruébalo
Completa
Una calle de doble sentido hay que escribirla en las dos celdas:
for a, b in streets:
i, j = index[a], index[b]
matrix[i][j] = = TrueLa celda [i][j] es la calle de i a j, y [j][i] es la misma calle de vuelta. En un grafo no dirigido las dos son siempre iguales.
La idea
Lo que cuesta
Las tres preguntas que la app de mensajería hace todo el tiempo cuestan cosas distintas:
| matriz | lista de adyacencia | |
|---|---|---|
| memoria | V² celdas | V listas y 2E entradas: O(V + E) |
| ¿hay una calle entre a y b? | una celda: O(1) | un recorrido por los vecinos de a: O(vecinos) |
| ¿quiénes son los vecinos de a? | la fila entera: O(V) | solo los vecinos: O(vecinos) |
El programa recorre los vecinos de cada parada de las dos formas y cuenta cada vistazo: en la matriz cada celda, en la lista cada parada y cada entrada.
matrix_looks = matrix_found = 0for i in range(len(stops)): for j in range(len(stops)): matrix_looks += 1 if matrix[i][j]: matrix_found += 1list_looks = list_found = 0for stop in stops: list_looks += 1 for nxt in graph[stop]: list_looks += 1 list_found += 1print(f"Matriz: {matrix_looks} vistazos, {matrix_found} vecinos")print(f"Lista: {list_looks} vistazos, {list_found} vecinos")in_matrix = matrix[index["Mercado"]][index["Parque"]]in_list = "Parque" in graph["Mercado"]print(f"¿Hay una calle Mercado - Parque? {in_matrix} {in_list}")Matriz: 64 vistazos, 18 vecinosLista: 26 vistazos, 18 vecinos¿Hay una calle Mercado - Parque? True TrueCon 8 paradas la diferencia es pequeña. Ejecuta lo mismo en una ciudad en cuadrícula de n cruces, cada uno unido a su vecino de la derecha y al de abajo:
- Matriz: toda la fila de cada cruce
O(n²) - Lista de adyacencia: solo las calles reales
O(n)
| Algoritmo | n = 10 | n = 1000 | n = 5000 | n = 100.000 |
|---|---|---|---|---|
| Matriz: toda la fila de cada cruce | 100 | 1.000.000 | 25.000.000 | ≈ 10.000.000.000 |
| Lista de adyacencia: solo las calles reales | 36 | 4872 | 24.716 | 498.734 |
matrix_looks = matrix_found = 0for i in range(len(stops)): for j in range(len(stops)): matrix_looks += 1 if matrix[i][j]: matrix_found += 1list_looks = list_found = 0for stop in stops: list_looks += 1 for nxt in graph[stop]: list_looks += 1 list_found += 1print(f"Matriz: {matrix_looks} vistazos, {matrix_found} vecinos")print(f"Lista: {list_looks} vistazos, {list_found} vecinos")in_matrix = matrix[index["Mercado"]][index["Parque"]]in_list = "Parque" in graph["Mercado"]print(f"¿Hay una calle Mercado - Parque? {in_matrix} {in_list}")Con 1000 cruces la matriz hace 1 000 000 de vistazos y la lista 4872. Con 5000 la matriz ya está en 25 000 000 y la lista en 24 716. Estos números son también la memoria: la matriz guarda n² celdas, la lista tantas entradas como vistazos hace.
Por eso los mapas de ciudades, las redes sociales y las dependencias entre paquetes se guardan como listas de adyacencia. Son grafos dispersos: E es del orden de V, no de V².
Más precisamente, para curiosos
La matriz gana cuando el grafo es denso: casi todos están conectados con casi todos, por ejemplo una tabla de distancias entre 50 almacenes. Entonces V² celdas no son un desperdicio, y «¿hay una arista?» es una celda. También hay un término medio: una lista de adyacencia con un conjunto (set) en lugar de una lista responde «¿hay una calle?» en O(1) de media, al precio de más memoria por entrada.
La idea
Sentido y longitud
En el sistema real una calle viene con una longitud, y algunas calles son de un solo sentido. La lista de adyacencia guarda entonces un par: hacia dónde y cuántos metros. El sistema las envía como texto, una calle por fila: «de a metros».
lines = [ "Almacén Estación 400", "Almacén Mercado 300", "Estación Plaza 500", # …]graph = {stop: [] for stop in stops}for line in lines: a, b, meters = line.split() graph[a].append((b, int(meters))) graph[b].append((a, int(meters)))(b, meters). split() parte la fila en tres, e int convierte los metros en número.text = ", ".join(f"{to} {meters} m" for to, meters in graph["Mercado"])print("Mercado" + ": " + text)Mercado: Almacén 300 m, Plaza 350 m, Parque 600 mUna calle de un solo sentido es solo el primer add: b entra en la lista de a, no al revés. En la matriz solo se rellena [i][j], y deja de ser simétrica. En una matriz ponderada la celda guarda la longitud, y una calle ausente es un valor especial, por ejemplo infinito.
Pruébalo
Encuentra el error
Un compañero construye la lista de adyacencia. El programa imprime:
graph = {stop: [] for stop in stops}for a, b in streets: graph[a].append(b) graph[b].append(b)Almacén: Estación, MercadoEstación: Estación, PlazaMercado: Mercado, Plaza, ParquePlaza: Plaza, Plaza, CineParque: Parque, EstadioCine: Cine, HospitalHospital: Hospital, EstadioEstadio: Estadio, EstadioEstación resulta ser su propia vecina, y Almacén falta en su lista. ¿Qué línea tiene el error?
Elige la línea con el error.
El segundo sentido tiene que poner a en la lista de b: graph[b].append(a). Ahora cada calle escribe b en su propia lista. El camino de Almacén a Estación está, el de vuelta no, como si todas las calles fueran de un solo sentido, más una «calle» de cada parada a sí misma.
Más precisamente
Cómo es en los otros lenguajes
- Trampa:
[[False] * n] * ncrea n referencias a la misma fila. Cambiamatrix[0][1]y la columna 1 cambia en todas las filas. Por eso la matriz se crea con[[False] * n for _ in range(n)]. - Cada celda de una lista es una referencia (8 bytes), aunque el valor sea
False. Una matriz de listas de 40 000 × 40 000 son unos 12,8 GB solo en referencias. Para tablas numéricas existenbytearrayo los arreglos de NumPy. collections.defaultdict(list)crea la lista vacía por sí mismo en la primera calle:graph[a].append(b)sin el bucle anterior.
Ejercicio
Calles y metros
Resuelve la tarea en tu editor.
Las calles de una parada. El sistema envía las calles de doble sentido como filas «de a metros», y las de un solo sentido por separado:
lines = [ "Almacén Estación 400", "Almacén Mercado 300", "Estación Plaza 500", "Mercado Plaza 350", "Mercado Parque 600", "Plaza Cine 450", "Cine Hospital 300", "Parque Estadio 500", "Hospital Estadio 250",]one_way = [ "Estación Mercado 650", "Estadio Cine 550",]Construye el grafo ponderado: las calles de doble sentido entran en las dos listas, las de un solo sentido solo en la lista de la primera parada. Para cada parada imprime cuántas calles salen de ella y cuántos metros suman, y al final la parada con más calles (en caso de empate, la primera en el orden):
Almacén: 2 calles, 700 mEstación: 3 calles, 1550 mMercado: 3 calles, 1250 mPlaza: 3 calles, 1300 mParque: 2 calles, 1100 mCine: 2 calles, 750 mHospital: 2 calles, 550 mEstadio: 3 calles, 1300 mMás calles: Estación (3)Más tareas
- Callejones sin salida. Imprime las paradas de las que sale una sola calle.
- Matriz con metros. Construye una matriz en la que la celda es la longitud de la calle, o -1 si no hay calle, e imprímela.
- El otro sentido. A partir del grafo con las calles de un solo sentido construye el inverso: cada arista a → b pasa a ser b → a. ¿Cuál de los dos necesitas si preguntas «desde qué paradas se llega al Hospital»?
Test