Recorrido narrado · CSR: todo el grafo en dos arrays

Dirección y pesos

Dirigido: cada arista u→v se guarda una vez, en la lista de u.
Sin dirección: cada arista se guarda en las dos listas, como dos aristas dirigidas.
Pesos: si cada arista tiene un peso (una distancia, un tiempo), va en un array pesos paralelo a vecinos: el peso de la arista guardada en vecinos[k] está en pesos[k].

El peso de la arista guardada en vecinos[k] está en pesos[k], en la misma columna. En la columna 3, la arista 2→0 (vecino 0) pesa 7. Los pesos son de ejemplo.

Texto

para k desde inicio[u] hasta inicio[u + 1] − 1:    v ← vecinos[k]; w ← pesos[k]    … usar la arista u → v con peso w

Representación	Memoria	Vecinos de v	Añadir arista
listas de adyacencia	O(V + E), muchas reservas	O(grado), saltando	O(1) amortizado
CSR	O(V + E), dos arrays	O(grado), contiguo	O(V + E)

Recorrer los vecinos en CSR lee memoria contigua: el mismo argumento de la caché que hizo ganar al array sobre la lista.

Su fila en la tabla de costos

Con la fila de CSR, la tabla de costos del grafo queda así:

Representación	memoria	¿existe (u, v)?	vecinos de v	añadir una arista
listas de adyacencia	O(V + E)	O(grado(u))	O(grado(v))	O(1) amortizado
CSR	O(V + E)	O(log grado(u)) si los vecinos de cada vértice van ordenados; O(grado(u)) si no	O(grado(v)), contiguo	O(V + E)

Ocupan lo mismo en notación O; CSR gana en recorrer y pierde en cambiar. Es el mismo intercambio de siempre: lo contiguo para leer mucho, lo enlazado para cambiar mucho.