Representación de Grafos

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. La representación no es un detalle de implementación

Un grafo es un objeto abstracto: un conjunto de vértices y aristas, nada más. Un ordenador no puede almacenar un objeto abstracto. Almacena bytes, y la elección de qué bytes decide, antes de que escribas una sola línea de algoritmo, de qué es capaz tu programa.

Esa afirmación es fácil de enunciar y fácil de subestimar, así que aquí está su versión más contundente. La búsqueda en anchura se ejecuta en tiempo O(n + m) sobre una lista de adyacencia y en tiempo O(n2) sobre una matriz de adyacencia. El mismo algoritmo, el mismo grafo, la misma salida. Solo cambia el almacenamiento. En un grafo con un millón de vértices y cincuenta millones de aristas, esa es la diferencia entre unos 51 millones de operaciones y aproximadamente un billón: un factor de alrededor de 19,600. Ningún ajuste de constantes recupera eso. La representación fue desde el principio la complejidad asintótica del algoritmo.

La razón es sencilla una vez vista. Ambas versiones de BFS hacen lo mismo en cada vértice: enumerar sus vecinos. Una lista de adyacencia responde a «¿quiénes son los vecinos de v?» en un tiempo proporcional a cuántos hay. Una matriz de adyacencia lo responde recorriendo una fila entera de longitud n, que en su mayor parte son ceros. Sumado sobre todos los vértices, la lista cuesta 2m y la matriz cuesta n2. Esta es exactamente la observación sobre la que Hopcroft y Tarjan construyeron sus algoritmos de grafos en tiempo lineal a principios de los años setenta, y es la razón por la que la lista de adyacencia se convirtió en la opción por defecto en todos los cursos de algoritmos desde entonces.

Pero la lista de adyacencia no siempre es la respuesta, y tratarla como opción automática es un error propio. Pregunta si dos vértices dados son adyacentes y la matriz responde con un acceso a memoria mientras la lista recorre una secuencia de vecinos. Multiplica el grafo por sí mismo y la matriz te entrega gratis el número de paseos. Almacena un grafo genuinamente denso y la matriz usa menos memoria, no más. Ejecuta en una GPU y ninguna de las dos estructuras es la que quieres.

Así que el planteamiento honesto no es «qué representación es la mejor», sino qué pregunta vas a hacer con más frecuencia, y cómo de grande es el grafo. Este artículo recorre las siete representaciones que importan en la práctica, deduce el coste de cada operación en cada una y termina con un procedimiento de decisión. Todos los números sobre el grafo de ejemplo de abajo se calcularon con un script en lugar de afirmarse, y la aritmética está reproducida para que puedas comprobarla.

2. El ejemplo recurrente

Un pequeño grafo ponderado sostiene todo el artículo. Es deliberadamente lo bastante diminuto como para escribirlo por completo en cada representación, y deliberadamente lo bastante irregular como para que las representaciones se vean realmente distintas.

V = {0, 1, 2, 3, 4, 5}

E = { {0,1}:4   {0,2}:3   {1,2}:2   {1,3}:5   {2,4}:7   {3,4}:1   {3,5}:6 }

n = 6      m = 7      suma de grados = 14 = 2m
grados     0:2   1:3   2:3   3:3   4:2   5:1

Dos datos sobre él van a volver una y otra vez. Sus conjuntos de vecinos, escritos en orden, son

0 → 1, 2
1 → 0, 2, 3
2 → 0, 1, 4
3 → 1, 4, 5
4 → 2, 3
5 → 3

y su densidad es 7 / 15 = 46.7%, ya que un grafo simple con 6 vértices admite como mucho C(6,2) = 15 aristas. Eso es muy denso para lo que se ve en la realidad, lo que supone un correctivo útil: los grafos de juguete de los libros de texto son casi siempre densos, y las intuiciones sobre representación que generan son casi siempre erróneas para datos de producción. Lo corregiremos en la sección 6.

3. La lista de aristas

La representación más simple consiste en escribir las aristas y parar ahí.

edges = [ (0,1,4), (0,2,3), (1,2,2), (1,3,5), (2,4,7), (3,4,1), (3,5,6) ]

Un arreglo de m triples. El espacio es Θ(n + m) si además guardas un recuento de vértices, y Θ(m) si el conjunto de vértices está implícito en las aristas. No se precalcula nada, no se indexa nada.

La consecuencia es que casi toda consulta es un recorrido completo. «¿Son 1 y 4 adyacentes?» exige recorrer las siete aristas. «¿Cuáles son los vecinos de 3?» exige recorrer las siete aristas. Ambas son O(m), lo que resulta catastrófico si lo haces dentro de un bucle sobre los vértices, porque eso se convierte en O(nm).

Y aun así la lista de aristas no es una elección ingenua, porque hay tres situaciones importantes que quieren exactamente esta forma:

• Algoritmos que iteran sobre aristas en lugar de sobre vértices. El algoritmo de Kruskal ordena todas las aristas por peso y las considera en ese orden; nunca pide una lista de vecinos. Bellman-Ford relaja cada arista n - 1 veces; de nuevo, pura iteración sobre aristas. Para estos, la lista de aristas no es meramente adecuada, es óptima, ya que cualquier otra representación tendría que aplanarse de vuelta al orden de las aristas.
• Intercambio y almacenamiento. Todos los formatos de archivo de grafos en disco son listas de aristas, porque es la única representación independiente del orden, que solo añade al final y que se analiza trivialmente. Cuando descargas un conjunto de datos de SNAP o de las colecciones DIMACS, obtienes una lista de aristas, y tu primer paso es convertirla.
• Streaming. Si el grafo no cabe en memoria en absoluto, lo que llega es una lista de aristas, una arista cada vez, y el modelo de computación semi-streaming se basa en la suposición de que eso es todo lo que obtienes.

La regla práctica es que una lista de aristas es un formato de transporte y un formato de iteración , no un formato de consulta. Los sistemas reales leen una lista de aristas y construyen de inmediato algo indexado. Esa conversión es el tema de la sección 7, y es más barata de lo que la gente espera: un counting sort sobre los identificadores de vértice la hace en O(n + m).

4. La matriz de adyacencia

Numera los vértices de 0 a n - 1 y construye la matriz n × n llamada A en la que A[u][v] = 1 si {u, v} es una arista y 0 en caso contrario. Para el ejemplo recurrente:

      0  1  2  3  4  5        suma de fila
  0 [ 0  1  1  0  0  0 ]         2
  1 [ 1  0  1  1  0  0 ]         3
  2 [ 1  1  0  0  1  0 ]         3
  3 [ 0  1  0  0  1  1 ]         3
  4 [ 0  0  1  1  0  0 ]         2
  5 [ 0  0  0  1  0  0 ]         1

36 celdas, 14 de ellas no nulas

Tres propiedades estructurales se deducen directamente, y cada una es una comprobación útil al depurar.

• La matriz de un grafo no dirigido es simétrica. A[u][v] = A[v][u] siempre, así que la mitad del almacenamiento es redundante. Los grafos dirigidos renuncian a esta simetría, que es precisamente lo que hace visible la dirección en el álgebra.
• Las sumas por fila son los grados: 2, 3, 3, 3, 2, 1, que coinciden con la lista de la sección 2. El número total de unos es 2m = 14, ya que cada arista aporta dos celdas.
• La diagonal es cero en un grafo simple, porque una entrada diagonal no nula es un bucle.

Lo que compras es adyacencia en tiempo constante. Preguntar si 1 y 4 son adyacentes es una lectura de arreglo, A[1][4], independiente del grado. Ninguna otra representación de este artículo lo consigue sin hashing. Lo que pagas es Θ(n2) de espacio, sin importar cuántas aristas existan, y Θ(n) de tiempo para enumerar los vecinos de un vértice, sin importar lo pocos que sean.

Ese último coste es el que muerde. El vértice 5 tiene un único vecino, pero leer la fila 5 para descubrirlo toca seis celdas. Escala eso a un millón de vértices y encontrar los vecinos de un vértice de grado uno toca un millón de celdas. El O(n2) del BFS sobre matriz es enteramente este efecto, acumulado.

El refinamiento del empaquetado en bits. Si el grafo no es ponderado, cada celda necesita un bit, no un byte y desde luego no un entero de 32 bits. Empaquetar las filas en palabras de máquina reduce la memoria por un factor de 8 frente a una matriz de bytes y de 32 frente a una matriz de enteros, y hace algo más interesante: permite operar sobre 64 vecinos por instrucción. Intersecar dos vecindades, que es el bucle interno del conteo de triángulos y de muchos algoritmos de clique, se convierte en un AND por palabras sobre n/64 palabras en lugar de un bucle sobre n entradas. Volvemos a esto en la sección 11, porque es la razón principal por la que sobreviven las representaciones densas.

5. La lista de adyacencia

Almacena, para cada vértice, una secuencia de sus vecinos.

adj[0] = [ (1,4), (2,3) ]
adj[1] = [ (0,4), (2,2), (3,5) ]
adj[2] = [ (0,3), (1,2), (4,7) ]
adj[3] = [ (1,5), (4,1), (5,6) ]
adj[4] = [ (2,7), (3,1) ]
adj[5] = [ (3,6) ]

El espacio es Θ(n + m): una ranura por vértice más 2m = 14 entradas de vecinos para un grafo no dirigido, o m para uno dirigido. Enumerar los vecinos de v cuesta Θ(deg(v)), que es óptimo, ya que no puedes listar k cosas en menos de k tiempo.

Esta es la representación que hace posibles los algoritmos de grafos en tiempo lineal, y su adopción tiene una historia precisa. El artículo de Tarjan de 1972 sobre la búsqueda en profundidad y los algoritmos complementarios de Hopcroft y Tarjan de 1973 son explícitos en que las cotas O(n + m) dependen del almacenamiento como lista de adyacencia; los mismos procedimientos sobre una matriz son O(n2). El libro de texto de Aho, Hopcroft y Ullman de 1974 convirtió después la lista en la presentación estándar, y desde entonces es la opción por defecto en el código de recorrido .

El coste es que la prueba de adyacencia ya no es constante. Para responder a «¿son 1 y 4 adyacentes?» recorres adj[1], tres entradas, y no encuentras nada. En general eso es O(deg(u)), o O(min(deg(u), deg(v))) si eres lo bastante cuidadoso como para recorrer la lista más corta. En un grafo con unos pocos vértices de grado muy alto, que es el aspecto de cualquier grafo social o web, ese mínimo puede seguir siendo de millones.

La cuestión del orden de los vecinos. Nada en la definición dice que las secuencias de vecinos deban estar ordenadas, y la mayor parte del código las deja en orden de inserción. Ordenarlas cuesta O(m log m) una vez y compra dos cosas: adyacencia con búsqueda binaria en O(log deg(u)), e intersección de vecindades en tiempo lineal por fusión, que es en lo que se apoyan las implementaciones rápidas de conteo de triángulos. Si intersecas vecindades, ordena.

La trampa de implementación. La imagen de libro de texto de una lista de adyacencia es un arreglo de listas enlazadas, y esa imagen es un mal consejo en el hardware moderno. Una lista enlazada desreferencia un puntero por vecino, y cada desreferencia es un posible fallo de caché que cuesta del orden de cien ciclos. Un vector<vector<int>> es mejor, ya que los vecinos de cada vértice son contiguos, pero aún dispersa n bloques asignados por separado por el montón y paga una cabecera de asignación por vértice. La solución está en la sección 7.

Variantes basadas en hash. Sustituir cada secuencia de vecinos por un conjunto hash da una prueba de adyacencia en O(1) esperado manteniendo espacio Θ(n + m) , lo que parece lo mejor de ambos mundos. En la práctica la constante es poco amable: un conjunto hash cuesta varias veces la memoria de un arreglo compacto de enteros, destruye la localidad de iteración y hace que el recorrido de vecinos, que es la operación que más haces, sea apreciablemente más lento. Úsalo cuando las consultas de adyacencia dominen de verdad sobre el recorrido, y mide en lugar de suponer.

6. Qué significa realmente «disperso»

Todo lo anterior depende de una palabra. Un grafo es disperso cuando m está cerca de n y denso cuando m está cerca de n2, y la línea divisoria práctica es la densidad

densidad = m / C(n,2) = 2m / (n(n-1))

que es la fracción de las aristas posibles que existen. El ejemplo recurrente está en 7/15 = 46,7 %, que es enormemente denso. Los grafos reales no son así. Una red social con un millón de usuarios y cincuenta millones de amistades, una media de 100 amigos cada uno, tiene una densidad de 1.0 × 10-4: una centésima parte del uno por ciento. Las redes de carreteras son todavía más extremas, con un grado medio inferior a 3 porque las intersecciones tienen un número limitado de calles. El grafo web, los grafos de citas, las redes de interacción de proteínas y los grafos de dependencias están todos en el mismo régimen.

Esto es lo que cuesta, calculado para exactamente ese grafo de un millón de vértices:

La matriz es aproximadamente 300 veces mayor que las estructuras dispersas incluso empaquetada a bits individuales, y no cabe en la memoria de ninguna máquina corriente. Esto no es una preferencia marginal. Es la diferencia entre un programa que se ejecuta y uno que no puede arrancar.

Vale la pena conocer el umbral con precisión. Una matriz empaquetada en bits cuesta n2/8 bytes; una estructura dispersa que almacena un destino de 4 bytes por arco dirigido cuesta unos 8m bytes. La matriz gana cuando n2/8 < 8m, es decir, cuando m > n2/64, lo que corresponde a una densidad superior a aproximadamente 3,1 %. Por encima, usa una matriz; por debajo, no. Casi todos los grafos que te encontrarás fuera de pequeños problemas de búsqueda combinatoria están tres órdenes de magnitud por debajo.

La comparación completa, operación por operación, escribiendo d para el grado del vértice implicado:

La tabla en esencialmente esta forma es la presentación estándar, se remonta a Aho, Hopcroft y Ullman y está reproducida en el capítulo de grafos de Cormen, Leiserson, Rivest y Stein. Léela como una afirmación sobre qué pregunta haces, no sobre qué fila es la mejor. La única celda en la que la matriz es excepcionalmente fuerte es la prueba de adyacencia, y las únicas celdas en las que la lista de aristas es fuerte son la iteración sobre aristas completas y el añadido al final. Todo lo demás pertenece a las estructuras dispersas indexadas.

7. Fila dispersa comprimida

La representación que usa de verdad el código de grafos en producción no es la lista de adyacencia como arreglo de vectores. Es la fila dispersa comprimida, tomada tal cual del álgebra lineal dispersa, donde es estándar desde los trabajos de Gustavson a principios de los años setenta y está documentada en Duff, Erisman y Reid como el esquema canónico de almacenamiento disperso. En el mundo de los grafos a veces se la llama representación forward star , o simplemente lista de adyacencia aplanada.

La idea es concatenar todas las secuencias de vecinos en un único arreglo y mantener un segundo arreglo que registre dónde empieza el tramo de cada vértice.

offsets = [ 0, 2, 5, 8, 11, 13, 14 ]                       longitud n + 1 = 7
targets = [ 1, 2, 0, 2, 3, 0, 1, 4, 1, 4, 5, 2, 3, 3 ]     longitud 2m  = 14
weights = [ 4, 3, 4, 2, 5, 3, 2, 7, 5, 1, 6, 7, 1, 6 ]     longitud 2m  = 14

Los vecinos del vértice v son targets[offsets[v] .. offsets[v+1] - 1]. Para el vértice 2 eso son las posiciones de la 5 a la 7, lo que da los vecinos [0, 1, 4] con pesos [3, 2, 7], que coincide exactamente con adj[2] . El grado sale gratis como offsets[v+1] - offsets[v], recuperando 2, 3, 3, 3, 2, 1 sin tocar en absoluto el arreglo de destinos.

Asintóticamente esto es idéntico a una lista de adyacencia. En la práctica es sustancialmente más rápido, por cuatro razones que nada tienen que ver con la notación O grande:

• Localidad. Los vecinos de un vértice ocupan bytes consecutivos, así que recorrerlos fluye por las líneas de caché en lugar de perseguir punteros. El precaptador del hardware puede ver el patrón de acceso y adelantarse a él.
• Sin asignación por vértice. Dos asignaciones sustituyen a n + 1 de ellas. En el ejemplo de un millón de vértices eso elimina unos 38 MiB de cabeceras y, más importante, elimina un millón de ocasiones para que los bloques de vecinos queden dispersos.
• Trivialmente serializable. Toda la estructura son dos arreglos de enteros, así que puede mapearse en memoria desde disco, enviarse por red o entregarse a una GPU sin corregir punteros.
• Compresión de índices. Como targets contiene identificadores de vértice, un grafo con menos de 2³² vértices necesita solo 4 bytes por entrada, y uno con menos de 2¹⁶ necesita 2. El arreglo de offsets sí necesita entradas de 64 bits en cuanto 2m supera 2³¹, que es un error real y frecuente a escala de miles de millones de aristas.

Construir CSR a partir de una lista de aristas es O(n + m) y no requiere ordenar. Cuenta el grado de cada vértice en una pasada, acumula las cuentas en offsetscon una suma de prefijos, y luego haz una segunda pasada colocando cada arista en su hueco con un cursor móvil por vértice. Esto es un counting sort por vértice origen, y es la vía de ingesta estándar en toda biblioteca de grafos seria.

El precio es la rigidez. Insertar una sola arista desplaza todas las entradas posteriores de targets, así que la estructura es efectivamente inmutable: la reconstruyes en Θ(n + m) en lugar de actualizarla. Ese es un buen intercambio cuando el grafo se carga una vez y se consulta muchas, que describe la mayoría de las cargas analíticas, y uno malo cuando el grafo cambia constantemente. La sección 12 se ocupa del segundo caso.

8. La matriz de incidencia

La tercera matriz clásica indexa vértices contra aristas en lugar de contra vértices. Etiqueta las siete aristas de e1 a e7 en el orden en que se listaron, y pon B[v][e] = 1 cuando v es un extremo de e:

       e1 e2 e3 e4 e5 e6 e7
   0 [  1  1  0  0  0  0  0 ]
   1 [  1  0  1  1  0  0  0 ]
   2 [  0  1  1  0  1  0  0 ]
   3 [  0  0  0  1  0  1  1 ]
   4 [  0  0  0  0  1  1  0 ]
   5 [  0  0  0  0  0  0  1 ]

sumas por columna todas 2      sumas por fila 2,3,3,3,2,1 = grados

La forma es n × m, así que el espacio es Θ(nm), que es peor que la matriz de adyacencia para cualquier grafo con más aristas que vértices. Nadie almacena un grafo así para calcular. La matriz de incidencia se gana su sitio por otra razón: es el puente entre la teoría de grafos y el álgebra lineal.

Dos identidades lo dejan claro. Para la matriz sin signo de arriba, B BT = A + D, donde D es la matriz diagonal de los grados. Sustituir los números del ejemplo recurrente lo confirma exactamente. Si en cambio orientas cada arista de forma arbitraria y escribes -1 en su cola y +1 en su cabeza, la matriz de incidencia con signo Bs cumple

B_s B_s^T  =  D - A  =  L,   el laplaciano

con independencia de la orientación que hayas elegido. Esa identidad es la razón de que el laplaciano sea semidefinido positivo, y es la puerta de entrada a la teoría espectral de grafos. Diestel desarrolla más esta línea, usando la matriz de incidencia para definir el espacio de ciclos y el espacio de cortes de un grafo, dos espacios vectoriales sobre el cuerpo de dos elementos cuyas dimensiones son m - n + c y n - c para un grafo con c componentes. La matriz de incidencia es además el marco natural para los problemas de flujo: la matriz de restricciones de un programa lineal de flujo en redes es la matriz de incidencia con signo, y su unimodularidad total es lo que garantiza que el programa lineal tenga soluciones óptimas enteras.

Una nota más. La matriz de incidencia maneja los multigrafos con más elegancia que la matriz de adyacencia, ya que las aristas paralelas son simplemente columnas distintas en lugar de un recuento embutido en una celda. Los hipergrafos, donde una arista puede unir más de dos vértices, no tienen ninguna matriz de adyacencia sensata, pero sí una matriz de incidencia perfectamente natural con sumas por columna mayores que dos. Si alguna vez necesitas generalizar más allá de los grafos ordinarios, esta es la representación que generaliza.

9. Dirección, peso, multiplicidad y bucles

Todo lo anterior suponía un grafo simple no dirigido. Cuatro desviaciones habituales cambian lo que cada representación debe hacer, y ahí es donde se concentran los errores de implementación.

Dirección. En un grafo dirigido la matriz de adyacencia deja de ser simétrica, y A[u][v] = 1 significa solo un arco de u a v . La lista de adyacencia almacena cada arco una vez en lugar de dos, así que los arreglos de vecinos contienen m entradas en lugar de 2m. Esa reducción a la mitad es, con diferencia, la fuente más común de estimaciones de memoria erradas por un factor de dos.

La complicación real es que un grafo dirigido tiene dos vecindades. adj[v] da los sucesores; los predecesores exigen o bien recorrer toda la estructura o bien almacenar una segunda copia con todos los arcos invertidos. El álgebra lineal dispersa llama a esa segunda copia columna dispersa comprimida, y todo algoritmo que camine hacia atrás, incluidas la alcanzabilidad inversa, el procedimiento de componentes fuertemente conexas de Kosaraju y el Dijkstra hacia atrás en la búsqueda bidireccional, la necesita. Presupuesta dos estructuras, no una.

Peso. Los pesos pueden vivir directamente en las celdas de la matriz, sustituyendo el 1 por el peso. La sutileza es en qué se convierte una no-arista: 0 es un peso legítimo, así que una celda con 0 es ambigua. La convención es almacenar ∞ para las aristas ausentes en contextos de caminos más cortos, que es exactamente lo que Floyd-Warshall supone al entrar, y 0 en contextos de flujo, donde un arco de capacidad cero y un arco ausente son realmente lo mismo. Elige uno deliberadamente. En las estructuras dispersas el peso va en un arreglo paralelo indexado igual que targets, como en el listado CSR de arriba, lo que mantiene ambos al unísono y preserva la localidad. Almacenar pares intercalados también está bien y a veces es mejor; almacenar los pesos en un mapa hash aparte indexado por arista es casi siempre peor.

Multiplicidad. Las aristas paralelas rompen la premisa básica de la matriz de adyacencia, ya que una celda contiene un valor. El arreglo habitual es almacenar la multiplicidad como un recuento entero, lo que funciona para problemas de conteo pero descarta los datos por arista, como pesos o identificadores distintos. Las listas de adyacencia aceptan las multiaristas sin quejarse: el mismo vecino simplemente aparece más de una vez. Si necesitas atributos por arista en un multigrafo, almacena identificadores de arista en los arreglos de vecinos y guarda los atributos en una tabla de aristas aparte indexada por esos identificadores, que es lo que hacen la mayoría de las bases de datos de grafos.

Bucles. Un bucle en v pone un valor no nulo en la diagonal. La convención que pilla a la gente es que en un grafo no dirigido un bucle aporta 2 al grado de v, así que la matriz de adyacencia no dirigida estándar almacena A[v][v] = 2 para un solo bucle, con el fin de mantener cierta la identidad suma de fila igual a grado. Mucho código almacena 1 en su lugar y luego informa en silencio de grados incorrectos. En una lista de adyacencia la misma pregunta pasa a ser si v aparece una o dos veces en su propia secuencia de vecinos, y la respuesta honesta es que debes decidirlo y documentarlo, porque ambas convenciones existen en la literatura.

10. Representaciones algebraicas

Una vez que un grafo es una matriz, las operaciones matriciales significan algo. Esto no es una curiosidad; es la base de todo un estilo de computación sobre grafos.

Las potencias de la matriz de adyacencia cuentan paseos. La entrada Ak[u][v] es exactamente el número de paseos de longitud k de u a v, lo que se sigue por inducción de la definición de producto de matrices. En el ejemplo recurrente:

A^2 =  [ 2  1  1  1  1  0 ]
       [ 1  3  1  0  2  1 ]
       [ 1  1  3  2  0  0 ]
       [ 1  0  2  3  0  0 ]
       [ 1  2  0  0  2  1 ]
       [ 0  1  0  0  1  1 ]

Se lee A2[1][4] = 2: hay dos paseos de longitud 2 de 1 a 4, en concreto 1→2→4 y 1→3→4. Compruébalo con el dibujo. La diagonal A2[v][v] es 2, 3, 3, 3, 2, 1, que es de nuevo la sucesión de grados, porque un paseo de longitud 2 de v a sí mismo es un paso hasta un vecino y vuelta. Una potencia más allá, trace(A3) = 6, y dividir por 6 da un triángulo, que la fuerza bruta confirma que es {0, 1, 2}. La división por 6 descuenta los tres puntos de partida y las dos direcciones de cada triángulo.

El laplaciano. Define L = D - A:

L =  [  2 -1 -1  0  0  0 ]
     [ -1  3 -1 -1  0  0 ]
     [ -1 -1  3  0 -1  0 ]
     [  0 -1  0  3 -1 -1 ]
     [  0  0 -1 -1  2  0 ]
     [  0  0  0 -1  0  1 ]

Cada fila suma cero, así que el vector de unos está en el núcleo y L es singular. El teorema de la matriz-árbol de Kirchhoff dice que eliminar una fila cualquiera y su columna correspondiente y tomar el determinante cuenta los árboles de expansióndel grafo. Los seis cofactores de la matriz de arriba valen 11, y enumerar los C(7,5) = 21 subconjuntos de cinco aristas y comprobar la aciclicidad de cada uno encuentra exactamente 11 árboles de expansión. El teorema no es una aproximación; es una identidad, y convierte un problema de conteo que parece exponencial en un solo determinante.

Los valores propios del laplaciano llevan más información. La multiplicidad del valor propio 0 es el número de componentes conexas. El segundo valor propio más pequeño, la conectividad algebraica de Fiedler, mide lo difícil que es desconectar el grafo, y el patrón de signos de su vector propio da una bisección utilizable del grafo. Esta es la maquinaria detrás del agrupamiento espectral y de buena parte de la teoría espectral de grafos de Chung.

Grafos como álgebra lineal sobre semianillos. La versión más profunda de esta idea es que muchos algoritmos de grafos son operaciones matriciales, una vez que cambias la aritmética. Sustituye (+, ×) por (min, +) y el producto de matrices se convierte en la relajación de caminos más cortos, así que An-1 sobre el semianillo min-más es la matriz de caminos más cortos entre todos los pares. Sustitúyelo por (OR, AND) y se convierte en alcanzabilidad. La búsqueda en anchura desde un origen es la multiplicación repetida de un vector frontera disperso por la matriz de adyacencia sobre un semianillo booleano. Kepner y Gilbert lo exponen sistemáticamente, y es la especificación que implementa el estándar GraphBLAS. La ganancia es práctica: expresar un algoritmo como productos de matriz dispersa por vector le permite heredar décadas de álgebra lineal paralela afinada, que es como están construidos muchos frameworks de grafos sobre GPU.

11. Cuándo gana la matriz

Después de la sección 6sería fácil concluir que las matrices de adyacencia son un recurso didáctico. No lo son, y vale la pena ser precisos sobre las cuatro situaciones en las que la matriz es la respuesta correcta.

Valores pequeños de n. Si n es de unos pocos cientos, n2 son unas decenas de miles de celdas y el argumento de la memoria se evapora. Floyd-Warshall calcula los caminos más cortos entre todos los pares en tiempo Θ(n3) y espacio Θ(n2) sobre una matriz, con un bucle interno de tres líneas y un comportamiento de caché casi perfecto; para n en los cientos, rutinariamente gana a ejecutar Dijkstra n veces sobre una estructura dispersa, pese a la peor asintótica. La programación competitiva y la investigación operativa están llenas de este régimen.

Grafos genuinamente densos. Por encima del umbral de densidad de aproximadamente 3,1 % calculado antes, la matriz es más pequeña además de más rápida. Los grafos complementarios, los grafos de similitud con un umbral permisivo y los grafos de restricciones de problemas de planificación caen aquí con regularidad.

Paralelismo con bitsets. Este es el argumento más fuerte. Empaqueta cada fila de la matriz en palabras de máquina y las operaciones de conjuntos sobre vecindades pasan a ser paralelas por palabra. La clausura transitiva mediante la técnica de los Cuatro Rusos, introducida por Arlazarov, Dinic, Kronrod y Faradzev en 1970, calcula la alcanzabilidad en O(n3 / log n) precalculando resultados para bloques de bits; el mismo truco con palabras corrientes de 64 bits da una ganancia enorme en el factor constante casi sin código. El conteo de triángulos, la clique máxima por ramificación y acotación y los productos matriciales booleanos se apoyan todos en esto. Una estructura dispersa simplemente no puede hacer 64 pruebas de adyacencia en una instrucción.

Acceso a la multiplicación rápida de matrices. Algunos problemas de grafos se reducen a la multiplicación de matrices y heredan su exponente. El algoritmo de Seidel calcula los caminos más cortos entre todos los pares en un grafo no dirigido y sin pesos en tiempo O(nω log n) elevando al cuadrado repetidamente la matriz de adyacencia, donde ω es el exponente de la multiplicación de matrices. Alman y Vassilevska Williams situaron ω por debajo de 2,3729 en 2021, y refinamientos posteriores lo han bajado algo más. Estas cotas son en gran medida teóricas, ya que los algoritmos que las alcanzan tienen constantes que los hacen poco prácticos, pero la reducción es real y existe solo porque el grafo es una matriz.

12. Grafos que cambian

Todas las estructuras anteriores se describieron como si el grafo fuera fijo. Muchos no lo son, y el coste de actualización es una dimensión que la tabla comparativa estándar minusvalora.

Los casos claros son los extremos. Una matriz de adyacencia admite tanto la inserción como la eliminación en O(1), ya que ambas son una única escritura de celda; su problema nunca fue la velocidad de actualización. Una lista de aristas añade al final en O(1) pero elimina en O(m), porque primero tiene que encontrar la arista. CSR no hace ninguna de las dos: cualquier cambio estructural la reconstruye entera en Θ(n + m).

Las listas de adyacencia quedan en medio y recompensan un poco de cuidado. Añadir un vecino a un arreglo dinámico es O(1) amortizado. Eliminar cuesta O(deg(u)) para localizar la entrada, pero solo O(1) para quitarla una vez encontrada, siempre que intercambies el último elemento con el hueco en lugar de desplazarlo todo. Si además necesitas eliminar la copia inversa en un grafo no dirigido, guarda en cada entrada la posición de su gemela para que la segunda eliminación también sea O(1) , que es exactamente lo que hace la clásica representación de aristas basada en arreglos con índices emparejados.

Tres patrones cubren la mayoría de las necesidades reales:

• Acumular y reconstruir. Acumula las actualizaciones en un pequeño búfer lateral, responde a las consultas contra CSR más búfer, y reconstruye CSR cuando el búfer supere un umbral. Una reconstrucción cuesta Θ(n + m), así que repartirla entre Θ(m) actualizaciones sale a O(1) por actualización siempre que m sea al menos n, lo que cubre esencialmente cualquier grafo real. Esto es lo que hacen la mayoría de los sistemas analíticos, y suele bastar.
• Marcado con lápidas. Marca las entradas eliminadas en lugar de quitarlas, y compacta periódicamente. Quitar la entrada pasa a ser O(1) una vez encontrada, y ninguna otra entrada se mueve, así que los índices a los arreglos de vecinos siguen siendo válidos. Localizar la entrada sigue siendo O(deg(u)) salvo que ya tengas un manejador a ella, y todo recorrido posterior tiene que saltarse las entradas muertas.
• Estructuras genuinamente dinámicas. Cuando las actualizaciones y las consultas de conectividad se entrelazan y ambas deben ser rápidas, la literatura de estructuras de datos tiene respuestas. Los link-cut trees y los Euler tour trees mantienen un bosque cambiante en tiempo logarítmico por operación, y la conectividad dinámica general sobre grafos arbitrarios se construye sobre ellos, con O(log2 n) amortizado por actualización. Estas son considerablemente más intrincadas que todo lo anterior, y solo deberías recurrir a ellas cuando el patrón de acumular y reconstruir se haya medido y resultado insuficiente.

Una advertencia específica del hardware. Una estructura rápida en la tabla asintótica puede ser lenta en la práctica porque las actualizaciones la fragmentan. Una lista de adyacencia que ha crecido con un millón de inserciones individuales tiene sus bloques de vecinos dispersos por el montón en orden de asignación, y un recorrido posterior paga esa dispersión en cada vértice. Reconstruir periódicamente en CSR a menudo compensa solo por restaurar la localidad, aunque no cambie ninguna cota asintótica.

13. Grafos implícitos: no almacenar nada

Hay una representación más, y es la que la gente olvida que existe: no almacenar el grafo.

Un grafo implícito o procedural se define mediante una función. En lugar de una estructura de datos, proporcionas una rutina sucesora que, dado un vértice, genera sus vecinos bajo demanda. Nada se materializa hasta que se visita.

No es una técnica marginal. Es como funciona esencialmente toda la búsqueda en espacios de estados:

• Espacios de estados de puzles y juegos. El grafo de configuraciones del cubo de Rubik tiene unos 4,3 × 10¹⁹ vértices. Almacenarlo no es una cuestión de esfuerzo de ingeniería: un bit por estado ya son más de cinco exabytes, y los arcos, a dieciocho por estado, pasarían de seis zettabytes. Su función sucesora, aplicar uno de los dieciocho giros de cara, son una docena de líneas de código. Los algoritmos de búsqueda funcionan perfectamente sobre él.
• Planificación y verificación de modelos. El grafo de estados alcanzables de un programa concurrente se genera ejecutando transiciones. Los verificadores de modelos de estado explícito almacenan solo el conjunto visitado, nunca las aristas.
• Grafos geométricos y de cuadrícula. Una cuadrícula de búsqueda de rutas tiene una función sucesora obvia: cuatro u ocho desplazamientos con una comprobación de límites y de obstáculos. Una lista de adyacencia para una cuadrícula de 4096 por 4096 con movimiento en ocho direcciones contiene 134 millones de entradas, cada una de las cuales una función de dos líneas reproduce exactamente. Esto importa directamente para A* en cuadrículas.

Vale la pena enunciar las consecuencias con claridad. El espacio cae de Θ(n + m) para el grafo a Θ(|visited|) para la búsqueda, que es lo que hace viable la técnica. A cambio pierdes todo lo que requiere ver el grafo entero: no puedes contar aristas, calcular una distribución de grados ni ejecutar ningún algoritmo que itere sobre todos los vértices. Tampoco puedes pedir predecesores de forma barata salvo que escribas una segunda función para ellos, y regenerar una vecindad cuesta CPU cada vez en lugar de una lectura de memoria, lo que puede ser la opción más cara para una región muy revisitada.

La representación implícita es también lo que da pie a la familia de búsquedas con memoria acotada. La A* con profundización iterativa guarda solo el camino actual en lugar de una lista abierta, cambiando regeneración repetida por espacio lineal, y solo tiene sentido porque la regeneración es posible.

14. Representaciones comprimidas y sucintas

A escala web, incluso CSR es demasiado grande, y dos líneas de investigación distintas atacan eso.

Explotar la estructura. El framework WebGraph de Boldi y Vigna es aquí la referencia estándar. Observa que, si ordenas las páginas web por URL, las páginas de un mismo sitio acaban con conjuntos de enlaces salientes casi idénticos, y sus listas de destinos quedan numéricamente próximas. Codificar cada lista como una referencia a una lista anterior parecida más una pequeña corrección, y codificar después los destinos restantes por huecos con un código de longitud variable, reduce el grafo web a unos pocos bits por enlace, un orden de magnitud mejor que los identificadores crudos de 32 bits. La técnica depende por completo de un buen orden de los vértices, que es la lección general: comprimir grafos es sobre todo un problema de reetiquetado. Blandford, Blelloch y Kash demostraron un resultado complementario para los grafos separables, que incluyen los grafos planares y la mayoría de las mallas, mostrando que un orden basado en separadores da representaciones de O(n)bits que aun así responden a una consulta de adyacencia en tiempo constante.

Estructuras de datos sucintas. Otra tradición pide representaciones cuyo tamaño se acerque al mínimo teórico de información sin dejar de responder consultas sin descomprimir. El trabajo de Jacobson de 1989 introdujo las primitivas rank y select que lo hacen posible, y Munro y Raman lo extendieron a árboles y otras estructuras. Un árbol con raíz de n nodos necesita unos 2n bits en lugar de los n punteros que gasta una codificación ingenua, y la navegación sigue siendo de tiempo constante. Para un grafo el problema general es más difícil, pero el planteamiento es el correcto: el número de grafos etiquetados distintos con n vértices y m aristas da una cota inferior de aproximadamente m log(n2/m) bits, y lo cerca que una representación llegue de ahí es una forma significativa de juzgarla.

Ninguna de las dos líneas es algo a lo que recurrir por defecto. Ambas cuestan tiempo de consulta, ambas cuestan complejidad de implementación, y ambas solo valen la pena cuando el grafo realmente no cabe. El paso intermedio práctico, y el que la mayoría debería probar primero, es simplemente renumerar los vértices para que los vecinos tengan identificadores cercanos. Eso por sí solo mejora de forma medible el comportamiento de la caché sobre un CSR corriente, y cuesta un recorrido en anchura.

15. Un procedimiento de decisión

Condensando todo lo anterior en algo utilizable delante del teclado:

1. ¿Puedes generar los vecinos con una regla? Si el grafo es un espacio de estados, una cuadrícula o cualquier cosa definida de forma procedural, usa una representación implícita y almacena solo lo que visites.
2. ¿Es denso el grafo, o es n pequeño? Por encima de un 3 % de densidad, o por debajo de unos mil vértices, usa una matriz de adyacencia empaquetada en bits. Obtienes adyacencia en tiempo constante y operaciones de conjuntos paralelas por palabra, y por encima del umbral de densidad, también menos memoria. Por debajo, con npequeño, la matriz es la estructura mayor y simplemente da igual.
3. ¿Tu algoritmo solo recorre aristas? Kruskal, Bellman-Ford y cualquier cosa en streaming quieren una lista de aristas. No construyas un índice que nunca vas a consultar.
4. ¿Cambia el grafo después de cargarlo? Si no, construye CSR. Si cambia rara vez, construye CSR con un búfer de actualizaciones y reconstruye periódicamente. Si cambia constantemente, usa listas de adyacencia de arreglos dinámicos con borrado swap-and-pop.

Después aplica dos correcciones. Si el grafo es dirigido y necesitas predecesores, construye también la estructura invertida y paga la segunda copia. Si la prueba de adyacencia domina de verdad tu carga de trabajo en lugar de la iteración sobre vecinos, ordena los arreglos de vecinos para la búsqueda binaria antes de recurrir a conjuntos hash.

16. Errores comunes

• Suponer que la lista de adyacencia siempre es lo correcto. Es la opción por defecto correcta, no una respuesta universal. En un grafo denso de 500 vértices, una matriz de adyacencia es más pequeña, más simple y más rápida.
• Citar O(n + m) para un algoritmo que se ejecuta sobre una matriz. El recorrido sobre una matriz de adyacencia es Θ(n2). La cota pertenece a la representación, no al pseudocódigo.
• Olvidar el factor dos. Un grafo no dirigido almacena 2m entradas en cualquier estructura de adyacencia, porque cada arista aparece en las listas de sus dos extremos. Dimensionar un arreglo a m es un desbordamiento de búfer, no un problema de rendimiento.
• Usar un arreglo de offsets de 32 bits. Los offsets de CSR indexan un arreglo de longitud 2m. Pasados unos dos mil millones de arcos dirigidos esto desborda en silencio y corrompe toda búsqueda de vecinos. Los destinos pueden seguir siendo de 32 bits mientras n esté por debajo de cuatro mil millones; los offsets no.
• Almacenar cero para una arista ponderada ausente. Cero es un peso válido. Usa un centinela de ∞, o almacena la presencia por separado, o usa una estructura dispersa donde la ausencia sea simplemente una entrada ausente.
• Construir CSR ordenando. La construcción con counting sort es O(n + m). Ordenar primero la lista de aristas es O(m log m) e innecesario, aunque es un atajo razonable si de todos modos querías arreglos de vecinos ordenados.
• No almacenar el grafo inverso. Las consultas de predecesores sobre un CSR dirigido exigen un recorrido completo del arreglo de destinos. Si las haces, construye la estructura transpuesta una vez.
• Elegir una representación solo por la asintótica. Una lista de adyacencia y CSR son ambas Θ(n + m), y CSR suele ser varias veces más rápida por la localidad. Los factores constantes en código de grafos limitado por memoria no son un error de redondeo.
• Manejar mal los bucles en el recuento de grados. Un bucle añade 2 al grado en un grafo no dirigido. Decidas lo que decidas que debe almacenar la estructura de adyacencia, haz que la función de grado concuerde con ello.

17. Glosario

19. Referencias

Fuentes de las definiciones, cotas de complejidad y técnicas anteriores, junto con los textos estándar en los que se desarrolla este material, listadas en orden cronológico.

1. Arlazarov, V. L., Dinic, E. A., Kronrod, M. A. y Faradzev, I. A. (1970). “On economical construction of the transitive closure of a directed graph.” Soviet Mathematics Doklady, 11, 1209–1210.
2. Gustavson, F. G. (1972). “Some basic techniques for solving sparse systems of linear equations.” En Sparse Matrices and Their Applications, Plenum Press, 41–52.
3. Tarjan, R. E. (1972). “Depth-first search and linear graph algorithms.” SIAM Journal on Computing, 1(2), 146–160.
4. Hopcroft, J. y Tarjan, R. E. (1973). “Algorithm 447: efficient algorithms for graph manipulation.” Communications of the ACM, 16(6), 372–378.
5. Aho, A. V., Hopcroft, J. E. y Ullman, J. D. (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley.
6. Duff, I. S., Erisman, A. M. y Reid, J. K. (1986). Direct Methods for Sparse Matrices. Oxford University Press.
7. Jacobson, G. (1989). “Space-efficient static trees and graphs.” Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS), 549–554.
8. Seidel, R. (1995). “On the all-pairs-shortest-path problem in unweighted undirected graphs.” Journal of Computer and System Sciences, 51(3), 400–403.
9. Chung, F. R. K. (1997). Spectral Graph Theory. CBMS Regional Conference Series in Mathematics 92, American Mathematical Society.
10. Munro, J. I. y Raman, V. (2001). “Succinct representation of balanced parentheses and static trees.” SIAM Journal on Computing, 31(3), 762–776.
11. Blandford, D. K., Blelloch, G. E. y Kash, I. A. (2003). “Compact representations of separable graphs.” Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 679–688.
12. Boldi, P. y Vigna, S. (2004). “The WebGraph framework I: compression techniques.” Proceedings of the 13th International World Wide Web Conference (WWW), 595–602.
13. Cormen, T. H., Leiserson, C. E., Rivest, R. L. y Stein, C. (2009). Introduction to Algorithms, 3.ª edición, capítulo 22. MIT Press.
14. Kepner, J. y Gilbert, J., editores (2011). Graph Algorithms in the Language of Linear Algebra. Society for Industrial and Applied Mathematics.
15. Diestel, R. (2017). Graph Theory, 5.ª edición. Springer, Graduate Texts in Mathematics 173.
16. Alman, J. y Vassilevska Williams, V. (2021). “A refined laser method and faster matrix multiplication.” Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 522–539.