¿Qué son los algoritmos BFS y DFS y cuándo deberías elegir cada uno?

BFS y DFS son algoritmos de recorrido de grafos que encuentran sistemáticamente los vértices alcanzables desde un vértice inicial. BFS se expande nivel a nivel desde los vértices cercanos, lo que lo hace adecuado cuando necesitas un camino con el número mínimo de aristas en un grafo no ponderado. DFS sigue una rama hasta donde sea posible antes de retroceder, por lo que se utiliza como base para problemas como el análisis estructural, la detección de ciclos y la ordenación topológica. Ninguno es siempre mejor; la elección depende del criterio del camino y del propósito del grafo. ocw.mit.edu↗algs4.cs.princeton.edu↗

¿Qué encuentran BFS y DFS en el recorrido de grafos?

Un grafo es una estructura relacional formada por vértices y aristas. Los vértices representan entidades como personas, ciudades, páginas web o tareas, mientras que las aristas representan conexiones entre ellas, como amistades, carreteras, enlaces o relaciones de prerrequisito. El conjunto de vértices se denota por $V$, y el conjunto de aristas por $E$.

Si las aristas no tienen dirección, el grafo es no dirigido. Por ejemplo, una amistad mutua normalmente puede considerarse bidireccional. En cambio, relaciones como que A siga a B o que la tarea A deba terminar antes que la tarea B forman un grafo dirigido. En un grafo dirigido, solo puedes desplazarte en la dirección de una flecha; no puedes moverte automáticamente en la dirección opuesta. ocw.mit.edu↗

La pregunta más básica del recorrido de grafos es: «¿Qué vértices pueden alcanzarse desde un punto inicial $s$?». Al responder esta pregunta, BFS y DFS también pueden registrar información adicional, como si un vértice ha sido visitado, el camino por el que se llegó por primera vez a cada vértice y el orden de recorrido. Sin embargo, un recorrido que comienza en un vértice procesa únicamente la parte que realmente es alcanzable desde ese vértice. No visita necesariamente todos los vértices del grafo. ocw.mit.edu↗

Un árbol también es un tipo de grafo. Por ello, BFS y DFS se pueden usar en problemas que parecen árboles, como jerarquías de carpetas u organigramas. Sin embargo, es importante recordar que un grafo general puede contener ciclos que regresan a un vértice y múltiples caminos hacia el mismo vértice. Aplicar directamente a un grafo general una implementación diseñada solo para recorrer árboles puede causar visitas duplicadas.

¿Cómo explora BFS primero los vértices cercanos?

BFS significa Breadth-First Search, o búsqueda en anchura. Primero encuentra los vértices alcanzables desde el punto inicial mediante una arista, luego los que requieren dos aristas y después tres, expandiendo el rango de búsqueda en ese orden. Aquí, la distancia no es distancia física ni coste; es el número de aristas que se deben recorrer desde el punto inicial. algs4.cs.princeton.edu↗

BFS suele utilizar una cola para ello. Una cola es una estructura de datos FIFO (First In, First Out), lo que significa que el primer elemento añadido es el primero que se extrae. Introduce el vértice inicial en la cola y márcalo como visitado; después, extrae un vértice de la parte frontal de la cola. Marca como visitados todos los vecinos no descubiertos de ese vértice y añádelos al final de la cola. Repite el proceso hasta que la cola esté vacía. Como los vértices cercanos descubiertos antes se procesan primero, se conserva la expansión nivel a nivel. gh.cp-algorithms.com↗algs4.cs.princeton.edu↗

Por ejemplo, supongamos que, partiendo de A, descubres los vecinos B y C de A. Cuando BFS procesa B, descubre los vecinos de B; después procesa C y descubre los vecinos de C. Aunque un vértice descubierto desde B esté a mayor profundidad, C, que ya fue colocado en la cola en el mismo nivel, se procesa primero o muy poco después. El orden exacto entre B y C puede variar según el orden en que se almacenen los vértices adyacentes.

La clave de BFS es marcar un vértice como visitado en cuanto se descubre. Si retrasas la marca hasta que se extraiga de la cola, dos vértices pueden descubrir cada uno al mismo vecino e insertarlo en la cola más de una vez. En un BFS típico, marcar un nuevo vecino como descubierto justo en el momento en que se añade a la cola es más sencillo y seguro.

¿En qué condiciones BFS proporciona un camino más corto?

BFS se elige a menudo porque, en un grafo no ponderado, encuentra un camino con el número mínimo de aristas desde el vértice inicial hasta cada vértice alcanzable. Examina todos los vértices a un paso del inicio antes de examinar los vértices a dos pasos, por lo que un camino con menos aristas que el que descubre por primera vez un vértice no puede aparecer más tarde. Si registras el vértice precedente como padre cuando cada vértice se descubre por primera vez durante BFS, esos punteros a padres forman un árbol de caminos más cortos. algs4.cs.princeton.edu↗

Para reconstruir un camino, sigue los punteros a padres hacia atrás desde el vértice objetivo hasta el vértice inicial y, después, invierte el orden. Por ejemplo, si parent[D] = B y parent[B] = A, el camino descubierto de A a D es A → B → D. Usa un marcador independiente para indicar que el vértice inicial no tiene padre.

Sin embargo, interpretar «más corto» de forma demasiado amplia conduce a errores. BFS garantiza el número mínimo de aristas solo cuando todas las aristas pueden tratarse como si tuvieran el mismo coste. Si las carreteras tienen tiempos de viaje distintos o los vuelos tienen tarifas distintas, un camino que usa dos aristas puede ser más barato o más rápido que uno que usa una sola arista. En ese caso, BFS estándar no es un algoritmo de caminos más cortos por coste. Según las propiedades de los pesos, considera métodos ponderados específicos como el algoritmo de Dijkstra o el algoritmo de Bellman-Ford. algs4.cs.princeton.edu↗

Por tanto, BFS encaja bien en problemas como «¿Cuántos grados de conexión separan a dos amigos?» o «¿Cuántos movimientos se necesitan para llegar a un punto de una cuadrícula cuando mover una celda arriba, abajo, izquierda o derecha cuenta como un movimiento?». En cambio, si el objetivo es el menor tiempo o coste, primero verifica que los pesos de las aristas sean realmente iguales.

¿Por qué DFS profundiza antes de retroceder?

DFS significa Depth-First Search, o búsqueda en profundidad. Desde el vértice actual, elige un vecino no visitado y sigue avanzando hasta haber explorado una rama tan profundamente como sea posible. Cuando llega a un callejón sin salida, vuelve al vértice anterior y busca otro vecino que todavía no se haya explorado. Este proceso de regreso también se denomina retroceso o backtracking. ocw.mit.edu↗

DFS es fácil de implementar con llamadas recursivas. Al entrar en un vértice, primero márcalo como visitado y luego llama a la misma función de recorrido para cada vecino no visitado de ese vértice. Cuando una llamada recursiva termina, el control regresa naturalmente al punto que la llamó, expresando el flujo de profundizar y luego retroceder.

La recursión no es la única opción. DFS también puede implementarse de forma iterativa con una pila explícita. Una pila es una estructura de datos LIFO (Last In, First Out), lo que significa que el último elemento añadido es el primero que se extrae. Al extraer primero el vértice descubierto más recientemente, puedes producir un comportamiento en profundidad. En una implementación recursiva, la pila de llamadas del programa desempeña este papel de forma implícita. ocw.mit.edu↗gh.cp-algorithms.com↗

Los punteros a padres creados por DFS también pueden mostrar un camino desde el vértice inicial hasta un vértice. Sin embargo, no se garantiza que ese camino tenga el número mínimo de aristas. Como DFS sigue su primera rama elegida tan profundamente como sea posible, podría descubrir un camino más corto en otra rama solo más tarde. ocw.mit.edu↗

¿Qué tipos de análisis estructural usan DFS?

DFS muestra su valor cuando se analiza la estructura de un grafo en lugar de limitarse a comprobar la alcanzabilidad. Encontrar componentes conexas es un ejemplo representativo. En un grafo no dirigido, ejecutar DFS una vez desde cualquier vértice no visitado encuentra como un grupo todos los vértices conectados a él. Iniciar DFS de nuevo desde un vértice no visitado restante encuentra otro grupo.

La detección de ciclos es otra aplicación común de DFS. Un ciclo es una estructura en la que seguir aristas puede llevarte de vuelta al punto de inicio o a un vértice que ya está en el camino actual. En un grafo dirigido, puedes detectar un ciclo distinguiendo si encuentras un vértice que ya está en el camino recursivo actual. Por eso debes distinguir entre un vértice que simplemente se ha visitado una vez y uno que se encuentra actualmente en el camino de recorrido.

La ordenación topológica organiza dependencias dirigidas, como las relaciones de prerrequisito entre tareas, en un orden. Solo es posible en un grafo dirigido acíclico, o DAG. Un DAG es un grafo dirigido sin ningún ciclo que regrese a su punto de partida al seguir las direcciones de las aristas. Si existe un ciclo, surge una contradicción —por ejemplo, B debe terminar antes que A y A debe terminar antes que B—, por lo que ningún orden lineal puede satisfacer todas las aristas. Un método que usa el orden de finalización de DFS es una de las bases de la ordenación topológica. algs4.cs.princeton.edu↗

Encontrar componentes fuertemente conexas también es un tema importante basado en DFS. Una componente fuertemente conexa es un conjunto de vértices de un grafo dirigido en el que cualesquiera dos vértices del mismo grupo pueden alcanzarse mutuamente. Sin embargo, este problema no se resuelve con un único DFS sencillo; requiere una construcción algorítmica que utiliza el orden de recorrido y las direcciones de las aristas. algs4.cs.princeton.edu↗

¿Qué problemas ocurren sin marcadores de visitado?

En un grafo general, un array o conjunto de visitados no es opcional; es esencial para la terminación y la corrección. Por ejemplo, si A y B están conectados, puedes ir de A a B y luego volver de B a A. Sin comprobar el estado de visitado, DFS puede alternar recursivamente entre A y B para siempre, y BFS puede colocar el mismo vértice en la cola varias veces. ocw.mit.edu↗

El término visitado puede dividirse de forma ligeramente distinta según la implementación. En BFS, un vértice normalmente se marca como «descubierto» en el momento en que se añade a la cola. En DFS, es habitual marcar un vértice como visitado inmediatamente al entrar en su función. Los análisis más avanzados de grafos dirigidos pueden distinguir entre un estado no visitado, un estado que se está explorando y un estado completado.

El principio de visitar cada vértice una sola vez está directamente relacionado con la eficiencia del recorrido. Si no expandes vértices que ya se han procesado, entonces, con listas de adyacencia, inspeccionas cada vértice y arista solo un número limitado de veces. Además, si asignas un puntero a padre solo cuando un vértice se descubre por primera vez, queda claro qué camino descubrió primero ese vértice.

Para recorrer un grafo completo, necesitas un bucle externo. Examina cada vértice por turnos y, cuando encuentres uno que aún no se haya visitado, inicia un nuevo BFS o DFS desde él. En un grafo no dirigido, esto produce un recorrido por componente conexa. En un grafo dirigido, procesa sucesivamente los rangos alcanzables en las direcciones de arista elegidas. ocw.mit.edu↗

¿Por qué la complejidad temporal depende de la representación del grafo?

La complejidad temporal de BFS y DFS suele expresarse como $O(\lvert V \rvert + \lvert E \rvert)$. Este es el análisis estándar cuando se usan listas de adyacencia. Una lista de adyacencia almacena la lista de vecinos conectados directamente para cada vértice. Con marcadores de visitado, cada vértice se procesa una vez y las aristas se comprueban al recorrer las listas de vecinos, por lo que el trabajo total es proporcional al número de vértices más el número de aristas. ocw.mit.edu↗

El espacio adicional suele ser $O(\lvert V \rvert)$. Esto incluye el array de visitados, el array de padres y la cola de BFS o la pila de DFS. Para DFS recursivo, la pila de llamadas necesaria por la profundidad de recursión también se incluye en el espacio adicional. Es útil distinguir entre el espacio usado para almacenar el propio grafo y el espacio extra usado por el algoritmo de recorrido. ocw.mit.edu↗

Una matriz de adyacencia almacena la existencia de una arista para cada par de vértices en una tabla. Para encontrar los vecinos de un vértice, puede ser necesario inspeccionar todos los vértices posibles. Por ello, BFS o DFS que usan una matriz de adyacencia pueden requerir normalmente $O(\lvert V \rvert^2)$ de tiempo. Para grafos dispersos con pocas aristas, las listas de adyacencia son especialmente eficientes porque solo recorren los vecinos realmente conectados. ocw.mit.edu↗

La notación de complejidad describe cómo tiende a crecer el uso de recursos a medida que aumenta el tamaño de la entrada. El tiempo de ejecución real también se ve afectado por los identificadores de los vértices, la implementación de la lista de adyacencia, la disposición de la memoria y el tamaño de la parte alcanzable desde el punto inicial del recorrido. Aun así, al elegir un algoritmo, es sensato comprobar primero si el grafo es disperso y cómo está representado.

¿Está fijado el orden de visita real de BFS o DFS?

No. BFS sigue el principio de procesar primero los niveles más cercanos, y DFS sigue el principio de explorar profundamente la rama actual, pero qué vértice se visita primero dentro del mismo nivel o qué rama se explora primero entre varios vecinos depende del orden de almacenamiento de los vértices adyacentes. gh.cp-algorithms.com↗gh.cp-algorithms.com↗

Por ejemplo, si la lista de vecinos de A está ordenada como B, C, BFS normalmente descubre primero B. Si la lista se cambia a C, B, puede descubrirse primero C. Esta diferencia puede tener un efecto mayor en DFS. Si cambia el primer vecino elegido, cambia la propia rama explorada en profundidad, junto con el árbol de recorrido y los caminos de DFS creados mediante punteros a padres.

Este hecho importa al evaluar el resultado de un algoritmo. Si un problema requiere «el primer orden de visita lexicográfico», debes ordenar las listas de adyacencia o especificar una regla de prioridad. En cambio, si solo necesitas la alcanzabilidad, el número de componentes conexas o las distancias mínimas en número de aristas, el orden detallado dentro del mismo nivel o profundidad puede no ser central para el resultado.

En particular, al implementar DFS de forma iterativa con una pila, el orden en el que se insertan los vecinos puede ser el inverso del orden en que realmente se extraen. Si quieres el mismo orden de visita que una implementación recursiva que usa un orden determinado de lista de adyacencia, debes ajustar intencionadamente la dirección en que se insertan los vecinos en la pila. No es una definición distinta de DFS; es una diferencia de implementación causada por el comportamiento LIFO.

¿Cuáles son los malentendidos y errores más comunes?

El primero es la idea errónea de que BFS resuelve todo tipo de problemas de caminos más cortos. Como se explicó anteriormente, BFS garantiza el número mínimo de aristas en un grafo no ponderado. Si los pesos difieren, un movimiento no tiene necesariamente el mismo valor que otro, por lo que cambia el propio modelo del problema. algs4.cs.princeton.edu↗algs4.cs.princeton.edu↗

El segundo es la suposición de que DFS siempre usa menos memoria que BFS. Incluyendo los arrays de visitados y el estado del recorrido, ambos algoritmos pueden usar generalmente $O(\lvert V \rvert)$ de espacio adicional. El tamaño máximo de la cola o la pila puede diferir en determinadas formas de grafo e implementaciones, pero la complejidad asintótica por sí sola no establece una ventaja incondicional para ninguno de los dos. ocw.mit.edu↗

El tercero es creer que DFS recursivo es seguro para cualquier entrada. En un grafo con una profundidad muy larga, la profundidad de recursión también aumenta. Debes tener en cuenta el límite de la pila de llamadas del lenguaje y del entorno de ejecución; en esos casos, una implementación iterativa con una pila explícita puede ser más práctica. También es importante entender que la pila de llamadas recursivas forma parte del espacio adicional de DFS. ocw.mit.edu↗

El cuarto es tratar un grafo dirigido como si fuera no dirigido. La existencia de una arista de A a B no significa que puedas viajar de B a A. Al almacenar la entrada en listas de adyacencia, un grafo no dirigido normalmente añade una arista a las listas de ambos vértices, mientras que un grafo dirigido la añade solo a la lista del vértice de origen. Esta diferencia cambia el significado de la alcanzabilidad, la conectividad y los ciclos. ocw.mit.edu↗

El quinto es confundir un resultado de recorrido con un único camino correcto. Cuando varios caminos tienen el mismo número mínimo de aristas, BFS registra uno de ellos mediante punteros a padres. DFS también puede producir caminos diferentes según el orden de los vecinos. Si el propio camino necesita una prioridad, deben especificarse reglas de ordenación o condiciones adicionales en el problema.

¿Qué criterios debes usar al elegir para un problema?

Lo mejor es expresar primero el objetivo con palabras. Si la pregunta solo plantea «¿Se puede alcanzar desde el punto inicial?», tanto BFS como DFS son posibles, y puedes elegir según el entorno de implementación y el análisis que necesites después. Si necesitas el número mínimo de aristas, como en «¿Cuántos movimientos idénticos se requieren para llegar?», BFS es la elección natural. Si necesitas seguir un camino en profundidad mientras analizas la estructura, o si importa el punto en el que regresas, probablemente DFS sea apropiado.

Después, comprueba qué significan las aristas. Determina si todos los movimientos tienen el mismo coste o si intervienen pesos como tiempo, distancia o coste. Si existen pesos, no apliques directamente la propiedad de camino más corto de BFS. Comprueba también de antemano si el grafo es dirigido, si puede haber ciclos y si necesitas examinar el grafo completo. ocw.mit.edu↗algs4.cs.princeton.edu↗

Los criterios de selección se pueden resumir de la siguiente manera.

Por último, considera el tamaño y la representación de la entrada. Para un grafo disperso, las listas de adyacencia y el análisis estándar $O(\lvert V \rvert + \lvert E \rvert)$ para BFS y DFS son una buena opción. En entornos donde la profundidad de recursión pueda ser un problema, considera DFS iterativo. Si el orden de visita afecta a la evaluación o a las reglas de negocio, el orden de la lista de adyacencia también forma parte del diseño.

Conclusión: los objetivos y las condiciones del recorrido importan más que los nombres

BFS y DFS son estrategias diferentes para recorrer exhaustivamente un grafo. BFS usa una cola para expandirse desde los vértices cercanos y tiene la ventaja de proporcionar caminos con el número mínimo de aristas en grafos no ponderados. DFS usa recursión o una pila para explorar profundamente una rama y retroceder, y constituye la base de muchos métodos que trabajan con la estructura del grafo, incluidas las componentes conexas, los ciclos y la ordenación topológica en DAG. ocw.mit.edu↗algs4.cs.princeton.edu↗

Ambos requieren marcadores de visitado y, por lo general, tienen la misma complejidad temporal asintótica al usar listas de adyacencia. Por tanto, la clave para elegir entre ellos no es una única etiqueta como la velocidad, sino qué define un camino más corto, si las aristas están ponderadas, cómo deben interpretarse la dirección y los ciclos, y si debe procesarse todo el grafo. Distinguir primero estas condiciones te permite usar BFS y DFS con el propósito adecuado.