ALGORITMO DE BÚSQUEDA: DEPTH FIRST SEARCH (PARTE 1) |... [Link]

Algorithms and More

Blog about programming!

ALGORITMO DE BÚSQUEDA: DEPTH FIRST SEARCH (PARTE 1)

Publicado el marzo 2, 2012| 10 comentarios

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

1 de 17 28/1/2020 9:44 p. m.
ALGORITMO DE BÚSQUEDA: DEPTH FIRST SEARCH (PARTE 1) |... [Link]

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:

2 de 17 28/1/2020 9:44 p. m.
ALGORITMO DE BÚSQUEDA: DEPTH FIRST SEARCH (PARTE 1) |... [Link]

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

3 de 17 28/1/2020 9:44 p. m.
ALGORITMO DE BÚSQUEDA: DEPTH FIRST SEARCH (PARTE 1) |... [Link]

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

4 de 17 28/1/2020 9:44 p. m.
ALGORITMO DE BÚSQUEDA: DEPTH FIRST SEARCH (PARTE 1) |... [Link]

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

5 de 17 28/1/2020 9:44 p. m.
ALGORITMO DE BÚSQUEDA: DEPTH FIRST SEARCH (PARTE 1) |... [Link]

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

6 de 17 28/1/2020 9:44 p. m.
ALGORITMO DE BÚSQUEDA: DEPTH FIRST SEARCH (PARTE 1) |... [Link]

7 llamamos recursivamente DFS( v )

8 marcamos origen como no visitado

Codigo C++: Algoritmo DFS usando Recursion

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:

1 ...
2 for( int i = 1 ; i <= V ; ++i ){ //recorremos todos los posibles vertices
3 if( !visitado[ i ] ){ //si alguno no fue visitado tenemos una componente a partir de ese nod
4 dfs( i ); //recorremos a partir de nodo i todo el grafo que se forma
5 total++; //incrementamos cantidad de componentes
6 }
7 }
8 ...

Usamos el algoritmo estandar DFS para cada recorrido:

1 void dfs( int u ){

2 visitado[ u ] = true;
3 visitado_componente[ u ] = true;
4 for( int v = 0 ; v < ady[ u ].size(); ++v ){
5 if( !visitado[ ady[ u ][ v ] ] ){
6 dfs( ady[ u ][ v ] );
7 }
8 }

7 de 17 28/1/2020 9:44 p. m.
ALGORITMO DE BÚSQUEDA: DEPTH FIRST SEARCH (PARTE 1) |... [Link]

9 }

Veamos gráficamente, el código anterior parte evaluando el vértice 1:

i=1
Visitados: Ninguno

Como no fue visitado entonces hacemos recorrido DFS partiendo de ese vértice ( dfs( i = 1 ) ). Entonces veamos el
recorrido:

Vértice Actual: 1
Vértices Adyacentes: 2
Vértices Visitados: 1

8 de 17 28/1/2020 9:44 p. m.
ALGORITMO DE BÚSQUEDA: DEPTH FIRST SEARCH (PARTE 1) |... [Link]

El siguiente paso es evaluar los adyacentes:

Vértice Actual: 2
Vértices Adyacentes: 3
Vértices Visitados: 1, 2

Vértice Actual: 3
Vértices Adyacentes: 2
Vértices Visitados: 1, 2, 3

9 de 17 28/1/2020 9:44 p. m.
ALGORITMO DE BÚSQUEDA: DEPTH FIRST SEARCH (PARTE 1) |... [Link]

Terminamos la función de DFS partiendo del vértice 1. Ahora volvemos al for inicial e incrementamos las
componentes.

1 ...
2 if( !visitado[ i ] ){
3 dfs( i );
4 total++; //incrementamos numero de componentes
5 }
6 ...

Ahora tenemos i = 2 pero 2 ya fue visitado por lo que no entraría al if, igual para i=3 que ya fue visitado; sin
embargo para i=4 este no fue visitado por lo tanto hacemos recorrido dfs partiendo del vértice 4:

i=4
Visitados: 1, 2, 3

Vértice Actual: 4
Vértices Adyacentes: 5
Vértices Visitados: 1, 2, 3, 4

10 de 17 28/1/2020 9:44 p. m.
ALGORITMO DE BÚSQUEDA: DEPTH FIRST SEARCH (PARTE 1) |... [Link]

Como 5 no fue visitado es el siguiente a evaluar:

Vértice Actual: 5
Vértices Adyacentes: 4
Vértices Visitados: 1, 2, 3, 4, 5

11 de 17 28/1/2020 9:44 p. m.
ALGORITMO DE BÚSQUEDA: DEPTH FIRST SEARCH (PARTE 1) |... [Link]

Terminamos DFS partiendo del vértice 4, entonces volvemos al if e incrementamos el numero de componentes,
de esta manera el resultado será de 2 componentes.

Codigo C++: DFS Ejemplo – Conectividad

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 )

12

25

53

43

67

78

Solución

Declaremos nuestras variables globales:

1 vector<int> ady[ MAX ]; //lista de adyacencia

2 int total; //la cantidad total de dominos que caerán
3 bool visitado[ MAX ]; //arreglo de domino caido

Modelemos el problema como un grado dirigido:

12 de 17 28/1/2020 9:44 p. m.
ALGORITMO DE BÚSQUEDA: DEPTH FIRST SEARCH (PARTE 1) |... [Link]

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:

1 void dfs( int u ){ //domino origen

2 total++; //aumento en mi respuesta la caida de un domino
3 visitado[ u ] = true; //domino "u" cayo
4 for( int v = 0 ; v < ady[ u ].size(); ++v ){ //verifico los demas posibles domino que caeran si impul
5 if( !visitado[ ady[ u ][ v ] ] ){ //si el domino adyacente no cayó entonces es el siguie
6 dfs( ady[ u ][ v ] ); //recursivamente veo que dominos caeran a partir del ady
7 }
8 }
9 }

Codigo C++: DFS Ejemplo – Domino

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

13 de 17 28/1/2020 9:44 p. m.
ALGORITMO DE BÚSQUEDA: DEPTH FIRST SEARCH (PARTE 1) |... [Link]

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

SHARE THIS:

 Twitter  Facebook

Me gusta
Sé el primero en decir que te gusta.

Esta entrada fue publicada en Algorithms, Main y etiquetada backtracking, depth first search, dfs, graph, search.
Guarda el enlace permanente.

10 RESPUESTAS A “ALGORITM O DE BÚSQUEDA: DEPTH FIRST SEARCH (PARTE 1)”

Luis | julio 21, 2014 en 12:05 am | Responder

no tienes el codigo hecho en java?

uxmar | octubre 18, 2014 en 7:45 pm | Responder

Hola jariasf,

Un saludo, muchas gracias por el aporte. Acabo de probar el siguiente código: ” Codigo C++:
Algoritmo DFS usando Recursion ”

Todo funciona perfecto con el ejemplo de ingreso que tu propones, mi pregunta es si este algoritmo
funciona para grafos dirigidos?

Pregunto porque aplique la siguiente entrada:

58
15
13

14 de 17 28/1/2020 9:44 p. m.
ALGORITMO DE BÚSQUEDA: DEPTH FIRST SEARCH (PARTE 1) |... [Link]

34
45
32
23
25
53

Nodo raiz: 1
Nodo Final: 5

Y me arroja lo siguiente:
1->5
1->3->4->5
1->2->3->5
1->2->3->5
1->3->5

nota: el nodo 1 con el 2 nunca se comunican y está arrojando una ruta posible de 1->2

Deberia arrojarme lo siguiente:

1->5
1->3->2->5
1->3->2->4->5
1->3->4->5

jariasf | octubre 18, 2014 en 8:44 pm | Responder

Hola, tienes razon, gracias por reportar el error. Las rutas deberian ser:
1->5
1->3->2->5
1->3->4->5
Ya esta arreglado el codigo. El codigo esta para grafos no dirigidos pero comentando una linea se
cambia para grafos dirigidos.

uxmar | octubre 18, 2014 en 9:22 pm | Responder

jariasf gracias a ti por el aporte y por corregir el código.

Te comento que lo volví a probar, lo que no se es si los dos link que tienes con este nombre ” Codigo
C++: Algoritmo DFS usando Recursion ” apuntan a diferentes sitios, probé con el que está a mitad del
post y sigue dando la misma ruta con grafo no dirigido, probé con el que está al final del post y ese
está mucho mejor.

Me muestra la siguiente salida:

1->5
1->3->2->5

15 de 17 28/1/2020 9:44 p. m.
ALGORITMO DE BÚSQUEDA: DEPTH FIRST SEARCH (PARTE 1) |... [Link]

1->3->4->5
1->3->5

Lo cual está perfecto hasta la 4ta linea, ya que la ruta 1->3->5 no debería estar alli, debido a que 3->5
nunca se comunican.

No se si te estará dando este mismo error?

jariasf | octubre 18, 2014 en 9:50 pm | Responder

Como te mencione antes, el código esta sobre grafos no dirigidos por tanto considera 3->5 como
valido, debes comentar la línea que crea una arista adicional(revisa el código). De todas formas acá
tienes el código sobre grafo dirigido y con la salida correcta [Link]

uxmar | octubre 18, 2014 en 9:58 pm |

Ya vi la linea comentada jariasf ! También vi el link que me enviaste.

Muchas gracias por tu ayuda, sigo trabajando en esto…

Voy a intentar pasarlo a java. Un saludo.

Mario Masias Vilca | octubre 23, 2014 en 9:41 pm | Responder

1. Simule el desplazamiento de una hormiga, en un tablero de ajedrez de n x n, la hormiga comienza a

caminar por una de las esquinas de la casilla (1,1). En primer lugar dio un paso adelante, luego uno a
la derecha, luego uno hacia atrás. Después, dio otro a la derecha, dos hacia adelante y dos hacia la
izquierda. Cada vez añadía una nueva fila y una nueva columna a la esquina que estaba explorando.
Por ejemplo, en sus primeros 25 pasos hizo el siguiente recorrido, donde el número de cada casilla
indica el orden en que la visitó:
25 24 23 22 21
10 11 12 13 20
9 8 7 14 19
2 3 6 15 18
1 4 5 16 17

El octavo paso la colocó en la casilla (2,3), mientras que el paso número 20 lo hizo en la (5,4). El
programa consiste en determinar su ubicación en un momento dado.
Entrada:
En la primera línea se indica el número de casos de prueba. Cada caso de prueba se describe en una
línea, en la que se indica el número del paso de la hormiga, n,
donde 1< n < 2. 109
Salida:
Por cada caso de prueba, escribir en una línea los números x e y que identifican la casilla
correspondiente al paso especificado en la entrada, separados por un espacio.
Ejemplo de entrada:
3
8

16 de 17 28/1/2020 9:44 p. m.
ALGORITMO DE BÚSQUEDA: DEPTH FIRST SEARCH (PARTE 1) |... [Link]

20
25
Ejemplo de salida:
22
23
54
15
¿Como podria aplicar DFS para este ejercicio? gracias por su respuesta

jariasf | octubre 23, 2014 en 10:12 pm | Responder

Como el limite maximo es 2×10^9 entonces no es factible usar DFS te daria TLE(Time Limit
Exceeded). Seria mejor que pienses la solucion de forma matematica y halles una formula que
pueda ayudar a mostrar las salidas de manera eficiente.

Mario Masias Vilca | octubre 24, 2014 en 5:25 pm | Responder

ok lo intentare

Asahel | diciembre 22, 2014 en 6:55 pm | Responder

Hola esta muy bien el tutorialpero como podría trasformarlo a java? como represento esta linea en
java vector ady[ MAX ]; ya que si sustituyo esto por un objeto de la clase Vector de java no puedo
acceder de manera bidimencional al array como se hace en C++ entonces como podría representarlo
en java?

17 de 17 28/1/2020 9:44 p. m.