6.3.3 En profundidad
6.3.3 Búsqueda en
profundidad
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 <bits/stdc++.h>
#include <stack>
#define oo 1005
using namespace std;
int N, A, K, D[oo]; ///N: Cant. de Nodo A: Cant. de Aristas K:
Cant. de Instrucciones
bool Mk[oo];
vector<int> V[oo];
stack<int> Q;
char S; ///Caracter Separador
void DFS ()
{
, newNod
= 0, ady = 0;
Q.push(0);
while(!Q.empty())
{
nodo = Q.top();
Q.pop();
vector<int>::iterator i;
for(i = V[nodo].begin(); i != V[nodo].end(); i++)
{
ady = *i;
if(Mk[ady])
continue;
Mk[ady] = true;
D[ady] = D[nodo] + 1;
Q.push(ady);
}
}
}
int main ()
{
freopen("DFS.in", "r", stdin);
freopen("DFS.out", "w", stdout);
int C_1, C_2;
cin
>> N >> A >> K;
for(int i = 0; i < A; i++)
{
cin >> C_1 >> C_2;
V[C_1].push_back(C_2);
V[C_2].push_back(C_1);
}
D[0] = 0;
Mk[0] = true;
DFS();
for(int i = 0; i < K; i++)
{
cin >> C_1;
cout << D[C_1] << "\n";
}
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|)
No comments