Algoritmo DFS: Implementación Recursiva

DFS (Búsqueda en Profundidad, por sus siglas en inglés) es un algoritmo utilizado para recorrer o buscar en estructuras de datos como árboles y grafos. Su principio fundamental es: explorar lo más profundamente posible a lo largo de una ruta hasta que no se pueda continuar (se encuentra un nodo ya visitado o no hay nodos adyacentes no visitados), luego retroceder al nodo anterior y elegir otra ruta no explorada para continuar profundizando.

• Se utiliza para explorar todas las posibles rutas
• Se caracteriza por su enfoque de profundidad, siendo adecuado para manejar relaciones de orden, conectividad y búsqueda de todas las rutas posibles
• La búsqueda en profundidad puede determinar la longitud de la ruta más corta entre dos puntos

Aplicaciones del DFS

1. Recorrido de grafos: determinación de conectividad, búsqueda de componentes fuertemente conexas (SCC).
2. Búsqueda de caminos: resolución de laberintos, verificación de existencia de caminos entre dos puntos.
3. Ordenamiento topológico: en grafos acíclicos dirigidos (DAG) para planificación de tareas.
4. Método de retroceso: problemas de permutaciones, combinaciones, N-reinas, entre otros.

Principios del DFS

El proceso de recorrido DFS es similar a "resolver un laberinto": partir de un punto inicial, elegir una dirección y avanzar hasta el final, encontrar un obstáculo y regresar a la última intersección, elegir otra dirección y continuar, hasta haber visitado todos los nodos alcanzables.

• Naturaleza recursiva: DFS es inherentemente adecuado para implementación recursiva (las llamadas recursivas forman una estructura de pila que guarda los "puntos de retroceso").
• Implementación no recursiva: también puede simularse utilizando una pila (Stack) manualmente, registrando nodos por visitar y rutas de retroceso.
• Marcado de visitas: es necesario un mecanismo de "marcado de visitados" (como un array booleano) para evitar visitas repetidas y bucles infinitos (especialmente en grafos con ciclos).

Plantilla General (Versión Recursiva)

DFS(nodo_actual u) {
  // Marcar el nodo actual como visitado
  visitado[u] = true;

  // Procesar el nodo actual u
  procesar(u);

  // Recorrer recursivamente todos los nodos adyacentes no visitados
  para(todos los nodos v alcanzables desde u) {
    si(v no visitado) {
      DFS(v);  // Recursión hacia v
    }
  }
}

// Forma de invocar
inicializar array visitado con false;
DFS(nodo_inicial s);

Plantilla General (Versión No Recursiva)

DFS(nodo_inicial s) {
  // Inicialización
  array visitado: marca si un nodo ha sido visitado, inicializado en false
  pila pila: almacena nodos por visitar
  introducir nodo_inicial s en pila;
  visitado[s] = true;  // Marcar nodo inicial como visitado

  // Ciclo para procesar todos los nodos en la pila
  mientras(pila no vacía) {
    // Tomar nodo superior u de la pila
    u = nodo superior de pila;
    extraer nodo superior;

    // Procesar nodo actual u (ej: salida, registro de ruta, etc.)
    procesar(u);

    // Recorrer todos los nodos adyacentes v de u (en orden inverso para mantener consistencia)
    para(todos los nodos v alcanzables desde u, en orden inverso) {
      si(v no visitado) {
        visitado[v] = true;  // Marcar como visitado
        introducir v en pila;  // Agregar para procesamiento posterior
      }
    }
  }
}

Pasos de Implementación del DFS (Ejemplo con Grafos)

Supongamos que almacenamos el grafo usando una lista de adyacencia (ady es un array donde ady[u] representa todos los nodos adyacentes al nodo u). A continuación se presentan los pasos estándar para implementar DFS:

Paso 1: Preparar Estructuras de Datos

• Almacenamiento del grafo: usar lista de adyacencia vector<vector>> ady</vector> para representar el grafo (adecuada para grafos dispersos, más eficiente).
• Marcado de visitas: usar array booleano visitado[] para marcar nodos visitados (inicializado en false).
• Nodo inicial: comenzar el recorrido desde un nodo de inicio especificado inicio.

Paso 2: Lógica Central de la Implementación Recursiva de DFS

1. Marcar nodo actual como visitado: al entrar a la función, establecer visitado[actual] = true, indicando que el nodo ha sido procesado.
2. Procesar nodo actual: realizar operaciones específicas según los requisitos (ej: imprimir valor del nodo, registrar ruta, etc.).
3. Recorrer todos los nodos adyacentes: para cada nodo adyacente siguiente del nodo actual:
   • Si siguiente no ha sido visitado (!visitado[siguiente]), llamar recursivamente a dfs(siguiente) para explorar profundamente esa ruta.
   • Si siguiente ya ha sido visitado, omitir (evitar repeticiones o bucles infinitos).
4. Retorno automático: cuando todos los nodos adyacentes del nodo actual han sido procesados, la función retorna automáticamente (retrocede a la llamada anterior), continuando con el procesamiento de otros nodos adyacentes del nodo anterior.

Paso 3: Implementación No Recursiva (Simulación con Pila)

Si la recursión es demasiado profunda y podría causar desbordamiento de pila, se puede usar una pila para simular manualmente el proceso DFS:

1. Crear una pila y agregar el nodo de inicio inicio, marcando visitado[inicio] = true.
2. Mienrtas la pila no esté vacía:
   • Extraer el nodo superior actual de la pila y procesarlo.
   • Recorrer todos los nodos adyacentes siguiente de actual:
     • Si siguiente no ha sido visitado, marcar visitado[siguiente] = true y agregarlo a la pila (nota: para mantener consistencia con el orden recursivo, generalmente se agregan en orden inverso los nodos adyacentes).
3. Repetir los pasos 2 hasta que la pila esté vacía.

Ejemplos de Código (Implementación en C++)

Tomemos como ejemplo un grafo no dirigido con la siguiente estructura (nodos 0-4):

0 conectado con 1, 2
1 conectado con 0, 3, 4
2 conectado con 0
3 conectado con 1
4 conectado con 1

Implementación Recursiva

#include <iostream>
#include <vector>
using namespace std;

// Almacenamiento del grafo con lista de adyacencia
vector<vector>> grafo;
// Array de marcado de visitas
vector<bool> procesado;

// Función DFS recursiva: comienza el recorrido desde nodo u
void explorarDFS(int u) {
    // 1. Marcar nodo actual como visitado
    procesado[u] = true;
    // 2. Procesar nodo actual (simple impresión)
    cout << u << " ";
    
    // 3. Recorrer todos los nodos adyacentes, recursivamente visitar los no visitados
    for (int v : grafo[u]) {
        if (!procesado[v]) {  // Solo visitar nodos no visitados
            explorarDFS(v);
        }
    }
    // 4. El retorno de la función implica retroceso automático
}

int main() {
    // Inicializar grafo (5 nodos: 0-4)
    int n = 5;
    grafo.resize(n);
    procesado.resize(n, false);
    
    // Agregar aristas (grafo no dirigido, agregar en ambas direcciones)
    grafo[0].push_back(1);
    grafo[0].push_back(2);
    grafo[1].push_back(0);
    grafo[1].push_back(3);
    grafo[1].push_back(4);
    grafo[2].push_back(0);
    grafo[3].push_back(1);
    grafo[4].push_back(1);
    
    // Comenzar DFS desde nodo 0
    cout << "Resultado de recorrido DFS (recursivo):";
    explorarDFS(0);  // Salida: 0 1 3 4 2
    return 0;
}
</bool></vector></vector></iostream>

Implementación No Recursiva (Simulación con Pila)

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

// DFS no recursivo: simular con pila
void explorarDFS(int inicio, const vector<vector>>& grafo) {
    int n = grafo.size();
    vector<bool> visitado(n, false);
    stack<int> pila;
    
    // 1. Nodo inicial entra en pila y se marca
    pila.push(inicio);
    visitado[inicio] = true;
    
    cout << "Resultado de recorrido DFS (no recursivo):";
    
    // 2. Ciclo mientras la pila no esté vacía
    while (!pila.empty()) {
        // Extraer nodo superior y procesar
        int u = pila.top();
        pila.pop();
        cout << u << " ";
        
        // 3. Nodos adyacentes entran en pila (en orden inverso para mantener consistencia)
        // Nota: la pila es LIFO (último en entrar, primero en salir), el orden inverso garantiza
        // que los nodos adyacentes se visiten en el mismo orden que en la versión recursiva
        for (auto it = grafo[u].rbegin(); it != grafo[u].rend(); ++it) {
            int v = *it;
            if (!visitado[v]) {
                visitado[v] = true;
                pila.push(v);
            }
        }
    }
}

int main() {
    // Estructura del grafo igual que en el ejemplo recursivo
    int n = 5;
    vector<vector>> grafo(n);
    
    grafo[0].push_back(1);
    grafo[0].push_back(2);
    grafo[1].push_back(0);
    grafo[1].push_back(3);
    grafo[1].push_back(4);
    grafo[2].push_back(0);
    grafo[3].push_back(1);
    grafo[4].push_back(1);
    
    // Comenzar DFS desde nodo 0
    explorarDFS(0, grafo);  // Salida: 0 1 3 4 2
    return 0;
}
</vector></int></bool></vector></stack></vector></iostream>

Complejidad Temporal

• Para grafos: recorrer todos los nodos V y aristas E, la complejidad temporal es O(V + E).
• Para árboles (un caso especial de grafos, donde E = V-1): la complejidad temporal es O(V).

En resumen: el núcleo de DFS es "profundizar primero, retroceder para explorar", implementado mediante recursión o pilas. Lo clave es usar marcado de visitas para evitar repeticiones, ampliamente aplicado en diversos problemas de búsqueda y recorrido.