Representaciones de grafos

Qué cubre este capítulo

Un grafo es la estructura más general del libro: vértices conectados por aristas, sin raíz, sin regla de padre y con ciclos permitidos. Carreteras, redes sociales, dependencias, la web, diagramas de circuitos — cualquier cosa que sea un montón de elementos con conexiones entre ellos es un grafo. Pero antes de que puedas correr un solo algoritmo de grafos, tienes que decidir cómo vas a guardar la cosa, y esa decisión tiñe todo lo que viene después. Este capítulo construye las dos representaciones clásicas — la lista de adyacencia y la matriz de adyacencia — y muestra por qué la lista es la opción por defecto para los grafos dispersos que conforman casi toda la realidad, mientras que la matriz solo gana en los casos densos.

Un poco de historia

La teoría de grafos tiene casi tres siglos, y empezó con una caminata. En 1736 Leonhard Euler resolvió el problema de los Siete Puentes de Königsberg — ¿podías cruzar los siete puentes de la ciudad exactamente una vez? — abstrayendo las porciones de tierra a puntos y los puentes a conexiones, y demostrando que no existía tal ruta. Esa abstracción, tirar el mapa y quedarse solo con "qué se conecta con qué", fundó la teoría de grafos y nos dio el vocabulario de vértices y aristas. Dos siglos después, cuando las computadoras necesitaron almacenar esos grafos abstractos, las dos representaciones de este capítulo surgieron como las codificaciones naturales: una matriz de conexiones, en el espíritu de las tablas de incidencia que los matemáticos ya usaban, y la lista de vecinos, más económica. Elegir entre las dos ha sido la primera lección de programación práctica con grafos desde entonces, porque es el primer lugar donde aparece la brecha entre la simplicidad matemática de un grafo y su costo computacional.

La intuición

Un grafo se define por qué vértices se conectan con cuáles. La lista de adyacencia guarda eso directamente: para cada vértice, una lista de los vértices con los que está conectado. La lista del vértice 3 podría ser [1, 7, 9], lo que significa que 3 se conecta con 1, 7 y 9. Para encontrar los vecinos de un vértice, lees su lista — tocas solo sus vecinos reales, nada más. El almacenamiento total es una entrada por vértice más una (o dos) por arista: O(V + E).

La matriz de adyacencia guarda la misma información como una cuadrícula: una tabla V×V donde la celda (u, v) vale 1 si hay una arista de u a v y 0 si no. Para checar si existe una arista específica, lees una celda — O(1), al instante. Pero la cuadrícula tiene una celda para cada par posible de vértices, conectados o no, así que siempre usa espacio O(V²), y para encontrar los vecinos de un vértice tienes que recorrer su fila completa de V celdas, la mayoría de las cuales son 0 en un grafo disperso.

Ese es el intercambio en una frase: la lista guarda solo lo que existe y paga un pequeño recorrido para probar una arista; la matriz guarda todas las conexiones posibles y prueba una arista al instante. Cuál gana depende de la densidad — cuántas de las aristas posibles existen realmente. Los grafos reales casi siempre son dispersos: una persona tiene unos cientos de amigos, no unos miles de millones; una página web enlaza a decenas de páginas, no a todo internet; un cruce de calles conecta con un puñado de calles. Cuando E está cerca de V y no de V², el O(V+E) de la lista aplasta al O(V²) de la matriz, y por eso la lista es la opción por defecto.

Complejidad: cómo escala

Las dos representaciones tienen perfiles de costo que son espejo uno del otro, como se ve en la tabla del resumen: la lista es $O(V+E)$ de espacio con pruebas de arista e iteración de vecinos en $O(\text{degree})$; la matriz es $O(V^2)$ de espacio con pruebas de arista en $O(1)$ e iteración de vecinos en $O(V)$. Para los grafos dispersos que importan, la diferencia de espacio es enorme. La gráfica traza la memoria de un grafo disperso (grado promedio 6) conforme crece el número de vértices:

Con 4000 vértices, el grafo disperso ocupó unos 437 KB como lista de adyacencia contra 125 MB como matriz — 286 veces más memoria, para el mismo grafo idéntico, porque la matriz reserva una celda para los 16 millones de pares posibles cuando solo existen 24000 aristas. Y esa memoria no es solo almacenamiento: como un recorrido tiene que leer la matriz completa para encontrar todas las aristas, la matriz también vuelve O(V²) a todos los algoritmos de grafos, donde la lista los deja en O(V+E). La representación no es un detalle — define la complejidad de todo lo que viene después.

En qué es buena y en qué no

La lista de adyacencia es la opción correcta por defecto para prácticamente cualquier grafo real, porque los grafos reales son dispersos y su espacio y recorrido O(V+E) son lo que hace eficientes a los algoritmos de los siguientes diez capítulos. BFS, DFS, Dijkstra y los demás son O(V+E) porque corren sobre listas de adyacencia; sobre una matriz serían O(V²). Si no estás seguro de cuál usar, usa la lista.

La matriz se gana su O(V²) solo en dos situaciones. Primera, grafos densos, donde E de verdad está cerca de V² — ahí la matriz no desperdicia, y su disposición contigua y amigable con el cache puede ser más rápida. Segunda, cargas de trabajo dominadas por consultas del tipo "¿hay una arista entre exactamente u y v?" en lugar de iteración de vecinos, donde la prueba O(1) de la matriz le gana al recorrido de la lista. Algunos algoritmos (Floyd-Warshall, en un capítulo posterior) son naturalmente algoritmos de matriz. Pero fuera de esos casos la memoria cuadrática de la matriz es un lastre que crece rápido — 286× aquí y peor conforme los grafos crecen — así que es la especialista, no la opción por defecto.

Los datos, o las entradas

La gráfica de memoria modela grafos dispersos (grado promedio 6) con números de vértices crecientes, aislando la brecha de espacio entre O(V+E) y O(V²). La animación construye un grafo pequeño de seis vértices una arista a la vez, para que puedas ver cómo la estructura — vértices y sus conexiones — va tomando forma.

Constrúyelo, una función a la vez

Para la lista de adyacencia, agregar una arista hace append a las listas de vecinos:

def add_edge(self, u, v):
    """O(1): append v to u's neighbor list (and u to v's, if undirected)."""
    self._adj[u].append(v)
    if not self.directed:
        self._adj[v].append(u)

Y obtener los vecinos es simplemente leer una lista — tocas solo los vecinos reales:

def neighbors(self, u):
    """O(1) to get the list; iterating it is O(degree(u)) — you touch only u's actual
    neighbors, never the vertices it doesn't connect to. This is why traversals over a
    sparse graph are O(V+E) with a list."""
    return self._adj[u]

La matriz es la versión de cuadrícula — O(1) para probar una arista, O(V) para encontrar vecinos:

def add_edge(self, u, v):
    """O(1): set the cell (and its mirror, if undirected)."""
    self._m[u][v] = 1
    if not self.directed:
        self._m[v][u] = 1

def has_edge(self, u, v):
    """O(1): one array lookup — the matrix's whole advantage."""
    return self._m[u][v] == 1

def neighbors(self, u):
    """O(V): scan the entire row, even the zeros — the matrix's whole disadvantage on
    a sparse graph, where almost every cell is 0."""
    return [v for v in range(self.n) if self._m[u][v]]

Míralo funcionar

Aquí tienes un grafo de seis vértices construyéndose una arista a la vez. Los vértices están en posiciones fijas; cada cuadro agrega una arista (resaltada en naranja) e ilumina sus dos extremos. Avanza paso a paso y observa cómo emerge la red — esto es exactamente lo que add_edge le hace a la lista de adyacencia, cada arista agregando los dos extremos a la lista de vecinos del otro. Al final tienes un pequeño grafo conexo, del tipo que explorarán los algoritmos de recorrido de los siguientes capítulos:

El código completo

Ambas versiones en un solo lugar — cambia entre ellas. La pestaña desde cero tiene las dos representaciones. La pestaña de librería es el modelo de memoria que cuantifica su diferencia, y hace las veces de la librería real, networkx, cuyo Graph es un dict de dicts — una lista de adyacencia en espíritu — porque Python no tiene un tipo de grafo integrado; construyes uno con listas o dicts exactamente como aquí.

"""Graph representations — how you store a graph in the first place, which decides what
every graph algorithm after this costs.

A graph is a set of vertices and edges: any vertex can connect to any other, forming
networks — roads, social links, dependencies, the web. Unlike a tree, there's no root,
no parent rule, and cycles are allowed. Before you can search or find paths, you have to
choose a representation, and the choice is a real trade-off between two options:

  - an ADJACENCY LIST — each vertex keeps a list of its neighbors — O(V+E) space,
    perfect for the sparse graphs that dominate the real world;
  - an ADJACENCY MATRIX — a V×V grid of 0/1 — O(V²) space, but O(1) to test whether a
    specific edge exists.

Most real graphs are sparse (each vertex touches only a few others), so the adjacency
list is the default; the matrix wins only for dense graphs or when you constantly ask
"is there an edge between exactly these two?"
"""


class Graph:
    """Adjacency-list graph: O(V+E) space, O(degree) neighbor iteration."""

    def __init__(self, n, directed=False):
        self.n = n
        self.directed = directed
        self._adj = [[] for _ in range(n)]

    # region: add_edge
    def add_edge(self, u, v):
        """O(1): append v to u's neighbor list (and u to v's, if undirected)."""
        self._adj[u].append(v)
        if not self.directed:
            self._adj[v].append(u)
    # endregion

    # region: neighbors
    def neighbors(self, u):
        """O(1) to get the list; iterating it is O(degree(u)) — you touch only u's actual
        neighbors, never the vertices it doesn't connect to. This is why traversals over a
        sparse graph are O(V+E) with a list."""
        return self._adj[u]
    # endregion

    def has_edge(self, u, v):
        """O(degree(u)): scan u's neighbors. The list's weak spot — the matrix does this
        in O(1)."""
        return v in self._adj[u]

    def edge_count(self):
        total = sum(len(a) for a in self._adj)
        return total if self.directed else total // 2


class MatrixGraph:
    """Adjacency-matrix graph: O(V²) space, O(1) edge test, O(V) neighbor iteration."""

    def __init__(self, n, directed=False):
        self.n = n
        self.directed = directed
        self._m = [[0] * n for _ in range(n)]

    # region: matrix
    def add_edge(self, u, v):
        """O(1): set the cell (and its mirror, if undirected)."""
        self._m[u][v] = 1
        if not self.directed:
            self._m[v][u] = 1

    def has_edge(self, u, v):
        """O(1): one array lookup — the matrix's whole advantage."""
        return self._m[u][v] == 1

    def neighbors(self, u):
        """O(V): scan the entire row, even the zeros — the matrix's whole disadvantage on
        a sparse graph, where almost every cell is 0."""
        return [v for v in range(self.n) if self._m[u][v]]
    # endregion

"""The graph library everyone uses in Python is the third-party `networkx` — a `nx.Graph`
is an adjacency structure (a dict of dicts) with hundreds of algorithms built on top. In
the standard library there's no graph type; you build one from dicts or lists, exactly as
here. So the counterpart for this chapter is the two representations against each other,
measured on the thing that separates them — memory on a sparse graph, and edge-lookup
speed — with `networkx`'s dict-of-dicts being essentially the adjacency-list approach.
"""
import sys


# region: memory
def list_memory(graph):
    """Rough memory of an adjacency-list graph: proportional to V + E (the neighbor
    entries)."""
    total = sys.getsizeof(graph._adj)
    for row in graph._adj:
        total += sys.getsizeof(row) + sum(sys.getsizeof(x) for x in row[:0])  # container overhead
        total += 8 * len(row)                          # ~8 bytes per neighbor reference
    return total


def matrix_memory(graph):
    """Rough memory of an adjacency-matrix graph: proportional to V² regardless of how
    many edges actually exist."""
    return graph.n * graph.n * 8                        # ~8 bytes per cell
# endregion

Desde cero vs librería

Aquí no hay una medición de tiempos mano a mano, porque las representaciones no son implementaciones que compitan por hacer lo mismo — son dos estructuras de datos distintas con costos que son espejo una de la otra, y el "ganador" depende por completo de tu grafo. La gráfica de memoria es la comparación decisiva: 286× con 4000 vértices dispersos, creciendo de forma cuadrática. La conclusión práctica es una regla que vas a aplicar durante los siguientes diez capítulos: usa la lista de adyacencia por defecto, porque los grafos reales son dispersos y la lista mantiene sus algoritmos en O(V+E); recurre a la matriz solo cuando el grafo sea genuinamente denso o cuando las pruebas de arista en tiempo constante dominen tu carga de trabajo. Todos los algoritmos de grafos que vienen asumen una lista de adyacencia salvo que específicamente quieran una matriz — y saber por qué es saber que la representación, elegida antes de que corra cualquier algoritmo, es lo que define el costo del algoritmo.

Dónde te lo vas a encontrar

Te encuentras estas representaciones debajo de cada grafo que tocas. Las redes sociales guardan el grafo de seguidores/amigos como listas de adyacencia (una matriz de miles de millones de usuarios al cuadrado es impensable). Los crawlers web y PageRank operan sobre el grafo de enlaces como estructuras de adyacencia dispersas. Los compiladores construyen grafos de dependencias y de flujo de control como listas de adyacencia. Los protocolos de ruteo representan las redes como grafos con pesos. El GPS y los mapas guardan las redes de carreteras como listas de adyacencia con las distancias como pesos. Y cuando el rendimiento de verdad importa, una variante comprimida llamada CSR (compressed sparse row) empaqueta una lista de adyacencia en arrays planos para un recorrido amigable con el cache — la representación detrás del procesamiento de grafos de alto rendimiento y del álgebra lineal dispersa. La matriz, por su parte, aparece donde los grafos son pequeños y densos o donde los algoritmos tienen forma de matriz, como los caminos más cortos entre todos los pares.

Puntos clave

Un grafo son vértices y aristas, y la primera decisión es cómo guardarlo: una lista de adyacencia (espacio O(V+E), operaciones O(degree)) o una matriz de adyacencia (espacio O(V²), prueba de arista O(1)). Como los grafos reales son dispersos, la lista es la opción por defecto — mantiene la memoria lineal y, sobre todo, deja todo recorrido en O(V+E) donde una matriz forzaría O(V²). La matriz es la especialista para grafos densos y cargas de trabajo pesadas en pruebas de arista. Encima de eso agrega dirigido/no dirigido y con pesos, y la lista de adyacencia dirigida con pesos es sobre lo que corre casi todo este nivel.

Ya con un grafo en mano, el resto del nivel se trata de hacerle preguntas. La primera y más fundamental es la alcanzabilidad: empezando en algún lado, ¿a dónde puedes llegar, y en qué orden? Los siguientes dos capítulos responden eso con los dos grandes recorridos de grafos — búsqueda en anchura, que usa la cola del nivel de estructuras lineales para explorar de lo más cercano hacia afuera, y búsqueda en profundidad, que usa la pila (o la recursión) para clavarse hasta el fondo. Todo algoritmo de grafos después de ellos es uno de estos dos recorridos con algo extra encima.