Búsqueda en profundidad

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
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 que permite 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).

Pseudocódigo[editar]

  • 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[editar]

/**
Jorge Alejandro Jimenez Luna
Algorithm: BFS (Graph)
*/

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

using namespace std;

int N, A, K, D[oo]; ///N: Cant. de Nodo A: Cant. de Aristas K: Cant. de Intrucciones
bool Mk[oo];
vector<int> V[oo];
queue<int> Q;
char S;             ///Caracter Separador

void BFS ()
{
    int nodo = 0, newNod = 0, ady = 0;

    Q.push(0);

    while(!Q.empty())
    {
        nodo = Q.front();
        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("BFS.in", "r", stdin);
    freopen("BFS.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;

    BFS();

    for(int i = 0; i < K; i++)
    {
        cin >> C_1;
        cout << D[C_1] << "\n";
    }

    return 0;
}

Código en matrix[editar]

/**
Jorge Alejandro Jimenez Luna
Algorithm: BFS (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 BFS ()
{
    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("BFS.in", "r", stdin);
    freopen("BFS.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;
    BFS();
    printf("%d\n", CA[_e.f][_e.c]);

    return 0;
}

Arcos DF[editar]

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[editar]

  • 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[editar]