3 - Representaciones de grafos en Python

Elegir cómo guardar un grafo en memoria cambia la complejidad de las operaciones. En Python predominan dos estructuras: la matriz de adyacencia y la lista de adyacencia. Este tema compara ambas, sus costos y los escenarios donde conviene cada una.

3.1 Matriz de adyacencia

Se usa un arreglo bidimensional n x n donde n es la cantidad de vértices. Cada celda [u][v] indica si existe arista de u a v (o almacena el peso si el grafo es ponderado).

n = 4
matriz = [
  [0, 3, 0, 1],
  [3, 0, 2, 0],
  [0, 2, 0, 4],
  [1, 0, 4, 0],
]

# Consulta de adyacencia y peso
u, v = 0, 1
if matriz[u][v] != 0:
  print(f"Existe arista {u}->{v} con peso {matriz[u][v]}")
else:
  print(f"No hay arista directa entre {u} y {v}")

La consulta de adyacencia es O(1) y el código queda compacto. El costo es el consumo de memoria O(n²), incluso si hay pocas aristas.

3.2 Lista de adyacencia

Cada vértice guarda una lista de sus vecinos. Se implementa con listas de Python, diccionarios o arreglos de listas.

n = 4
lista = {i: [] for i in range(n)}

def agregar_arista(u, v, peso):
  lista[u].append((v, peso))

def imprimir_vecinos(u):
  vecinos = " ".join(f"{v}(peso={p})" for v, p in lista[u])
  print(f"Vecinos de {u}: {vecinos}")

agregar_arista(0, 1, 3)
agregar_arista(0, 3, 1)
agregar_arista(1, 2, 2)
agregar_arista(3, 2, 4)

imprimir_vecinos(0)

Con las inserciones anteriores, la lista de vecinos de 0 respeta el orden de inserción, por lo que la salida esperada es: Vecinos de 0: 1(peso=3) 3(peso=1).

El uso de memoria es proporcional al número de aristas (O(n + m)). Consultar adyacencia directa requiere recorrer la lista de vecinos de u (O(grado(u))).

3.3 Comparación entre estructuras

• Adyacencia: matriz O(1); lista O(grado(u)).
• Memoria: matriz O(n²); lista O(n + m).
• Iterar vecinos: similar en ambas; la lista ahorra posiciones vacías.
• Mutabilidad: insertar/eliminar aristas es inmediato en lista; en matriz basta asignar pero se paga el costo fijo de n² celdas.

3.4 Costos de memoria en cada representación

En una matriz de enteros de 4 bytes, un grafo con 5.000 vértices ocupa alrededor de 95 MB aunque tenga pocas aristas. En una lista de adyacencia en Python el consumo depende de las estructuras internas (listas y tuplas), pero sigue creciendo con las aristas efectivas.

3.5 Cuándo conviene usar cada una

• Matriz: grafos densos, tamaño moderado y consultas frecuentes de adyacencia; útil para algoritmos basados en matrices (Floyd-Warshall).
• Lista: grafos dispersos o grandes, cuando se prioriza memoria o se recorre a menudo la vecindad; natural para Dijkstra con montículo y BFS/DFS.
• En proyectos mixtos se combina: matriz para precálculos rápidos y lista para recorridos eficientes.