Búsqueda en profundidad para niños

Búsqueda en profundidad.(Orden en el que se visitan los nodos)

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

En inglés: Depth-first search Facts for Kids

• Á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.