← Estructuras de datos desde cero · Lección 24/32
Puntos y líneas: qué es un grafo
Vértices y aristas
Un grafo es un montón de vértices (puntos) unidos por aristas (líneas). Sirve para todo lo que son relaciones: pueblos y carreteras, personas y amistades, páginas y enlaces, casillas de un mapa y sus vecinas.
Los árboles de las unidades anteriores son un caso especial: un grafo sin ciclos donde cada nodo tiene un solo padre. En un grafo general puede haber ciclos, varios caminos entre dos puntos y pedazos sueltos.
El grado de un vértice es cuántas aristas lo tocan. Como cada arista toca dos vértices, la suma de todos los grados es el doble de las aristas.
$ node leccion.js
Pulsa CORRER (o Ctrl+Enter).
Qué mirar
- B y C tienen grado 3; A, D y E, grado 2. Compáralo con el dibujo.
- La suma da 12, el doble de las 6 aristas.
Toda la lección en una página
Vértices y aristas
Un grafo es un montón de vértices (puntos) unidos por aristas (líneas). Sirve para todo lo que son relaciones: pueblos y carreteras, personas y amistades, páginas y enlaces, casillas de un mapa y sus vecinas.
Los árboles de las unidades anteriores son un caso especial: un grafo sin ciclos donde cada nodo tiene un solo padre. En un grafo general puede haber ciclos, varios caminos entre dos puntos y pedazos sueltos.
El grado de un vértice es cuántas aristas lo tocan. Como cada arista toca dos vértices, la suma de todos los grados es el doble de las aristas.
const vertices = ["A", "B", "C", "D", "E"];
const aristas = [["A", "B"], ["A", "C"], ["B", "C"], ["B", "D"], ["C", "E"], ["D", "E"]];
console.log(vertices.length, "vértices,", aristas.length, "aristas");
const grado = {};
for (const v of vertices) grado[v] = 0;
for (const [a, b] of aristas) {
grado[a]++;
grado[b]++;
}
console.log(grado);
let suma = 0;
for (const v of vertices) suma += grado[v];
console.log("suma de grados:", suma);
- B y C tienen grado 3; A, D y E, grado 2. Compáralo con el dibujo.
- La suma da 12, el doble de las 6 aristas.
Lista de adyacencia
Una lista de aristas sirve para guardar el grafo, pero no para preguntar «¿quiénes son los vecinos de C?» sin revisarlas todas. Lo más usado es la lista de adyacencia: a cada vértice le toca un arreglo con sus vecinos. En JavaScript, un Map (o un objeto) de vértice a arreglo.
En un grafo no dirigido cada arista se anota dos veces, una en cada punta. Ocupa memoria O(V + E) (vértices más aristas), y recorrer los vecinos de un vértice cuesta lo que tenga de vecinos.
const vertices = ["A", "B", "C", "D", "E"];
const aristas = [["A", "B"], ["A", "C"], ["B", "C"], ["B", "D"], ["C", "E"], ["D", "E"]];
const ady = new Map();
for (const v of vertices) ady.set(v, []);
for (const [a, b] of aristas) {
ady.get(a).push(b);
ady.get(b).push(a); // no dirigido: en los dos sentidos
}
console.log(ady);
console.log("vecinos de C:", ady.get("C"));
console.log("¿B y E son vecinos?", ady.get("B").includes("E"));
- Cada vértice tiene su arreglo de vecinos; la arista A–B aparece en el de A y en el de B.
- Los vecinos de C salen directo:
[A, B, E]. - Preguntar si B y E son vecinos obliga a revisar la lista de B: es
false.
Matriz de adyacencia
La otra forma es una matriz de V × V: la casilla [i][j] vale 1 si hay arista entre i y j, y 0 si no. Preguntar si dos vértices están unidos cuesta O(1), pero la matriz ocupa O(V²) aunque casi no haya aristas.
Regla práctica: lista de adyacencia casi siempre; matriz cuando el grafo es chico o casi todos están unidos con todos.
const vertices = ["A", "B", "C", "D", "E"];
const aristas = [["A", "B"], ["A", "C"], ["B", "C"], ["B", "D"], ["C", "E"], ["D", "E"]];
const indice = {};
vertices.forEach((v, i) => { indice[v] = i; });
const n = vertices.length;
const matriz = Array.from({ length: n }, () => new Array(n).fill(0));
for (const [a, b] of aristas) {
matriz[indice[a]][indice[b]] = 1;
matriz[indice[b]][indice[a]] = 1;
}
console.log(" " + vertices.join(" "));
for (let i = 0; i < n; i++) console.log(vertices[i], matriz[i].join(" "));
console.log("¿B y E?", matriz[indice.B][indice.E] === 1);
- La matriz es simétrica: en un grafo no dirigido,
[i][j]y[j][i]siempre coinciden. - De 25 casillas, sólo 12 tienen un 1. Con mil vértices serían un millón de casillas, casi todas en cero.
Con flecha y con peso
Dos variantes que vienen en las siguientes lecciones:
- Dirigido: la arista tiene sentido, como seguir a alguien en una red (tú lo sigues; él a ti, quién sabe). Se anota una sola vez, en el vértice de salida.
- Con pesos: cada arista lleva un número, como los kilómetros de una carretera o el costo de un vuelo. En la lista de adyacencia, cada vecino va con su peso:
[vecino, peso].
El dibujo es dirigido y con pesos.
const aristas = [["A", "B", 4], ["A", "C", 2], ["C", "B", 1], ["B", "D", 5], ["C", "D", 8]];
const ady = {};
for (const [a, b, peso] of aristas) {
if (!ady[a]) ady[a] = [];
if (!ady[b]) ady[b] = [];
ady[a].push([b, peso]); // dirigido: sólo de a hacia b
}
console.log(ady);
console.log("de C se puede ir a:", ady.C.map(([v]) => v));
console.log("de D se puede ir a:", ady.D.map(([v]) => v));
- Cada vecino trae su peso: de A a B cuesta 4 y de A a C, 2.
- D no tiene salidas: todas las flechas llegan a él y ninguna sale. En un grafo dirigido, «vecino» depende del sentido.