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

Estructuras de Datos
- Lineales
  - Arrays
  - Listas enlazadas
  - Pilas y Colas
- No lineales
  - Arboles BST
  - Heaps
  - Grafos
- Hash
  - Funcion hash
  - Colisiones
  - Rehashing
- Algoritmos
  - Ordenamiento
  - Busqueda binaria
  - BFS DFS
- Optimizacion
  - Big-O
  - Dinamica
  - Voracidad

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²

f(x) = x · f(x) = x^2

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:

Arrastra cada ficha a su categoría (o tócala y luego toca la categoría). También puedes usar el teclado.

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

Video complementario

Recurso audiovisual para reforzar los conceptos.

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.

Tu texto se guarda sólo en este dispositivo.

VisuAlgoVisualizaciones animadas de estructuras de datos y algoritmos.

Recorridos en grafos (BFS y DFS)

Herramientas de la lección

Sobre este contenido

Ir a