Fenómeno

Millones de listas pequeñas

Un planificador de rutas carga el mapa de calles de un país: 10 millones de cruces. Con listas de adyacencia, son 10 millones de listas, cada una con 3 o 4 vecinos y su propia reserva de memoria. Recorrer los vecinos de un cruce y luego los del siguiente salta por toda la memoria.

El mapa no cambia mientras se calculan rutas.

Piensa antes de seguir: si el grafo no cambia, ¿hace falta que cada lista sea una estructura aparte?