Github
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
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
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
3
4
5
6
7
8
| ...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:
1
2
3
4
5
6
7
8
9
| void dfs( int u ){ visitado[ u ] = true; visitado_componente[ u ] = true; for( int v = 0 ; v < ady[ u ].size(); ++v ){ if( !visitado[ ady[ u ][ v ] ] ){ dfs( ady[ u ][ v ] ); } }} |
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
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
Terminamos la función de DFS partiendo del vértice 1. Ahora volvemos al for inicial e incrementamos las componentes.
1
2
3
4
5
6
| ...if( !visitado[ i ] ){ dfs( i ); total++; //incrementamos numero de componentes}... |
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
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
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.
No hay comentarios.:
Publicar un comentario