ALGORITMO DE BÚSQUEDA: DEPTH FIRST SEARCH

Posted: March 5, 2011 in Algoritmos

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 pseudocodigo:

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 S

Código en C++:  Algoritmo DFS usando Stack

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

Codigo C++:  Algoritmo DFS usando Recursion

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 caidos

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 caidos. Para la segunda consulta caéran solamente 4->3, y finalmente para 6 caerán 6->7->8

La solución lo relizaremos 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"
      }
    }
}

Codigo C++: DFS Ejemplo – Domino

Componentes Conexas

Algun 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 estandar 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 ] );
       }
    }
}

Codigo C++: DFS Ejemplo – Conectividad

A continuación algunos problemas que pueden ser resueltos con este algoritmo:

JUEZ UVA:

459 – Graph Connectivity

Varios Problemas se encuentran en el UvaToolkit colocando en el buscador DFS

JUEZ PKU:

2245 – Lotto

TOPCODER:

SRM 371: DIV 2 – 1000  FloodRelief

SRM 407: DIV 2 – 500 CorporationSalary

SRM 435 : DIV 1 – 250 CellRemoval

Se irán agregando mas adelante mas problemas de otros jueces asi como más aplicaciones de DFS.

Resumen de códigos:

Código en C++:  Algoritmo DFS usando Stack

Código en C++:  Algoritmo DFS usando Recursion

Código en C++: DFS Ejemplo – Domino

Código en C++: DFS Ejemplo – Conectividad

Por: Jhosimar George Arias Figueroa

[Saludos, les escribe Jhosimar Arias autor de los tutoriales aqui mostrados y parte de algunos posts. Escribo este post para hacerles llegar mi blog propio:

http://jariasf.wordpress.com/

Traslade mis 2 tutoriales de DFS y BFS, asi mismo agregue algunas cosas a ambos como mas imagenes en el caso de DFS y un punto mas en el BFS. Posteare mas tutoriales en mi propio blog asi como soluciones de problemas de jueces que parezcan interesantes.]

Comments
  1. Gzi says:

    Una pregunta la página de http://acm.tju.edu.cn/toj esta disponible para hacer ejercicios???? Es que he intentando acceder pero no puedo.

  2. El TJU no es un juez estable, cada cierto tiempo no es posible acceder como ahora, te recomiendo entrenar de otros sitios… el UVA es una excelente opcion.

  3. Marcos says:

    Al parecer ya no hay actividad en este blog😦

  4. melkfis says:

    como se podria modificar ese algoritmo de las componentes conexas usando DFS para obtener los vertices que forman a cada componente?

    • Para ver vertices de cada componente una posible solucion seria usar un arreglo de visitado exclusivo para cada componente e irlo limpiando cada vez que encuentra una nueva componente, modificacion vendria asi en el codigo DFS EJEMPLO CONECTIVIDAD:

      void dfs( int u ){
      visitado[ u ] = true;
      visitado_componente[ u ] = true;
      ….

      int main(){

      if( !visitado[ i ] ){
      // limpio vertices vistos en la componente anterior
      memset( visitado_componente , 0 , sizeof( visitado_componente ) );
      dfs( i );
      printf(“Componente %d:” , total + 1 );
      //imprimo vertices de componente actual
      for( int j = 1 ; j <= V ; ++j )
      if( visitado_componente[ j ] ) printf(" %d" , j );
      printf("\n\n");
      total++; //incrementamos cantidad de componentes
      }

      • Merkhus67 says:

        Estaba leyendo la solucion de Algoritmo DFS usando recursion y dentro del dfs realizas esta instruccion

        ( first )? printf(“%d” , u ) : printf(“->%d” , u );

        que hace exactamente?. Disculpa mi ignorancia..pero no la entiendo. Saludos y excelente blog!

      • ( first )? printf(“%d” , u ) : printf(“->%d” , u );

        Me imprimira el primer valor sin los caracteres -> anteponiendolo, osea si tengo digamos 2 , 3, 4, 5 me imprimira 2->3->4->5. Antes del 2 no ira “->”. Eso sirve para algunos jueces cuando pide q imprimas espacios en blanco entre los valores, ya que si pones solamente usas
        printf(“ %d” , u ); tendriamos un espacio en blanco al inicio (_2 3 4 5)

        O si usas printf(“%d ” , u ); tendriamos un espacio en blanco al final (2 3 4 5_) por eso se pone un condicion de si es el 1ero q voy imprimir pues que me imprima solo el numero.

  5. Vlad says:

    Alguien podria ayudarme con el problema del domino pero aplicandolo en JAVA? En serio me urge :S

  6. El Yonki says:

    Me haria falta saber como puedo usar el algoritmo de dfs para obtener puntos de articulacion de un grafo cualquiera

  7. Juancho says:

    Ojo que hay un paso de más en el pseudocódigo inicial: es la línea 6, en la que se hace lo siguiente:

    6: marcamos como visitado v

    Eso no hace falta porque en la llamada recursiva el nodo es lo primero que se marca.

    Saludos

  8. marin says:

    como se podria usar con matriz de adyacencia?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s