Representación de grafos

Un mapa de rutas, las dependencias de un proyecto y una red social son el mismo objeto: elementos y relaciones entre ellos. Antes de recorrerlo o de buscar caminos hay que decidir cómo se guarda, porque esa decisión fija el costo de todo lo que venga después.

Vértices, aristas y las variantes

Un grafo son vértices y aristas. Si la relación es simétrica el grafo es no dirigido; si no lo es, cada arista tiene origen y destino. Las aristas pueden llevar peso: distancia, costo, capacidad.

Dos números mandan en el análisis: la cantidad de vértices $V$ y la de aristas $E$. Un grafo es denso cuando $E$ se acerca a $V^2$ y ralo cuando se parece a $V$. Casi todos los grafos reales son ralos, y eso decide gran parte de lo que sigue.

La matriz de adyacencia

La matriz de adyacencia es un arreglo de $V \times V$ donde la celda $(i,j)$ dice si existe la arista, o cuánto pesa. Preguntar si dos vértices son vecinos es una lectura: $O(1)$.

El precio es la memoria, $\Theta(V^2)$ sin importar cuántas aristas haya, y el costo de recorrer los vecinos de un vértice, que obliga a mirar la fila entera: $O(V)$, la mayoría celdas vacías. En un grafo no dirigido la matriz es simétrica y alcanza con guardar media.

Las listas de adyacencia

Las listas de adyacencia guardan, para cada vértice, sólo sus vecinos reales. La memoria pasa a ser $\Theta(V+E)$ y recorrer los vecinos de un vértice cuesta lo que ese vértice tiene, no lo que podría tener.

Lo que se pierde es la consulta directa: saber si existe una arista puntual obliga a recorrer la lista del vértice, $O(grado)$. Para un grafo ralo la cuenta cierra a favor de las listas, y por eso son la representación por defecto.

Comparar E contra V al cuadrado

La regla práctica sale de comparar $E$ con $V^2$. Con un grafo denso o algoritmos que consultan aristas sueltas todo el tiempo, la matriz gana. Con un grafo ralo que se recorre —BFS, DFS, caminos mínimos—, ganan las listas: esos algoritmos terminan en $O(V+E)$ con listas y arrastran un $O(V^2)$ con matriz.

Hay un caso a favor de la matriz aunque el grafo sea ralo: los algoritmos que la usan como matriz, por ejemplo calcular caminos entre todos los pares.

Representaciones intermedias

Hay representaciones intermedias. La lista de aristas guarda sólo las ternas origen, destino y peso: es lo mínimo para algoritmos que las ordenan por peso, como el árbol generador mínimo.

Para grafos grandes y estáticos se usa la forma comprimida: un arreglo con todos los vecinos concatenados y otro con dónde empieza cada vértice. Ocupa poco, recorre rápido por localidad de memoria y no admite cambios sin reconstruirla.

Dos detalles que se pagan caro

Dos detalles se pagan caro si se ignoran. El primero: en un grafo no dirigido cada arista aparece dos veces en las listas, así que la memoria es $2E$ y un recorrido ingenuo puede procesarla dos veces.

El segundo: los vértices conviene numerarlos de $0$ a $V-1$ y traducir los nombres reales con una tabla hash. Con índices enteros, el estado de los algoritmos —visitados, distancias, padres— son arreglos comunes en vez de diccionarios.

Elegir la representación

La cuenta que ordena la decisión es cuántas aristas tiene el grafo comparado con cuántas podría tener. Un grafo con $V$ vértices puede tener hasta $V^2$ aristas, y los grafos reales casi nunca se acercan: una red social con mil millones de cuentas no tiene mil millones de amigos por cuenta, tiene unos cientos. Por eso la lista de adyacencia es el default, y la matriz aparece sólo cuando el grafo es chico o genuinamente denso.

Cierre

Matriz y listas describen el mismo grafo con costos opuestos: la matriz responde rápido por una arista y paga $V^2$ de memoria; las listas ocupan $V+E$ y recorren vecinos sin desperdicio. Con grafos ralos, que son casi todos, las listas son el default.