Algoritmos de grafos: BFS, Dijkstra y Kruskal demostrados paso a paso

Tres objetivos distintos: llegar en menos pasos, encontrar la ruta más barata y conectar todos los puntos con el menor coste total. Un mismo grafo permite distinguirlos.

Un grafo consta de vértices V y aristas E. Este es simple, no dirigido y conexo: cada enlace se recorre en ambos sentidos. Tiene 6 vértices y 9 aristas. Los números son costes, no longitudes del dibujo. Procesamos los vecinos alfabéticamente y desempatamos las aristas del mismo peso por su nombre. Un camino une vértices; un ciclo vuelve al inicio sin repetir los demás vértices. Un árbol es conexo y no tiene ciclos.

A–B: 4   A–C: 2   B–C: 1   B–D: 5   C–D: 8   C–E: 10   D–E: 2   D–F: 6   E–F: 3

Líneas verdes continuas: aristas elegidas o predecesores actuales; grises discontinuas: otras aristas. BFS omite los pesos. Los predecesores intermedios de Dijkstra pueden cambiar. ∞ indica distancia aún desconocida.

1. BFS: el menor número de pasos

La búsqueda en anchura ignora los pesos: cada arista cuenta como un paso. Desde A buscamos el menor número de aristas hasta cada vértice alcanzable. Una cola FIFO extrae primero el elemento que entró primero.

Asigna d(A)=0 y encola A. Extrae el primer vértice u; para cada vecino v no descubierto asigna d(v)=d(u)+1, registra u como predecesor y encola v. Marca v al encolarlo, no al extraerlo, para evitar duplicados. Continúa hasta vaciar la cola.

Después de A: [B,C]. B descubre D; C descubre E sin modificar D. D descubre F. A–B–D–F tiene 3 aristas; A–C–E–F también: puede haber varias soluciones. La primera ruta cuesta 15, de modo que menos pasos no significa menor coste.

Por qué funciona

1. Invariante: la cola mantiene distancias no decrecientes. Mientras se procesa el nivel k, los nuevos vértices entran al final en el nivel k+1.
2. Base: A está correctamente en el nivel 0. Supón correctas las distancias hasta el nivel k. Cada nuevo vecino de un vértice de nivel k se alcanza en k+1 aristas.
3. No puede existir un camino más corto: su predecesor en él habría sido procesado en un nivel anterior y ya lo habría descubierto. La primera distancia asignada es mínima. Los predecesores reconstruyen un camino mínimo.

Con listas de adyacencia cada vértice se encola una vez y cada arista se examina dos veces: tiempo O(|V|+|E|), memoria auxiliar O(|V|), aparte del grafo. En un grafo no conexo solo se visita la componente de A.

Princeton · Algorithms, 4th Edition — BFS

2. Dijkstra: el camino de coste mínimo

Los pesos ahora importan y deben ser no negativos. d(v) es el mejor coste encontrado, inicialmente infinito salvo d(A)=0. S contiene los vértices con distancia definitiva.

Elige fuera de S el vértice u con menor d(u) y añádelo a S. Para cada vecino v fuera de S, relaja la arista: d(v) ← min(d(v), d(u)+w(u,v)). Actualiza el predecesor si mejora. Si el mínimo es infinito, los vértices restantes son inalcanzables.

Después de A: B=4, C=2. C mejora B a 3, propone D=10 y E=12. B mejora D a 8. D mejora E a 10 y propone F=14. E mejora F a 13. A–C–B–D–E–F cuesta 2+1+5+2+3=13, pero utiliza 5 aristas, más que BFS.

Por qué funciona

1. Cada estimación finita corresponde a un camino real y no subestima el óptimo. Supón correctas las distancias ya fijadas en S.
2. Si u tuviera un camino más barato, sea y su primer vértice fuera de S y x su predecesor dentro de S. Al procesar x, la relajación asignó a y una estimación no mayor que el coste de ese prefijo.
3. Los pesos restantes son no negativos: el prefijo no cuesta más que el camino completo hasta u. Entonces d(y) sería menor que d(u), contradiciendo la elección del mínimo. La distancia de u es correcta; la inducción demuestra todas las extracciones.

Con listas de adyacencia y un montículo binario con disminución de clave: O((|V|+|E|) log |V|), memoria auxiliar O(|V|). Buscar cada mínimo recorriendo los vértices cuesta O(|V|²+|E|). Los pesos negativos invalidan la prueba: con A→B=2, A→C=5, C→B=−10, B se fijaría en 2 aunque su mínimo es −5.

Princeton · Algorithms, 4th Edition — Dijkstra

3. Kruskal: conectar todo al menor coste

Buscamos una red que conecte todos los vértices minimizando la suma de pesos, no una ruta de A a F. Es un árbol de expansión mínima (MST). Un árbol de 6 vértices tiene exactamente 5 aristas.

Ordena las aristas por peso creciente. Cada vértice comienza en una componente separada. Acepta una arista solo si conecta componentes distintas; de lo contrario crea un ciclo. Union-Find comprueba y fusiona las componentes. Termina tras |V|−1 aristas aceptadas.

Orden inicial: BC(1), AC(2), DE(2), EF(3), AB(4), BD(5). Se rechaza AB porque A y B ya están unidos mediante C: cerraría A–C–B–A. BD une {A,B,C} con {D,E,F}. Total: 1+2+2+3+5=13. DF(6), CD(8), CE(10) ya no se necesitan.

Por qué funciona: argumento de intercambio

1. Invariante: existe un MST T que contiene las aristas F ya elegidas. Se cumple con F vacío. Sea e la siguiente arista aceptada entre dos componentes de F.
2. Si e pertenece a T, no cambia nada. Si no, al añadirla aparece un único ciclo. Este contiene una arista f que sale de la componente de un extremo de e; f no pertenece a F. Además w(f)≥w(e): una arista más ligera que cruzara esa componente se habría procesado antes y habría unido las componentes.
3. Sustituye f por e: sigue siendo un árbol y el coste no aumenta. Como T era mínimo, el nuevo árbol también lo es y contiene F junto con e. Se conserva el invariante. Tras |V|−1 elecciones, el árbol construido es un MST.

Ordenación O(|E| log |E|). Union-Find con compresión de caminos y unión por rango: O(|E| α(|V|)) total, casi lineal. Memoria O(|V|+|E|), incluyendo aristas ordenadas. Admite pesos negativos. Si el grafo no es conexo, produce un bosque de expansión mínima.

Princeton · Algorithms, 4th Edition — Kruskal

Aquí Dijkstra y Kruskal dan 13 y las mismas aristas por coincidencia. En el triángulo AB=2, AC=2, BC=1, el árbol de caminos mínimos desde A usa AB y AC, total 4. Un MST usa BC y una arista de peso 2, total 3; en ese árbol un camino desde A cuesta 3 en lugar de 2. Los objetivos son diferentes.