Struttura dati - Profondità primo attraversamento
L'algoritmo Depth First Search (DFS) attraversa un grafico con un movimento in profondità e utilizza uno stack per ricordare di ottenere il vertice successivo per avviare una ricerca, quando si verifica un vicolo cieco in qualsiasi iterazione.
Come nell'esempio sopra, l'algoritmo DFS passa da S ad A a D da G a E a B prima, poi a F e infine a C. Impiega le seguenti regole.
Rule 1- Visita il vertice adiacente non visitato. Contrassegnalo come visitato. Mostralo. Mettilo in una pila.
Rule 2- Se non viene trovato alcun vertice adiacente, fai apparire un vertice dalla pila. (Apparirà tutti i vertici dalla pila, che non hanno vertici adiacenti.)
Rule 3 - Ripeti la regola 1 e la regola 2 fino a quando la pila è vuota.
| Passo | Traversal | Descrizione |
|---|---|---|
| 1 |  |
Inizializza lo stack. |
| 2 |  |
marchio Scome visitato e metterlo nella pila. Esplora qualsiasi nodo adiacente non visitato daS. Abbiamo tre nodi e possiamo sceglierne uno qualsiasi. Per questo esempio, prenderemo il nodo in ordine alfabetico. |
| 3 |  |
marchio Acome visitato e metterlo nella pila. Esplora qualsiasi nodo adiacente non visitato da A. EntrambiS e D sono adiacenti a A ma siamo interessati solo ai nodi non visitati. |
| 4 |  |
Visitare De contrassegnalo come visitato e mettilo nella pila. Ecco, abbiamoB e C nodi, che sono adiacenti a Ded entrambi non sono visitati. Tuttavia, sceglieremo nuovamente in ordine alfabetico. |
| 5 |  |
Noi scegliamo B, contrassegnalo come visitato e mettilo in pila. QuiBnon ha alcun nodo adiacente non visitato. Quindi, facciamo scoppiareB dalla pila. |
| 6 |  |
Controlliamo lo stack in alto per tornare al nodo precedente e controlliamo se ha nodi non visitati. Qui troviamoD essere in cima alla pila. |
| 7 |  |
Solo il nodo adiacente non visitato proviene da D è Cadesso. Quindi visitiamoC, contrassegnalo come visitato e mettilo nella pila. |
Come Cnon ha alcun nodo adiacente non visitato, quindi continuiamo a far scoppiare la pila finché non troviamo un nodo che ha un nodo adiacente non visitato. In questo caso, non ce n'è e continuiamo a saltare finché lo stack non è vuoto.
Per conoscere l'implementazione di questo algoritmo nel linguaggio di programmazione C, fare clic qui .