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 .