Todo se puede aprender
...si se quiere.
Home » , , » Algoritmo de Búsqueda DFS: DEPTH FIRST SEARCH

Algoritmo de Búsqueda DFS: DEPTH FIRST SEARCH

El algoritmo de búsqueda que se explicará a continuación es Depth First Search ( DFS ) se explicará el algoritmo de manera similar a como se hizo BFS, proponiendo problemas y otorgando códigos del algoritmo en si.

Descripción

El algoritmo DFS posee varias aplicaciones la mas importante es para problemas de conectividad,  si un grafo es conexo, detectar ciclos en un grafo,  numero de componentes conexas,  etc y es bastante útil en otro algoritmos como para hallar las componentes fuertemente conexas en un grafo ( Algoritmo de Kosaraju, Algoritmo de Tarjan), para hallar puntos de articulación o componentes biconexas ( puentes ),  para recorrido en un circuito o camino euleriano, topological sort, flood fill y otras aplicaciones.

Como trabaja?

DFS va formando un árbol al igual que BFS pero lo hace a profundidad. Existen dos formas de hacer el recorrido una es usando una Pila y otra de manera recursiva:

Usando Stack

El concepto es el mismo que BFS solo que se cambia la Cola por una Pila, el proceso es como sigue: visitar el nodo inicial y ponerlo en la pila, ahora para ver los siguientes nodos a visitar sacamos el nodo tope de la pila y vemos sus adyacentes, los que no han sido visitados los insertamos en la pila. El proceso se repite hasta que la pila se encuentre vacía ( se han visitado todos los nodos ).

Algoritmo en pseudocódigo:

1  método DFS( origen):

2      creamos una pila S

3      agregamos origen a la pila S

4      marcamos origen como visitado

5      mientras S no este vacío:

6          sacamos un elemento de la pila S llamado v

7          para cada vertice w adyacente a v en el Grafo: 

8              si w no ah sido visitado:

9                 marcamos como visitado w

10                 insertamos w dentro de la pila 

Usando Recursión

Usar la recursión es mucho mas fácil y ademas muy útil, es la forma mas usada en la solución de problemas con este algoritmo.

Algoritmo en pseudocódigo: 
1  método DFS( origen):
2      marcamos origen como visitado 
3          para cada vertice v adyacente a origen en el Grafo: 
4              si v no ah sido visitado:
5                 marcamos como visitado v
6                 llamamos recursivamente DFS( v )  

Tomemos como ejemplo el siguiente grafo no dirigido: 

Al igual que con la pila requerimos un nodo inicial, de manera recursiva llamamos a los adyacentes del nodo inicial, de esta forma se puede ver si llamamos inicialmente a “1”:

Inicial “1”: marcamos “1” como visitado, sus adyacentes son “2”,  “3” y “5”.

Visitados: 1.

Adyacentes de 1: 2 , 3 , 5

En la llamada recursiva ira el primero insertado en la lista de adyacencia, en este caso “2”, marcamos como visitado. Ahora el inicial es “2”, sus adyacentes son “1” , “4” y “5”.

Visitados: 1 , 2

Adyacentes de 2: 1, 4 , 5

Evaluamos el 1ero de la lista que es “1” pero ya fue visitado por lo tanto sigo con el siguiente, en este caso “4” , marcamos como visitado. Ahora inicial es “4”, sus adyacentes son “2”.

Visitados: 1 , 2 , 4

Adyacentes de 4: 2

Tocaria el nodo 2 pero ya fue visitado termina la recursion por ese lado. El siguiente adyacente de “2” es “5”. Ahora inicial es “5”, marcamos como visitado, sus adyacentes son “1” y “2”.

Visitados: 1 , 2 , 4 , 5

Adyacentes de 5: 1 , 2

Igual que con nodo “4” sus adyacentes han sido visitados por lo tanto terminamos la recursion por el nodo “2”.

El nodo actual es “1”, sus adyacentes eran “2”, “5” y “3”, estabamos evaluando por “2” pero ya terminamos el siguiente es “5” el cual ya fue visitado, continuamos con “3” este no fue visitado, marcamos como visitado, vemos sus adyacentes “1”.

Visitados: 1 , 2 , 4 , 5 , 3

Adyacentes de 3: 1

Como nodo “1” ya fue visitado entonces termina la recursión y termina el recorrido DFS. Como se puede observar el orden en que fueron visitados los nodos es el recorrido DFS del grafo.

Posibles Paths en un grafo

Otra ayuda importantisima del algoritmo recursivo es que nos permite hallar todos los posibles paths( rutas) de un nodo inicial a otro final, ello lo conseguiremos usando backtracking dentro del algoritmo:

Algoritmo en pseudocódigo:

1  método DFS( origen,final):

2      marcamos origen como visitado 

3      recuperar el path si se llego a final

4          para cada vertice v adyacente a origen en el Grafo: 

5              si v no ah sido visitado:

6                 marcamos como visitado v

7                 llamamos recursivamente DFS( v )

8      marcamos origen como no visitado

Ejemplo Aplicativo:

Tengamos un juego de dominos donde si hago caer uno domino, todos los demas dominos que siguen a este caerán. Dado el numero de dominos “n”, el estado del juego en la forma “x y” ( si domino “x” cae entonces domino “y” tambien caerá) , la cantidad de consultas a realizar, cada consulta sera el numero del domino el cual yo impulsaré. El problema me pide hallar cuantos dominos caeran a partir del domino que yo impulsé.

Supongamos la entrada:

8 6 3  ( 8 dominos, 6 enlaces de dominos y 3 consultas  )

1 2

2 5

5 3

4 3

6 7

7 8

1

4

6

Solución

Declaremos nuestras variables globales: 

vector<int> ady[ MAX ]; //lista de adyacencia
int total; //la cantidad total de dominos que caerán
bool visitado[ MAX ]; //arreglo de dominos caídos

Modelemos el problema como un grado dirigido:

Ahora vemos cada consulta, la primera nos indica que impulsaré el domino numero 1, entonces al hacer ello los dominos que caerán serán 1 -> 2 -> 5 ->3, debo retornar 4 la cantidad de dominos caídos. Para la segunda consulta caéran solamente 4->3, y finalmente para 6 caerán 6->7->8

La solución lo realizaremos con un DFS como sigue:
void dfs( int u ){                          //domino origen
    total++;                                //aumento en mi respuesta la caida de un domino
    visitado[ u ] = true;                   //domino "u" cayo
    for( int v = 0 ; v < ady[ u ].size(); ++v ){ //verifico los demas posibles domino que caeran si impulso "u"
      if( !visitado[ ady[ u ][ v ] ] ){         //si el domino adyacente no cayó entonces es el siguiente a evaluar
         dfs( ady[ u ][ v ] );               //recursivamente veo que dominos caeran a partir del adyacente de "u"
      }
    }
}

Componentes Conexas

Algún problema puede ser que nos pida hallar la cantidad de componentes conexas, supongamos el siguiente grafo no dirigido:

La cantidad de componentes conexas es 2. El problema puede ser resuelto de la siguiente manera:

Evaluamos todos los vertices posibles y los tomamos como origen aquellos no visitados:
for( int i = 1 ; i <= V ; ++i ){    //recorremos todos los posibles vertices
    if( !visitado[ i ] ){          //si alguno no fue visitado tenemos una componente a partir de ese nodo
       dfs( i );                  //recorremos a partir de nodo i todo el grafo que se forma
       total++;                   //incrementamos cantidad de componentes
    }
}

Usamos el algoritmo estándar DFS para cada recorrido:
void dfs( int u ){
    visitado[ u ] = true;
    for( int v = 0 ; v < ady[ u ].size(); ++v ){
       if( !visitado[ ady[ u ][ v ] ] ){
           dfs( ady[ u ][ v ] );
       }
    }
}