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:
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 ).
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
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.
1 método DFS( origen):2 marcamos origen como visitado3 para cada vertice v adyacente a origen en el Grafo:4 si v no ah sido visitado:5 marcamos como visitado v6 llamamos recursivamente DFS( v )
Tomemos como ejemplo el siguiente grafo no dirigido:
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:
void dfs( int u ){ //domino origentotal++; //aumento en mi respuesta la caida de un dominovisitado[ u ] = true; //domino "u" cayofor( 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 evaluardfs( ady[ u ][ v ] ); //recursivamente veo que dominos caeran a partir del adyacente de "u"}}}
Componentes Conexas
for( int i = 1 ; i <= V ; ++i ){ //recorremos todos los posibles verticesif( !visitado[ i ] ){ //si alguno no fue visitado tenemos una componente a partir de ese nododfs( i ); //recorremos a partir de nodo i todo el grafo que se formatotal++; //incrementamos cantidad de componentes}}
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 ] );}}}
