thumb|250px|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: izquierda|miniaturadeimagen

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 entonces que, si el algoritmo no llegara a recordar los nodos ya visitados, entonces podría continuar en un bucle infinito: A, B, D, F, E, A, B, D, F, E, etc. sin visitar C o G.

Para evitar este bucle infinito, se pueden utilizar técnicas como la 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; Mk = 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.

Categoría:Árboles (estructura) Categoría:Algoritmos de búsqueda Categoría:Algoritmos de grafos