Programacion

ALGORITMO DE BÚSQUEDA: DEPTH FIRST SEARCH

Posted: March 5, 2011 by codebreakerscorp in Algoritmos
2
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 espara 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[pic]
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 verlos 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
5mientras 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 elsiguiente grafo no dirigido:
[pic]
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 lalista 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...