Visualizador DFS Online

Pseudocódigo

DFS se suele escribir de forma recursiva, pero la versión iterativa hace explícita la pila y evita desbordar la pila de llamadas en grafos profundos. Ambas producen el mismo orden de descubrimiento.

DFS(grafo, origen):
    tiempo = 0
    visitar(origen)

visitar(u):
    visitados.añadir(u)
    desc[u] = ++tiempo          // tiempo de descubrimiento
    para cada vecino v de u:
        si v no está en visitados:
            padre[v] = u
            visitar(v)
    fin[u] = ++tiempo           // tiempo de finalización

Los tiempos de descubrimiento y finalización son el verdadero producto de DFS. El intervalo [desc[u], fin[u]] de un descendiente queda estrictamente anidado dentro del de su antecesor, y esa propiedad de anidamiento es la base del orden topológico, la detección de ciclos, las componentes fuertemente conexas de Tarjan, los puntos de articulación y los puentes.

Ejemplo resuelto, paso a paso

Ejecuta DFS desde A sobre el grafo que carga el visualizador por defecto, tomando siempre los vecinos en orden alfabético.

Grafo de ejemplo: Aristas no dirigidas A-B (2), A-C (3), B-C (1) y C-D (4). DFS ignora los pesos.

1. Visitar A. desc[A] = 1. El primer vecino no visitado es B, así que recurre de inmediato en lugar de mirar también C.
2. Visitar B. desc[B] = 2. Sus vecinos son A, que es el padre y se omite, y C, no visitado. Recurre en C.
3. Visitar C. desc[C] = 3. Sus vecinos son A, B y D. A está visitado y no es el padre, así que A-C es una arista de retroceso y demuestra que existe un ciclo. B es el padre. D no está visitado, así que recurre en D.
4. Visitar D. desc[D] = 4. Su único vecino es C, el padre. No queda nada que hacer, así que fin[D] = 5.
5. Deshacer la recursión. El control vuelve a C, que se queda sin vecinos, así que fin[C] = 6. Después B termina en 7, y A, cuyo vecino restante C ya está visitado, termina en 8.

El orden de recorrido es A, B, C, D. BFS visita estos cuatro nodos en el mismo orden, pero los árboles son distintos: BFS construye un árbol plano con A a B, A a C y C a D, mientras que DFS construye la cadena única A a B a C a D. La arista de retroceso C a A identifica el ciclo A-B-C-A, y los intervalos anidados A[1,8], B[2,7], C[3,6], D[4,5] muestran directamente la profundidad de la recursión.

Complejidad y de dónde sale

Tiempo: O(V + E) · Espacio: O(V)

Cada vértice se visita exactamente una vez porque la comprobación de visitados protege la llamada recursiva, y cada arista se examina una vez desde cada extremo, lo que da 2E inspecciones en un grafo no dirigido y E en uno dirigido. El espacio es el conjunto de visitados más la pila de recursión, ambos O(V). La profundidad de la recursión es la longitud del camino simple más largo, así que en un grafo camino de un millón de nodos una implementación recursiva desbordará la pila de llamadas en la mayoría de lenguajes y hace falta la versión con pila explícita.

Cuándo usar Búsqueda en Profundidad y cuándo no

Elige DFS cuando la pregunta va sobre estructura. Elige BFS cuando va sobre distancia.

Errores frecuentes

• Desbordamiento de pila en grafos profundos. El DFS recursivo hace una llamada por vértice en un camino. Alrededor de 10.000 a 100.000 nodos, según el lenguaje, la pila de llamadas se agota. Conviértelo a pila explícita, o eleva el límite de recursión de forma deliberada si el lenguaje lo permite.
• Tratar la arista al padre como arista de retroceso. En un grafo no dirigido cada arista aparece desde ambos extremos, así que la arista de vuelta al padre siempre parece de retroceso. Omite el padre de forma explícita, y recuerda que con aristas paralelas debes omitirlo solo una vez.
• Usar el conjunto de visitados para detectar ciclos dirigidos. En un grafo dirigido, encontrar un nodo visitado no implica que haya un ciclo. Puede ser una arista cruzada hacia un subárbol ya terminado. Necesitas tres colores: no visitado, en la pila de recursión actual y terminado. Solo una arista hacia la pila de recursión cierra un ciclo.
• Suponer que el orden de recorrido es único. La salida de DFS depende del orden de iteración de los vecinos. Dos implementaciones correctas pueden producir órdenes válidos distintos, y por eso las pruebas deberían comprobar propiedades y no una secuencia exacta.

Preguntas frecuentes

¿Para qué sirve la búsqueda en profundidad?

DFS es la base del orden topológico, la detección de ciclos, las componentes fuertemente conexas, los puntos de articulación y los puentes, además de la generación de laberintos. En producción sostiene la resolución de dependencias en herramientas de compilación y gestores de paquetes, la detección de interbloqueos y los solucionadores por retroceso.

¿Cuál es la complejidad temporal de DFS?

O(V + E) en tiempo y O(V) en espacio con lista de adyacencia. Cada vértice se visita una vez y cada arista se inspecciona una vez desde cada extremo. El espacio es el conjunto de visitados más la pila de recursión, cuya profundidad es el camino simple más largo del grafo.

¿DFS es recursivo o iterativo?

Puede ser cualquiera de los dos. La forma recursiva es más corta y hace que los tiempos de descubrimiento y finalización aparezcan de forma natural. La iterativa usa una pila explícita y es la que necesitas en grafos lo bastante profundos como para desbordar la pila de llamadas, del orden de decenas de miles de nodos encadenados.

¿Cómo detecta DFS un ciclo?

En un grafo no dirigido, una arista hacia un nodo visitado que no es el padre del nodo actual cierra un ciclo. En un grafo dirigido hay que registrar qué nodos están en la pila de recursión actual, porque solo una arista de vuelta a la pila es una verdadera arista de retroceso. Una arista hacia un nodo terminado es cruzada o de avance y no demuestra nada.

¿Por qué DFS usa menos memoria que BFS?

DFS solo guarda el camino actual desde la raíz hasta el nodo, así que su memoria es proporcional a la profundidad. BFS guarda una frontera entera, que en un grafo ancho puede ser una fracción grande de todos los vértices. En un grafo profundo y estrecho la comparación se invierte y BFS es la opción más ligera.