Una lista de adyacencia guarda, para cada vértice, los vecinos conectados con él. Es una de las representaciones más utilizadas por su eficiencia y facilidad para recorrer grafos.
Un dibujo ayuda a comprender un grafo, pero un programa necesita almacenarlo en memoria. Una de las formas más comunes consiste en asociar cada vértice con una colección de sus vecinos.
Esta estructura recibe el nombre de lista de adyacencia. Resulta especialmente conveniente cuando el grafo posee relativamente pocas aristas frente a la cantidad máxima posible.
Para cada vértice creamos una entrada que contiene todos los vértices conectados directamente con él.
La lista indica que A es adyacente a B y C; B es adyacente a A y D, y así sucesivamente.
En un grafo no dirigido, cada arista aparece en las listas de sus dos extremos. Si existe {A, B}, B se agrega a la lista de A y A se agrega a la lista de B.
Esta duplicación no representa dos aristas: son las dos incidencias de una única conexión no dirigida.
En un grafo dirigido, la lista suele guardar los destinos alcanzables desde cada vértice. El arco A→B agrega B a la lista de A, pero no agrega A a la lista de B.
| Tipo | Conexión | Resultado |
|---|---|---|
| No dirigido | A—B | A: [B] y B: [A] |
| Dirigido | A→B | A: [B] y B: [] |
Si necesitamos consultar entradas con frecuencia, podemos mantener además una lista inversa con los arcos que llegan a cada vértice.
Selecciona dos vértices para agregar o quitar una conexión. La lista de adyacencia se actualiza inmediatamente. En modo dirigido, el primer nodo es el origen y el segundo, el destino.
Lista de adyacencia
A: [B, C] B: [A, D] C: [A, E] D: [B, E] E: [C, D]
Observa cómo una arista no dirigida actualiza dos listas, mientras que un arco dirigido modifica solamente la lista de su origen.
En JavaScript, Map permite asociar cada vértice con un arreglo o conjunto de vecinos.
const grafo = new Map();
grafo.set("A", ["B", "C"]);
grafo.set("B", ["A", "D"]);
grafo.set("C", ["A"]);
grafo.set("D", ["B"]);
console.log(grafo.get("A"));
console.log(grafo.get("D"));Una implementación reutilizable debe crear listas vacías para los vértices y actualizar ambos extremos al agregar una arista no dirigida.
const adyacencia = new Map();
function agregarVertice(v) {
if (!adyacencia.has(v)) adyacencia.set(v, new Set());
}
function agregarArista(a, b) {
agregarVertice(a);
agregarVertice(b);
adyacencia.get(a).add(b);
adyacencia.get(b).add(a);
}
agregarArista("A", "B");
agregarArista("A", "C");
console.log([...adyacencia.get("A")]);Utilizar Set evita insertar accidentalmente el mismo vecino más de una vez.
La lista ofrece acceso directo a todos los vecinos. En un grafo no dirigido, su longitud coincide con el grado del vértice si no hay bucles ni aristas múltiples.
Esta operación es eficiente porque no necesitamos revisar todas las aristas del grafo.
Una lista de adyacencia almacena una entrada por vértice y referencias para las aristas.
En grafos no dirigidos cada arista aparece dos veces, pero el factor constante no modifica la complejidad. Esta eficiencia vuelve a las listas adecuadas para grafos dispersos.
| Aspecto | Ventaja | Desventaja |
|---|---|---|
| Memoria | Usa O(V + E) | En grafos muy densos pierde ventaja |
| Recorrer vecinos | Acceso directo y eficiente | Depende del grado del vértice |
| Comprobar una arista | Rápido con Set | Con arreglos puede requerir búsqueda |
| Agregar conexiones | Operación sencilla | Hay que mantener ambos extremos |
Si las aristas tienen pesos, cada vecino puede almacenarse junto con el valor correspondiente.
Esta representación permite recorrer las conexiones y consultar sus costos, como requieren algoritmos de caminos mínimos.
Las listas de adyacencia ofrecen una representación compacta y práctica para la mayoría de los grafos utilizados en programación. Su estructura coincide naturalmente con la operación de visitar vecinos.
En el próximo tema estudiaremos las matrices de adyacencia, que representan todas las parejas posibles mediante una tabla bidimensional.