Visualizador BFS vs DFS

Observa cómo BFS y DFS exploran el mismo grafo de forma diferente. BFS avanza en anchura, DFS avanza en profundidad.

Valores iniciales — Visualizador BFS vs DFS

Grafo predefinido	Cuadrícula 4x4
Nodo inicial	0

Cambia cualquier control de arriba y los resultados se recalculan.

Cargando simulación interactiva...

BFS encuentra el camino más corto solo si todas las aristas cuestan lo mismo 🖖

La razón habitual para usar BFS es que devuelve la ruta más corta. Esa garantía es más estrecha de lo que parece: se cumple porque BFS trata cada arista como un paso, así que la primera vez que alcanza un nodo tiene que haber llegado con el mínimo número de saltos. Añade costes reales — distancias de carretera, tasas de transbordo, latencia — y la garantía se desvanece. BFS seguirá respondiendo con seguridad, y se equivocará, porque un camino de dos aristas caras puede costar fácilmente más que uno de cinco aristas baratas. El algoritmo de Dijkstra es el arreglo, y es casi exactamente esto: BFS con la cola simple sustituida por una cola de prioridad.

El mismo mapa, dos formas de viajar 🖖

Al ejecutarlas en paralelo se nota algo: visitan exactamente los mismos nodos y aristas, solo que en distinto orden. La búsqueda en anchura (BFS) explora todo el vecindario actual antes de avanzar, por lo que debe recordar cada nodo que espera en la frontera. La búsqueda en profundidad (DFS) se compromete con una rama y solo sigue el camino actual. La conclusión práctica: usa BFS cuando la respuesta esté probablemente cerca y DFS cuando el grafo sea profundo y quieras gastar poca memoria.

Ambos algoritmos nacieron en laberintos 🖖

Mucho antes de los ordenadores, la DFS ya existía como una regla para recorrer laberintos, publicada por el matemático francés Charles Pierre Trémaux en el siglo XIX. La BFS llegó mucho después: Edward F. Moore la reinventó en un artículo de 1959 titulado literalmente The Shortest Path Through a Maze, y Konrad Zuse ya la había esbozado en 1945. Dos pilares de la informática, ambos ideados originalmente solo para salir de un laberinto.

RECORRIDO DE GRAFOS — ¿QUÉ ORDEN NECESITA Y CUÁNTO CUESTA?

¿En qué caso de recorrido está?

BFS y DFS visitan los mismos nodos y se diferencian en una línea de código: una cola en lugar de una pila. Todo lo demás se sigue de ahí. La cola se extiende en anillos, así que cuando BFS llega por primera vez a un nodo lo ha hecho por un camino con el menor número de aristas. La pila se hunde, así que DFS alcanza antes el extremo lejano, pero por ninguna ruta en particular. Cuál conviene depende de la pregunta y de la forma del grafo, que decide lo que cuesta cada uno.

Necesita el menor número de aristas: BFS, porque visita por capas de distancia FIFO ⇒ min |E|

Un árbol: orden por niveles frente a preorden, y el coste en memoria se invierte BFS: O(w), DFS: O(d)

Una cadena: los dos órdenes coinciden y la elección deja de importar deg ≤ 2 ⇒ BFS = DFS

No todo es alcanzable: un solo nodo de partida no basta c(G) > 1

Necesita el menor número de aristas: BFS, porque visita por capas de distancia

Lo que sabe: Un grafo sin pesos y una pregunta de camino más corto. BFS visita todo lo que está a distancia 1, luego todo lo que está a distancia 2, de modo que la primera llegada a un nodo va por un camino mínimo.

Regla: FIFO ⇒ min |E|

Ejemplo resuelto: En la rejilla 4×4 desde el nodo 0, BFS visita 0, 1, 4, 2, 5, 8, 3, 6, 9, 12, …: un frente de onda diagonal. DFS visita 0, 1, 2, 3, 7, 6, 5, 4, … y llega al nodo 4 solo en su octavo paso.

Abrir este caso: Cuadrícula 4x4

Necesita el menor número de aristas: BFS, porque visita por capas de distancia. BFS barre hacia fuera por capas de distancia; DFS serpentea por un pasillo antes de volver. Un grafo sin pesos y una pregunta de camino más corto. BFS visita todo lo que está a distancia 1, luego todo lo que está a distancia 2, de modo que la primera llegada a un nodo va por un camino mínimo. — BFS barre hacia fuera por capas de distancia; DFS serpentea por un pasillo antes de volver.

Un árbol: orden por niveles frente a preorden, y el coste en memoria se invierte

Lo que sabe: En un árbol los dos órdenes tienen nombre: BFS es el orden por niveles, DFS es el preorden. Ambos visitan los 15 nodos; lo que cambia es cuánto hay que guardar a la vez.

Regla: BFS: O(w), DFS: O(d)

Ejemplo resuelto: BFS da 0, 1, 2, 3, …, 14: nivel por nivel. DFS da 0, 1, 3, 7, 8, 4, 9, 10, 2, …: primero por la espina izquierda. Cola máxima 8, pila máxima 4.

Abrir este caso: Árbol binario

Un árbol: orden por niveles frente a preorden, y el coste en memoria se invierte. El orden por niveles llena cada fila antes de bajar; el preorden corre hasta una hoja y retrocede. En un árbol los dos órdenes tienen nombre: BFS es el orden por niveles, DFS es el preorden. Ambos visitan los 15 nodos; lo que cambia es cuánto hay que guardar a la vez. — El orden por niveles llena cada fila antes de bajar; el preorden corre hasta una hoja y retrocede.

Una cadena: los dos órdenes coinciden y la elección deja de importar

Lo que sabe: Cada nodo tiene exactamente un vecino sin visitar, así que solo hay un camino hacia delante. BFS y DFS producen la misma secuencia y guardan un nodo cada vez.

Regla: deg ≤ 2 ⇒ BFS = DFS

Ejemplo resuelto: En la cadena de 12 nodos ambos visitan 0, 1, 2, …, 11 en ese orden, y ambos frentes se mantienen en tamaño 1 de principio a fin.

Abrir este caso: Cadena larga

Una cadena: los dos órdenes coinciden y la elección deja de importar. Sin nada donde ramificarse, ambos recorridos siguen la misma línea en el mismo orden. Cada nodo tiene exactamente un vecino sin visitar, así que solo hay un camino hacia delante. BFS y DFS producen la misma secuencia y guardan un nodo cada vez. — Sin nada donde ramificarse, ambos recorridos siguen la misma línea en el mismo orden.

No todo es alcanzable: un solo nodo de partida no basta

Lo que sabe: El grafo viene en trozos. Desde un nodo, cualquiera de los dos recorridos visita solo la componente a la que ese nodo pertenece y después se detiene.

Regla: c(G) > 1

Ejemplo resuelto: Desde el nodo 0 del grafo de 10 nodos, tanto BFS como DFS visitan exactamente 4 nodos y paran. Los nodos 4, 5, 6, 7, 8 y 9 no se tocan nunca.

Abrir este caso: Desconectado

No todo es alcanzable: un solo nodo de partida no basta. Cuatro nodos alcanzables y seis no: una partida explora una componente y nada más. El grafo viene en trozos. Desde un nodo, cualquiera de los dos recorridos visita solo la componente a la que ese nodo pertenece y después se detiene. — Cuatro nodos alcanzables y seis no: una partida explora una componente y nada más.

Referencias (2)

Insight block 3 — BFS as a maze algorithm: E. F. Moore, "The shortest path through a maze." Proceedings of an International Symposium on the Theory of Switching, Part II, 285–292. Harvard University Press, 1959.
Trémaux's rule, as it was actually published: É. Lucas, Récréations mathématiques, vol. 1. Gauthier-Villars, Paris, 1882 — Lucas credits the maze-walking procedure to Charles Pierre Trémaux.

Problema resuelto al detalle

Un recorrido de un laberinto con 16 nodos y 16 aristas 5 pasos
El laberinto consta de 16 nodos unidos por 16 aristas. Calcule cuántos nodos alcanza un recorrido que comienza en el nodo 0 y a qué distancia se encuentra el nodo 15 del nodo 0. Se trata del estado Pasillo del laberinto con nodo inicial 0.
1. Escriba el laberinto como una lista de adyacencia antes de hacer cualquier otra cosa. El nodo 4 es el que conviene destacar: no lo toca ni una sola arista, por lo que su grado es 0 y ningún recorrido que comience en otro lugar llegará jamás a él.
  
  $0 : 11 : 0, 2, 52 : 1, 33 : 24 : \emptyset 5 : 1, 6, 96 : 5, 7, 107 : 6, 118 : 9, 12 9 : 5, 8, 1010 : 6, 9, 1411 : 7, 15 12 : 8, 1313 : 12, 1414 : 10, 1315 : 11$
2. La búsqueda en anchura clasifica en capas todo lo que puede alcanzar, siendo la capa k todo lo que se encuentra por primera vez desde la capa k − 1. Construir estas capas es una clausura más que un recorrido: se completa una capa entera antes de abrir la siguiente y ningún nodo aparece dos veces.
  
  $L_{0} L_{3} L_{6} = {0} = {3, 6, 9} = {13, 15} L_{1} L_{4} = {1} = {7, 8, 10} L_{2} L_{5} = {2, 5} = {11, 12, 14}$
3. Sume los tamaños de las capas. El recorrido alcanza 15 nodos, uno menos de los 16 que contiene el grafo, motivo por el cual el contador de pasos se detiene una unidad por debajo del número de nodos.
  
  $1 + 1 + 2 + 3 + 3 + 3 + 2 = 15, n = 16, de g (4) = 0$
4. El nodo 15 aparece por primera vez en la capa 6, y el número de capa representa una distancia: un nodo solo se añade a la cola desde un nodo situado una capa por encima de él, de modo que a nada de la capa 6 se puede llegar en menos de 6 aristas. La ruta 0-1-5-6-7-11-15 consigue 6, por lo que la cota es exacta.
  
  $15 \in L_{6} ⟹ d (0, 15) = 6 : 0 \to 1 \to 5 \to 6 \to 7 \to 11 \to 15$
5. La búsqueda en profundidad no mantiene un invariante semejante. Supón que, en el nodo 1, el recorrido elige el 5 antes que el 2; después, en el nodo 5, el 9 antes que el 6; y, en el nodo 9, el 8 antes que el 10. Todas son elecciones válidas entre vecinos aún no visitados, pero lo adentran en el largo corredor y solo retrocede cuando ya no puede avanzar por el grafo. Alcanza el nodo 15 al final de un camino de 12 aristas, una respuesta perfectamente válida a la pregunta de si ese nodo es alcanzable.
  
  $0 \to 1 \to 5 \to 9 \to 8 \to 12 \to 13 \to 14 \to 10 \to 6 \to 7 \to 11 \to 15 ⟹ ℓ = 12$
Respuesta

El nodo 15 se encuentra a 6 aristas del inicio, y un recorrido en profundidad puede ofrecer una ruta de 12 hasta el mismo lugar. El factor de 2 no es lo más interesante; lo es el origen de un posible atajo. La componente alcanzable contiene 15 nodos, por lo que cualquier árbol generador de la misma utiliza 14 aristas, y el laberinto tiene 16, lo que significa que hay exactamente 2 aristas sobrantes. Elimine esas 2 y lo que queda es un árbol, donde existe exactamente un camino entre cualquier par de nodos; por tanto, ambos paneles coincidirían en cada distancia y diferirían únicamente en el orden de recorrido. Toda discrepancia sobre la distancia entre ellos se debe a esas 2 aristas adicionales. Esta es también la razón por la que la búsqueda en profundidad resulta más eficiente cuando la pregunta es simplemente si un nodo es alcanzable, y la opción incorrecta en cuanto la pregunta pasa a ser a qué distancia se encuentra.

$∣ E ∣ - (∣ V ∣ - 1) = 16 - (15 - 1) = 2$

Por el equipo de 42Math · Actualizado 2026-07-27

Contrastado con fuentes publicadas. Se agradecen correcciones. Política editorial · Correcciones

Todas las lecciones de Informática →

Problemas de ejemplo

Cuadrícula 4x4 - Cuadrícula 4×4: BFS explora capa por capa
Pasillo de laberinto - Corredor de laberinto
Grafo en estrella - Nueve radios, cada nodo a un salto del centro. Al no tener hacia dónde descender, la búsqueda en profundidad te devolverá el mismo orden que BFS.
Cadena larga - Doce nodos en línea: los órdenes vuelven a coincidir. Sin embargo, aquí cada algoritmo retiene un solo nodo a la vez frente a los nueve de la estrella.
Árbol binario - Árbol binario: DFS profundiza antes de expandirse en anchura
Desconectado - Dos cuadrados y dos nodos aislados. Si comienzas el recorrido en el nodo 0, llegarás a 4 de los 10. Por mucho que busques, jamás encontrarás el resto.
Grafo denso - Grafo denso: muchas aristas, órdenes similares