20. Recorrido en profundidad (DFS)

20.1 Introducción

Recorrer un grafo significa visitar sus vértices siguiendo un criterio sistemático. El recorrido en profundidad, conocido como DFS por Depth-First Search, avanza por una conexión, luego por otra y continúa hasta no encontrar vecinos nuevos.

Cuando alcanza un punto sin salida, retrocede hasta el vértice anterior y prueba otra rama.

20.2 Idea fundamental

DFS sigue tres acciones básicas:

1. Marcar el vértice actual como visitado.
2. Elegir un vecino todavía no visitado y profundizar desde él.
3. Si no quedan vecinos nuevos, retroceder.

20.3 La pila

DFS utiliza una estructura LIFO: el último vértice agregado es el primero en procesarse o retirarse.

En una implementación recursiva, la pila de llamadas del lenguaje conserva automáticamente el camino activo.

20.4 Orden de visita

El orden de DFS depende del vértice inicial y del orden en que se examinan los vecinos. Distintos órdenes pueden producir árboles DFS diferentes, aunque todos visitan la misma componente.

20.5 Simulación interactiva: DFS paso a paso

Selecciona un nodo como origen y pulsa Iniciar. Avanza paso a paso para observar la pila, el orden de visita, las aristas de descubrimiento y los retrocesos.

Verde indica el camino activo de la pila; celeste, vértices ya visitados; rosa, el vértice procesado en el paso actual.

20.6 Retroceso o backtracking

Cuando el vértice actual no tiene vecinos sin visitar, DFS lo retira de la pila y regresa al anterior.

Este mecanismo permite explorar todas las ramas sin perder el camino utilizado para llegar a ellas.

20.7 Árbol DFS

Cada vez que DFS descubre un vértice nuevo, la arista utilizada se incorpora al árbol DFS. Si la componente tiene n vértices, el árbol contiene n − 1 aristas.

20.8 Grafos desconectados

Una ejecución desde un origen visita únicamente su componente. Para recorrer todo un grafo desconectado debemos iniciar nuevas búsquedas desde los vértices todavía no visitados.

El resultado es un bosque DFS: un árbol de búsqueda por cada componente conexa.

20.9 DFS recursivo en JavaScript

function dfs(grafo, actual, visitados = new Set()) {
  visitados.add(actual);
  console.log(actual);

  for (const vecino of grafo[actual]) {
    if (!visitados.has(vecino)) {
      dfs(grafo, vecino, visitados);
    }
  }
  return visitados;
}

const grafo = { A: ["B", "C"], B: ["A", "D"], C: ["A"], D: ["B"] };
dfs(grafo, "A");

20.10 DFS iterativo

function dfsIterativo(grafo, origen) {
  const visitados = new Set();
  const pila = [origen];

  while (pila.length) {
    const actual = pila.pop();
    if (visitados.has(actual)) continue;
    visitados.add(actual);
    console.log(actual);

    for (const vecino of [...grafo[actual]].reverse()) {
      if (!visitados.has(vecino)) pila.push(vecino);
    }
  }
}

20.11 Complejidad y aplicaciones

Con listas de adyacencia, DFS utiliza tiempo O(V + E) y espacio O(V).

20.12 Errores comunes

• No marcar un vértice antes de visitar sus vecinos.
• Olvidar el conjunto de visitados y entrar en ciclos infinitos.
• Suponer que el orden de DFS es único.
• Usar recursión profunda sin considerar el límite de la pila.
• Recorrer solo una componente de un grafo desconectado.
• Confundir pila LIFO con cola FIFO.

20.13 Qué debes recordar de este tema

• DFS profundiza por una rama antes de retroceder.
• Utiliza una pila explícita o la pila de recursión.
• El conjunto de visitados evita repeticiones infinitas.
• El orden depende del origen y de los vecinos.
• Las aristas de descubrimiento forman un árbol DFS.
• Su complejidad es O(V + E).

20.14 Conclusión

DFS explora grafos mediante profundidad y retroceso. Su estructura simple sirve como base para conectividad, ciclos, componentes y numerosos algoritmos avanzados.

En el próximo tema estudiaremos BFS, que explora por niveles utilizando una cola.