Grafos: BFS, DFS y Dijkstra

Qué es un grafo

Un grafo es un conjunto de nodos unidos por aristas. Modela casi todo: calles y cruces en un GPS, routers y enlaces en Internet, materias y prerrequisitos en una malla curricular, o tareas y dependencias en un proyecto. Si las aristas tienen un costo (distancia, tiempo, latencia), el grafo es ponderado.

Los tres algoritmos

• BFS (búsqueda en anchura): visita por niveles usando una cola. En grafos sin pesos encuentra el camino con menos aristas.
• DFS (búsqueda en profundidad): avanza lo más lejos posible usando una pila y luego retrocede. Sirve para detectar ciclos, componentes conexas u orden topológico.
• Dijkstra: en cada paso fija el nodo no visitado con menor distancia acumulada y “relaja” sus vecinos. Encuentra el camino más corto si todos los pesos son no negativos. Lo publicó Edsger Dijkstra en 1959.

Ejemplo resuelto

En el grafo inicial, desde A hasta G: Dijkstra fija A (0), luego C (2) y B (4). Desde C llega a D con 2 + 3 = 5, mejor que 4 + 10 por B; desde B llega a H con 4 + 3 = 7. Al fijar D, E queda en 5 + 4 = 9; al fijar E, F queda en 11 y G en 14. Pasar por F también da 11 + 3 = 14, un empate, así que se conserva el primer camino encontrado: A → C → D → E → G con costo 14. Ejecútalo paso a paso y compara la tabla de distancias con este razonamiento.

Errores comunes

• Usar Dijkstra con pesos negativos: en ese caso se necesita Bellman-Ford.
• Confundir BFS y DFS: la estructura auxiliar (cola o pila) es lo que cambia el orden de visita.
• No marcar los nodos visitados: el recorrido puede entrar en un ciclo infinito.