Recorridos en grafos (BFS y DFS)

Diagrama de estructuras de datos: arbol binario, lista enlazada y tabla hash. — Estructuras de datos fundamentales y analisis de complejidad algoritmica.

Mapa conceptual

Ondas contra explorador testarudo Un grafo es una red de nodos unidos por aristas. Para explorarlo hay dos estrategias opuestas: BFS se expande como ondas en el agua (por capas); DFS se interna como un explorador que retrocede solo cuando choca con un muro.

Representar un grafo

Lista de adyacencia: cada nodo guarda sus vecinos. Compacto para grafos dispersos; iterar vecinos es proporcional a sus grados.
Matriz de adyacencia: n×n con 1 si hay arista. Consulta de arista O(1), pero O(n²) de memoria: adecuado para grafos densos.

BFS: búsqueda en anchura

BFS usa una COLA. Visita el origen, encola sus vecinos no vistos, y va tomando el siguiente de la cola. Así explora por niveles: primero todos los nodos a distancia 1, luego a 2, etc. Si las aristas no tienen peso, la primera vez que BFS alcanza un nodo lo hace por el camino más corto: su distancia es la verdadera.

DFS: búsqueda en profundidad

DFS usa una PILA (o recursión). Toma un vecino y se hunde lo más lejos posible antes de retroceder. Marca visitados para no repetir. Su estructura de árbol de descubrimiento revela ciclos, componentes conexos y permite el orden topológico de grafos dirigidos acíclicos.

La diferencia entera está en la estructura que guarda la frontera: cola o pila.
Recorrido	Estructura	Orden	Da el camino más corto	Uso típico
BFS	cola	por capas	Si (sin pesos)	distancias, niveles, componentes
DFS	pila / recursion	a fondo	No	ciclos, orden topologico, laberintos

En un grafo NO ponderado, ¿qué recorrido garantiza el camino más corto entre dos nodos?

Costo de ambos

Con lista de adyacencia, BFS y DFS visitan cada nodo una vez y recorren cada arista una vez: O(V + E) tiempo y O(V) memoria para las marcas. Son óptimos: hay que ver al menos todos los nodos y aristas.

Marcas y visitados

Sin marcar, se repiten ciclos indefinidamente. Un arreglo visitado (o cambiar el color en DFS a gris/negro) evita reprocesar. En DFS, detectar una arista hacia un nodo gris (en la pila actual) señala un ciclo.

[Escalado: V+E contra matriz n²]

Esta actividad interactiva ('Grafico interactivo') requiere el motor completo de Lumbre. El contenido estatico se muestra arriba; para la experiencia interactiva, visita la version online de este objeto.

DFS es la elección natural para calcular el número mínimo de aristas entre dos nodos en un laberinto sin pesos.

Errores frecuentes

No marcar visitados y quedar atrapado en un ciclo.
Usar DFS para caminos mínimos sin pesos: es correcto hallar UNO, no el más corto.
Suponer que el orden de recorrido es único: depende del orden en que se guardan los vecinos.

Aplicaciones

BFS: niveles en redes sociales, «grados de separación», rutas sin pesos, componentes conexos. DFS: detección de ciclos, orden topológico para dependencias, backtracking en laberintos y sudoku, componentes fuertemente conexos.

Asigna cada necesidad al recorrido indicado:

BFS

DFS

VisualGo
Animación interactiva de BFS y DFS sobre un mismo grafo.

Dado un grafo de dependencias de un proyecto, explica por qué el orden de compilación se obtiene con DFS (orden topológico) y qué haría BFS distinto. Ilustra con un ciclo y su consecuencia.

VisuAlgo
Visualizaciones animadas de estructuras de datos y algoritmos.