Depth first Search o Depth first traversal è un algoritmo ricorsivo per la ricerca di tutti i vertici di un grafico o struttura dati ad albero. Traversal significa visitare tutti i nodi di un grafico.
Depth First Search Algorithm
Un’implementazione DFS standard mette ogni vertice del grafico in una delle due categorie:
- Visited
- Not Visited
Lo scopo dell’algoritmo è contrassegnare ogni vertice come visitato evitando i cicli.,
L’algoritmo DFS funziona come segue:
- Inizia mettendo uno qualsiasi dei vertici del grafico in cima a uno stack.
- Prendi l’elemento superiore dello stack e aggiungilo all’elenco visitato.
- Crea un elenco dei nodi adiacenti di quel vertice. Aggiungi quelli che non sono nell’elenco visitato in cima allo stack.
- Continua a ripetere i passaggi 2 e 3 fino a quando lo stack non è vuoto.
Depth First Search Example
Vediamo come funziona l’algoritmo di ricerca Depth First con un esempio. Usiamo un grafico non orientato con 5 vertici.,
partiamo dal vertice 0, l’algoritmo DFS comincia mettendo in Visitata elenco e mettendo tutti i suoi vertici adiacenti nello stack.
Successivamente, visitiamo l’elemento nella parte superiore dello stack cioè 1 e andiamo ai suoi nodi adiacenti. Dal momento che 0 è già stato visitato, visitiamo 2 invece.,
Vertex 2 è un non visitati adiacente vertice in 4, quindi aggiungiamo che per la cima dello stack e la visita.
Dopo aver visitato l’ultimo elemento 3, non ha nodi adiacenti non visitati, quindi abbiamo completato la prima traversata di profondità del grafico.,
DFS Pseudocodice (implementazione ricorsiva)
Lo pseudocodice per DFS è mostrato di seguito. Nella funzione init (), si noti che eseguiamo la funzione DFS su ogni nodo. Questo perché il grafico potrebbe avere due diverse parti disconnesse, quindi per assicurarci di coprire ogni vertice, possiamo anche eseguire l’algoritmo DFS su ogni nodo.,
DFS(G, u) u.visited = true for each v ∈ G.Adj if v.visited == false DFS(G,v) init() { For each u ∈ G u.visited = false For each u ∈ G DFS(G, u)}
Implementazione DFS in Python, Java e C/C++
Il codice per l’algoritmo di ricerca Depth First con un esempio è mostrato di seguito. Il codice è stato semplificato in modo che possiamo concentrarci sull’algoritmo piuttosto che su altri dettagli.
la Complessità di Profondità Prima Ricerca
La complessità temporale dell’algoritmo DFS è rappresentato in forma di O(V + E), dove V è il numero di nodi e di E è il numero di spigoli.
La complessità dello spazio dell’algoritmo è O(V).,
Applicazione dell’algoritmo DFS
- Per trovare il percorso
- Per verificare se il grafico è bipartito
- Per trovare i componenti fortemente connessi di un grafico
- Per rilevare cicli in un grafico