Tema
Recorridos en anchura y en profundidad
- Algoritmos
- Nivel base
El recorrido en anchura visita los vértices por capas con ayuda de una cola, y el recorrido en profundidad se adentra por una rama con ayuda de una pila antes de retroceder.
Nombre en inglés
Breadth first and depth first search
Intuición
El recorrido en anchura es una mancha de tinta que crece de manera uniforme desde el origen, motivo por el cual encuentra el camino con menos aristas. El recorrido en profundidad es un explorador que sigue un pasillo hasta el fondo y solo entonces vuelve, y los tiempos de entrada y de salida que va registrando sirven para ordenar topológicamente y para detectar ciclos.
Fórmula
coste O(V + E) con listas de adyacencia ; anchura con cola ; profundidad con pila o recursion ; un grafo dirigido aciclico admite orden topologico
Ejemplo resuelto
En un grafo con aristas de A a B, de A a C, de B a D y de C a D, el recorrido en anchura desde A visita A, después B y C, y por último D, de modo que la distancia de A a D vale 2 aristas. El recorrido en profundidad desde A puede visitar A, B, D y después C, orden que no dice nada sobre distancias.
Errores frecuentes
- Usar el recorrido en anchura para hallar el camino más corto con pesos: Solo vale cuando todas las aristas pesan lo mismo, y con pesos hace falta el algoritmo de Dijkstra.
- Marcar los vértices como visitados al sacarlos de la cola y no al meterlos: Un mismo vértice entra varias veces y el coste se dispara.
- Confiar en la recursión con grafos grandes: Un recorrido en profundidad recursivo sobre un millón de vértices desborda la pila, situación en la que conviene la versión con pila explícita.
Ejercicio
Un grafo no dirigido con 7 vértices forma un camino simple de un extremo a otro. ¿Cuántas aristas recorre el recorrido en anchura desde un extremo hasta alcanzar el opuesto?
Ver la solución
Un camino simple con 7 vértices tiene 6 aristas, y el recorrido debe atravesarlas todas para llegar al extremo opuesto.
Respuesta: 6