Los algoritmos de grafos recorren conexiones, determinan alcanzabilidad, ordenan dependencias, encuentran rutas y seleccionan enlaces de bajo costo. Elegir el algoritmo adecuado depende de la dirección, los pesos y la pregunta que se quiere responder.
Una representación de grafo guarda conexiones; un algoritmo sobre grafos extrae información de esas conexiones. Puede descubrir todos los nodos alcanzables, hallar una ruta corta, detectar un ciclo o planificar tareas.
Antes de elegir un algoritmo debemos preguntar: ¿el grafo es dirigido?, ¿tiene pesos?, ¿pueden ser negativos?, ¿se busca una ruta, un orden o una estructura de bajo costo? Estas condiciones determinan qué método es correcto.
Usaremos V para la cantidad de vértices y E para la cantidad de aristas. Con una lista de adyacencia, recorrer todos los vecinos de todos los vértices cuesta normalmente O(V + E).
La complejidad asintótica orienta la elección, pero también importan el tamaño de los datos, la memoria disponible y si se necesitan una o muchas consultas.
La búsqueda en anchura, BFS por breadth-first search, explora primero todos los vecinos del origen, luego los vértices a distancia dos y así sucesivamente. Usa una cola.
BFS es apropiado para calcular saltos mínimos entre usuarios, buscar la salida más cercana en una grilla o descubrir una componente conexa.
function bfs(adyacentes, origen) {
if (!adyacentes.has(origen)) throw new Error("origen inexistente");
const distancia = new Map([[origen, 0]]);
const anterior = new Map();
const cola = [origen];
let cabeza = 0;
while (cabeza < cola.length) {
const actual = cola[cabeza++];
for (const vecino of adyacentes.get(actual) ?? []) {
if (distancia.has(vecino)) continue;
distancia.set(vecino, distancia.get(actual) + 1);
anterior.set(vecino, actual);
cola.push(vecino);
}
}
return { distancia, anterior };
}
const red = new Map([
["A", new Set(["B", "C"])],
["B", new Set(["D"])],
["C", new Set(["D", "E"])],
["D", new Set(["E"])],
["E", new Set()]
]);
console.log(bfs(red, "A").distancia.get("E")); // 2Marcar un vecino al encolarlo evita procesarlo varias veces. El índice cabeza evita el costo de shift(); con listas de adyacencia, BFS cuesta O(V + E).
El mapa de predecesores permite recuperar una ruta desde el destino hasta el origen y luego invertirla.
function reconstruirCamino(anterior, origen, destino) {
if (origen === destino) return [origen];
if (!anterior.has(destino)) return null;
const camino = [destino];
let actual = destino;
while (actual !== origen) {
actual = anterior.get(actual);
camino.push(actual);
}
return camino.reverse();
}
const resultado = bfs(red, "A");
console.log(reconstruirCamino(resultado.anterior, "A", "E"));
// ["A", "C", "E"]Puede haber varias rutas mínimas. La ruta concreta depende del orden en que estén almacenados los vecinos, pero su longitud coincide con la distancia calculada por BFS.
La búsqueda en profundidad, DFS por depth-first search, sigue una rama tan lejos como puede antes de retroceder. Se implementa con recursión o una pila explícita.
En ambos recorridos se necesita una marca de visitado para terminar correctamente cuando existen ciclos.
function dfs(adyacentes, origen) {
if (!adyacentes.has(origen)) throw new Error("origen inexistente");
const visitados = new Set();
const pila = [origen];
const orden = [];
while (pila.length > 0) {
const actual = pila.pop();
if (visitados.has(actual)) continue;
visitados.add(actual);
orden.push(actual);
for (const vecino of adyacentes.get(actual) ?? []) {
if (!visitados.has(vecino)) pila.push(vecino);
}
}
return orden;
}
console.log(dfs(red, "A")); // un orden de exploración válidoEl orden exacto puede variar con la lista de vecinos. La propiedad esencial es que cada vértice alcanzable se visita una vez, con costo O(V + E).
| Aspecto | BFS | DFS |
|---|---|---|
| Estructura principal | cola | pila o recursión |
| Exploración | por niveles | por ramas |
| Camino mínimo no ponderado | sí | no en general |
| Aplicaciones | distancias, cercanía, saltos | ciclos, componentes, ordenación |
| Complejidad usual | O(V + E) | O(V + E) |
La diferencia no es cuál visita más vértices, sino el orden de visita y la información que ese orden permite deducir.
En DFS de un digrafo, una arista hacia un vértice que aún está en la ruta de exploración revela un ciclo dirigido. Para detectarlo se distinguen tres estados: no visitado, en proceso y terminado.
Esta técnica permite identificar dependencias circulares. No basta con saber que un vértice fue visitado: se debe saber si aún pertenece a la cadena activa.
Un orden topológico es una lista de los vértices de un DAG tal que toda arista u → v coloca a u antes que v. Es útil para prerequisitos y tareas dependientes.
La dirección de las aristas debe definirse con cuidado. Si una arista significa «depende de», se interpreta en sentido contrario al de una arista que significa «habilita».
El algoritmo de Kahn comienza con vértices de grado de entrada cero. Los elimina conceptualmente y reduce el grado de entrada de sus vecinos. Cada vértice que queda en cero pasa a estar disponible.
function ordenTopologico(adyacentes) {
const gradoEntrada = new Map();
for (const vertice of adyacentes.keys()) gradoEntrada.set(vertice, 0);
for (const vecinos of adyacentes.values()) {
for (const vecino of vecinos) {
gradoEntrada.set(vecino, (gradoEntrada.get(vecino) ?? 0) + 1);
}
}
const cola = [...gradoEntrada].filter(([, grado]) => grado === 0).map(([v]) => v);
const orden = [];
let cabeza = 0;
while (cabeza < cola.length) {
const actual = cola[cabeza++];
orden.push(actual);
for (const vecino of adyacentes.get(actual) ?? []) {
const nuevoGrado = gradoEntrada.get(vecino) - 1;
gradoEntrada.set(vecino, nuevoGrado);
if (nuevoGrado === 0) cola.push(vecino);
}
}
return orden.length === gradoEntrada.size ? orden : null;
}Si el resultado es null, quedaron vértices con grado de entrada positivo: existe un ciclo. Con listas de adyacencia, el algoritmo cuesta O(V + E).
Cuando cada arista tiene un costo, el camino con menos aristas no necesariamente es el más barato. El problema de camino mínimo busca minimizar la suma de pesos.
BFS es correcto si todas las aristas tienen el mismo costo. Para pesos no negativos se utiliza habitualmente el algoritmo de Dijkstra.
Dijkstra mantiene la mejor distancia conocida desde un origen. En cada paso elige el vértice pendiente con distancia menor y relaja sus aristas, intentando mejorar la distancia de cada vecino.
Una cola de prioridad implementa eficientemente la elección del mínimo. La versión siguiente busca el mínimo por escaneo para mostrar con claridad la lógica del algoritmo.
function dijkstra(adyacentes, origen) {
if (!adyacentes.has(origen)) throw new Error("origen inexistente");
const distancia = new Map([...adyacentes.keys()].map(v => [v, Infinity]));
const anterior = new Map();
const pendientes = new Set(adyacentes.keys());
distancia.set(origen, 0);
while (pendientes.size > 0) {
let actual = null;
for (const vertice of pendientes) {
if (actual === null || distancia.get(vertice) < distancia.get(actual)) actual = vertice;
}
if (distancia.get(actual) === Infinity) break;
pendientes.delete(actual);
for (const { destino, peso } of adyacentes.get(actual) ?? []) {
if (peso < 0) throw new Error("Dijkstra no admite pesos negativos");
const alternativa = distancia.get(actual) + peso;
if (alternativa < distancia.get(destino)) {
distancia.set(destino, alternativa);
anterior.set(destino, actual);
}
}
}
return { distancia, anterior };
}La función supone que cada vértice aparece como clave del mapa, incluso si no tiene salidas. Esta versión cuesta O(V² + E); con una cola de prioridad suele obtenerse O((V + E) log V).
Dijkstra puede fallar con una arista de peso negativo, porque una distancia ya considerada definitiva podría mejorar más tarde. Bellman-Ford es una alternativa que admite esos pesos.
Un ciclo de peso negativo permite reducir el costo sin límite recorriéndolo repetidamente, por lo que no existe un camino mínimo finito en el sentido habitual.
En un grafo no dirigido, conexo y ponderado, un árbol de expansión mínima conecta todos los vértices con n - 1 aristas y el menor peso total posible.
Este problema aparece al planificar redes de cable, tuberías o enlaces cuando se busca conectividad global con un presupuesto mínimo.
Kruskal ordena las aristas de menor a mayor peso e incorpora una arista solo si sus extremos pertenecen a componentes distintas. Así nunca crea un ciclo.
La complejidad está dominada por ordenar las aristas: O(E log E). Si el grafo está desconectado, el resultado es un bosque de expansión mínima.
function kruskal(vertices, aristas) {
const padre = new Map([...vertices].map(v => [v, v]));
function encontrar(v) {
if (padre.get(v) !== v) padre.set(v, encontrar(padre.get(v)));
return padre.get(v);
}
function unir(a, b) {
const raizA = encontrar(a);
const raizB = encontrar(b);
if (raizA === raizB) return false;
padre.set(raizA, raizB);
return true;
}
const arbol = [];
for (const arista of [...aristas].sort((x, y) => x.peso - y.peso)) {
if (unir(arista.origen, arista.destino)) arbol.push(arista);
}
return arbol;
}
const aristas = [
{ origen: "A", destino: "B", peso: 4 },
{ origen: "A", destino: "C", peso: 2 },
{ origen: "B", destino: "C", peso: 1 }
];
console.log(kruskal(["A", "B", "C"], aristas));El resultado usa A—C de peso 2 y B—C de peso 1. La estructura de conjuntos disjuntos evita agregar A—B, ya que entonces sus extremos ya están conectados por las aristas elegidas.
| Problema | Algoritmo habitual | Condición |
|---|---|---|
| Vértices alcanzables | BFS o DFS | grafo general |
| Menos aristas desde un origen | BFS | no ponderado |
| Ordenar prerequisitos | orden topológico | DAG dirigido |
| Menor costo desde un origen | Dijkstra | pesos no negativos |
| Pesos negativos | Bellman-Ford | sin ciclo negativo útil |
| Conectar al menor costo total | Kruskal o Prim | no dirigido ponderado |
Los objetivos no son intercambiables: un árbol de expansión mínima no garantiza rutas más cortas desde un vértice concreto.
Las pruebas de algoritmos de grafos deben incluir vértices aislados, destinos inalcanzables, ciclos, aristas duplicadas, pesos cero y direcciones invertidas.
La representación debe contener explícitamente los vértices aislados cuando el algoritmo necesita distinguirlos de vértices inexistentes.
Los algoritmos convierten grafos en respuestas operativas: rutas, órdenes, costos y conexiones esenciales. En el próximo tema veremos aplicaciones concretas de grafos en programación y sistemas reales.