Grafos: Matriz de adyacencia vs. Lista de adyacencia

Al finalizar este tema

Comprenderá qué es un grafo y las diferencias entre sus dos formas de representación: la matriz de adyacencia y la lista de adyacencia.

Los árboles son un caso especial de grafos

Las estructuras de datos que hemos visto hasta ahora —arrays, listas enlazadas y árboles— tienen relaciones simples entre los datos. En un array, la relación es de orden; en un árbol, es jerárquica.

Sin embargo, las relaciones del mundo real son complejas. En las redes sociales, las personas se siguen entre sí. Las ciudades están conectadas por carreteras. Las páginas web están vinculadas mediante enlaces. La estructura de datos que representa estas relaciones de muchos a muchos es el grafo (Graph).

Un grafo está compuesto por nodos (o vértices) y aristas que conectan los nodos. Un árbol también es un tipo de grafo, pero es un grafo especial que posee la restricción de "padre-hijo" y la condición de "ausencia de ciclos".

Grafos dirigidos vs. no dirigidos

Grafo no dirigido: Si A está conectado con B, se puede ir tanto de A a B como de B a A. Es como la relación de amistad en Facebook: si tú eres amigo de alguien, esa persona también es tu amiga.

Grafo dirigido: Solo es posible ir de A a B, pero no necesariamente de B a A. Es como seguir a alguien en Instagram: que tú sigas a otra persona no significa que esa persona te siga a ti.

Matriz de adyacencia: una matriz bidimensional

Se representa un grafo con 5 nodos mediante una matriz de 5×5. matrix[i][j] = 1 indica que existe una arista desde el nodo $i$ hacia el nodo $j$.

A  B  C  D
A [ 0, 1, 1, 0 ]
B [ 1, 0, 0, 1 ]
C [ 1, 0, 0, 1 ]
D [ 0, 1, 1, 0 ]

Es un grafo no dirigido con las conexiones A-B, A-C, B-D y C-D. Al ser no dirigido, la matriz es simétrica respecto a la diagonal principal.

graph = [
    [0, 1, 1, 0],
    [1, 0, 0, 1],
    [1, 0, 0, 1],
    [0, 1, 1, 0],
]

# Verificar si A y B están conectados
if graph[0][1] == 1:
    print("A-B conectado")  # O(1)

Ventajas: Verificar si dos nodos están conectados es O(1). Se accede directamente mediante índices.

Desventajas: Si hay N nodos, se requiere una matriz de tamaño N×N. Con 10.000 nodos, se necesitan 100 millones de celdas. Ocupa todo el espacio incluso si hay pocas aristas.

Lista de adyacencia: lista de conexiones

Cada nodo almacena "la lista de nodos conectados a este nodo".

A: [B, C]
B: [A, D]
C: [A, D]
D: [B, C]

Es el mismo gráfico, pero la forma de representarlo es diferente.

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C'],
}

# Recorrer los nodos vecinos de A
for neighbor in graph['A']:
    print(neighbor)  # B, C

Ventajas: Utiliza memoria proporcional al número de aristas. Aunque haya 10 000 nodos, si hay 100 aristas, solo se requiere espacio para 100 aristas.

Desventajas: Para comprobar si dos nodos están conectados, es necesario recorrer la lista. En el peor de los casos, la complejidad es O(N).

¿Cuál elegir?

| Matriz de adyacencia       | Lista de adyacencia
---------+------------------+------------------
Verificar conexión  | O(1)             | O(grado)
Recorrido de vecinos  | O(V)             | O(grado)
Caso adecuado | Grafos densos con muchas aristas | Grafos dispersos con pocas aristas
Caso adecuado | Grafos densos con muchas aristas | Grafos dispersos con pocas aristas

Grafo denso: Tiene muchas aristas en relación con el número de nodos. Por ejemplo, una red aérea con vuelos directos entre todas las ciudades. La matriz de adyacencia es adecuada para este caso.

Grafo disperso: Tiene pocas aristas en relación con el número de nodos. Por ejemplo, en una red social de 100 millones de usuarios, cada usuario sigue a un promedio de 200 personas. La lista de adyacencia es adecuada para este caso.

La mayoría de los grafos en entornos reales son grafos dispersos. Por ello, la lista de adyacencia es la opción predeterminada. En las pruebas de programación (coding tests), lo ideal es pensar primero en la lista de adyacencia.

Grafo ponderado

Las aristas pueden tener un peso (weight). Por ejemplo, la distancia entre ciudades o la latencia de una red.

En la matriz de adyacencia, se coloca el valor del peso en lugar de 1:

# matrix[A][B] = distancia
matrix = [
    [0, 5, 3, 0],
    [5, 0, 0, 2],
    ...
]

En la lista de adyacencia, se representa mediante una tupla:

graph = {
    'A': [('B', 5), ('C', 3)],
    'B': [('A', 5), ('D', 2)],
    ...
}

Para encontrar la ruta más corta en un grafo ponderado, se utiliza el algoritmo de Dijkstra en lugar de BFS. BFS encuentra la ruta más corta basada en el número de aristas, mientras que Dijkstra lo hace basada en la suma de los pesos.

Conceptos clave

Un grafo es una estructura de datos que representa relaciones de muchos a muchos mediante nodos y aristas. La matriz de adyacencia permite verificar la conexión en O(1), pero utiliza un espacio de O(V^2). La lista de adyacencia solo utiliza un espacio de O(V+E) y es la opción predeterminada en la mayoría de los grafos en la práctica.