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
- 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.
- Wikimedia Commons alberga una categoría multimedia sobre Búsqueda en profundidad.