Búsqueda en profundidad

Una Búsqueda en profundidad (en inglés DFS o Depth First Search) es un algoritmo de búsqueda no informada utilizado para recorrer todos los nodos de un grafo o árbol (teoría de grafos) de manera ordenada, pero no uniforme. Su funcionamiento consiste en ir expandiendo todos y cada uno de los nodos que va localizando, de forma recurrente, en un camino concreto. Cuando ya no quedan más nodos que visitar en dicho camino, regresa (Backtracking), de modo que repite el mismo proceso con cada uno de los hermanos del nodo ya procesado.

Análogamente existe el algoritmo de búsqueda en anchura (BFS o Breadth First Search).

Evaluación 

Completitud: DFS es completo si y solo si usamos búsqueda basada en grafos en espacios de estado finitos, pues todos los nodos serán expandidos.

Optimalidad: DFS en ningún caso asegura la optimalidad, pues puede encontrar una solución más profunda que otra en una rama que todavía no ha sido expandida.

Complejidad temporal: en el peor caso, es , siendo b el factor de ramificación (número promedio de ramificaciones por nodo) y m la máxima profundidad del espacio de estados.

Complejidad espacial: , siendo b el factor de ramificación y d la profundidad de la solución menos costosa, pues cada nodo generado permanece en memoria, almacenándose la mayor cantidad de nodos en el nivel meta.

Ejemplo 
Para el grafo siguiente:

una búsqueda en profundidad empezando en el nodo A, con la suposición que las aristas a la izquierda son escogidas antes de las aristas a la derecha, el algoritmo va a visitar los nodos en esta orden: A, B, D, F, E, C, G. Se puede notar que si el algoritmo no recuerde los nodos ya visitados, el algoritmo podría continuar en una vuelta infinita A, B, D, F, E, A, B, D, F, E, etc. sin visitar C o G.

Para evitar esta vuelta infinita, puede usar técnicas como búsqueda en profundidad iterativa.

Pseudocódigo 

 Pseudocódigo para grafos

   DFS(grafo G)
      PARA CADA vértice u ∈ V[G] HACER
              estado[u] ← NO_VISITADO
              padre[u] ← NULO
      tiempo ← 0
      PARA CADA vértice u ∈ V[G] HACER
              SI estado[u] = NO_VISITADO ENTONCES
                      DFS_Visitar(u,tiempo)

   DFS_Visitar(nodo u, int tiempo)
      estado[u] ← VISITADO
      tiempo ← tiempo + 1
      d[u] ← tiempo
      PARA CADA v ∈ Vecinos[u] HACER
              SI estado[v] = NO_VISITADO ENTONCES
                      padre[v] ← u
                      DFS_Visitar(v,tiempo)
      estado[u] ← TERMINADO
      tiempo ← tiempo + 1
      f[u] ← tiempo

Código para grafos
/**
Algorithm: DFS (Graph)
*/

#include <iostream>
#include <vector>

using namespace std;

const int MAX_CANT_NODES = 1000;
vector<int> graph[MAX_CANT_NODES]; // Lista de adjacencia
bool vst[MAX_CANT_NODES]; // Vector de nodos visitados

void dfs (in
    vst[u] = true;

    for (int v : graph[u])
        if (!vst[v])
            dfs(v);
}

int main () {
    int n, m; // n: Cantidad de nodos, m: Cantidad de aristas
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;

        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    for (int i = 0; i < n; i++)
        if (!vst[i])
            dfs(i);

    return 0;
}

Código en matrix
/**
Algorithm: DFS (Matrix)
*/

#include <bits/stdc++.h>
#define oo 1005

using namespace std;

struct two
{
    int f, c;

    two(int a = 0, int b = 0)
    {
        f = a;
        c = b;
    }
};

const int Mf [] = {1, -1, 0, 0};
const int Mc [] = {0, 0, 1, -1};

int N, M, CA[oo][oo];
bool Mk[oo][oo];
queue<two> Q;

bool isPossible (int f, int c)  ///Saber si es posible el movimiento hacia esa casilla
{
    if(f < 0 || f > N - 1 || c < 0 || c > M - 1 || Mk[f][c])
        return false;
    return true;
}

void DFS ()
{
    int F, C;

    while(!Q.empty())
    {
        F = Q.front().f;
        C = Q.front().c;

        Q.pop();

        for(int i = 0; i < 4; i++)
        {
            int nf = F + Mf[i];
            int nc = C + Mc[i];

            if(isPossible(nf, nc))
            {
                CA[nf][nc] = CA[F][C] + 1;
                Mk[nf][nc] = true;
                Q.push(two (nf, nc));
            }
        }
    }
}

int main ()
{
    freopen("DFS.in", "r", stdin);
    freopen("DFS.out", "w", stdout);

    int X = 0;
    two _s, _e; ///Punto de Inicio

    cin >> N >> M;

    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            scanf("%s", &X); ///Leer como caracter pero asignar a numero
            if(X == 83) ///Inicio Letra - S
            {
                _s.f = i;
                _s.c = j;
                continue;
            }
            if(X == 69) ///Final Letra - E
            {
                _e.f = i;
                _e.c = j;
                continue;
            }
            if(X == 1)  ///Rocas
            {
                Mk[i][j] = true;
                continue;
            }
        }
    }
    Q.push(two (_s.f, _s.c));
    CA[0][0] = 0;
    Mk[0][0] = true;
    DFS();
    printf("%d\n", CA[_e.f][_e.c]);

    return 0;
}

Arcos DF 
Si en tiempo de descubrimiento de u tenemos el arco (u,v):

i. Si el estado de v es NO_VISITADO, entonces (u,v) ∈ DF,

El tiempo de ejecución es O(|V|+|E|)

Véase también 

 Árbol (estructura de datos)
 Recorrido de árboles
 Búsqueda en anchura

 Lema: Un grafo dirigido es cíclico si y sólo si al ejecutar DFS(G) produce al menos un arco hacia atrás.

Referencias 

 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 22.3: Depth-first search, pp.540–549.

Árboles (estructura)
Algoritmos de búsqueda
Algoritmos de grafos