Estructura de datos: primer recorrido en profundidad
El algoritmo Depth First Search (DFS) atraviesa un gráfico en un movimiento de profundidad y utiliza una pila para recordar obtener el siguiente vértice para iniciar una búsqueda, cuando se produce un callejón sin salida en cualquier iteración.
Como en el ejemplo anterior, el algoritmo DFS atraviesa de S a A a D a G a E a B primero, luego a F y finalmente a C. Emplea las siguientes reglas.
Rule 1- Visite el vértice adyacente no visitado. Márcalo como visitado. Muéstralo. Empújelo en una pila.
Rule 2- Si no se encuentra ningún vértice adyacente, muestre un vértice de la pila. (Aparecerán todos los vértices de la pila, que no tienen vértices adyacentes).
Rule 3 - Repita la Regla 1 y la Regla 2 hasta que la pila esté vacía.
| Paso | El recorrido | Descripción |
|---|---|---|
| 1 |  |
Inicializa la pila. |
| 2 |  |
marca Scomo visitado y ponerlo en la pila. Explore cualquier nodo adyacente no visitado deS. Tenemos tres nodos y podemos elegir cualquiera de ellos. Para este ejemplo, tomaremos el nodo en orden alfabético. |
| 3 |  |
marca Acomo visitado y ponerlo en la pila. Explore cualquier nodo adyacente no visitado de A. AmbosS y D son adyacentes a A pero solo nos preocupan los nodos no visitados. |
| 4 |  |
Visitar Dy marcarlo como visitado y ponerlo en la pila. Aquí tenemosB y C nodos, que son adyacentes a Dy ambos están sin visitar. Sin embargo, elegiremos nuevamente en orden alfabético. |
| 5 |  |
Nosotros elegimos B, márquelo como visitado y colóquelo en la pila. aquíBno tiene ningún nodo adyacente no visitado. Entonces, hacemos estallarB de la pila. |
| 6 |  |
Verificamos la parte superior de la pila para regresar al nodo anterior y verificamos si tiene nodos no visitados. Aquí encontramosD estar en la parte superior de la pila. |
| 7 |  |
Solo el nodo adyacente no visitado es de D es Cahora. Entonces visitamosC, márquelo como visitado y colóquelo en la pila. |
Como Cno tiene ningún nodo adyacente no visitado, por lo que seguimos haciendo estallar la pila hasta que encontramos un nodo que tiene un nodo adyacente no visitado. En este caso, no hay ninguno y seguimos apareciendo hasta que la pila está vacía.
Para conocer la implementación de este algoritmo en lenguaje de programación C, haga clic aquí .