DFS (Depth First Traversal) nella struttura dei dati: cos'è, ordini e applicazioni

Significato di DFS nella struttura dei dati

DFS in Data Structure, noto anche come depth-first traversal, è un algoritmo ricorsivo utilizzato principalmente per cercare tutti i vertici di un grafico o di una struttura dati ad albero. Traversal è la visita di ogni nodo di un grafo. L'algoritmo inizia dal nodo radice (che può essere un nodo arbitrario come il nodo radice in un grafico) e si spinge il più lontano possibile lungo ogni ramo prima di tornare indietro.

L'idea è di iniziare dalla radice o dal nodo arbitrario e mantenere il nodo contrassegnato. Successivamente, è necessario spostarsi sul nodo adiacente non contrassegnato e continuare questo ciclo fino a quando non ci sono nodi adiacenti non contrassegnati. Quindi tornare indietro ed esaminare gli altri nodi che non sono contrassegnati e attraversarli. Il passaggio finale è stampare i nodi all'interno del percorso.

Algoritmo

Formulare una funzione ricorsiva che prenderà l'indice del nodo e un array visitato.

1. Mantieni il nodo corrente contrassegnato come visitato e quindi stampalo.
2. Attraversa tutte le note adiacenti e quelle non contrassegnate e chiama la funzione ricorsiva con l'indice del nodo adiacente.

Esplora i nostri corsi di ingegneria del software popolari

Proprietà

L'analisi del tempo e dello spazio nel DFS in Data Structure varia a seconda della sua area di applicazione. Teoricamente, DFS viene utilizzato principalmente per attraversare un grafo completo e richiede tempo O(|V|+|E|) dove |V| rappresenta il numero di vertici e |E| rappresenta il numero di bordi. Questo grafico è lineare.

In queste applicazioni, lo spazio O(|V|) viene utilizzato anche come ultima risorsa per mantenere lo stack di vertici archiviato nel percorso di ricerca e l'insieme di vertici che sono già visitati. Pertanto, l'impostazione dei limiti di tempo e spazio è simile alla ricerca in ampiezza. Qui, i due algoritmi utilizzati sono meno dipendenti dalla loro complessità e più dalle varie caratteristiche degli ordini di vertici prodotti dai due algoritmi.

Quando si tratta di applicazioni di DFS in Data Structure relative a domini specifici, come la ricerca di soluzioni nel web-crawling o nell'IA, il grafico che richiede l'attraversamento potrebbe essere troppo consistente per essere visitato nella sua totalità. In questi casi, la ricerca viene eseguita solo a una profondità limitata; a causa di risorse limitate, come spazio su disco o memoria. Le strutture dati in genere non vengono utilizzate per tenere traccia dell'insieme di tutti i vertici visitati in precedenza. Una ricerca eseguita a una profondità ristretta rende ancora lineare il tempo quando si tratta dell'unità di spigoli e vertici espansi.

Tuttavia, ricorda che questo numero non ha la stessa dimensione dell'intero grafico poiché alcuni vertici possono essere cercati più volte e altri non cercati.

In tali casi, DFS si rivolge anche a metodi euristici per selezionare un ramo più promettente. Infine, quando non è possibile determinare il limite di profondità appropriato, a priori, la DFS di approfondimento iterativo viene applicata ripetutamente tramite una sequenza di limiti crescenti.

Impara i corsi di sviluppo software online dalle migliori università del mondo. Guadagna programmi Executive PG, programmi di certificazione avanzati o programmi di master per accelerare la tua carriera.

Algoritmo di ricerca in profondità

Ciascun vertice di un grafo in un'implementazione DFS standard è suddiviso in due categorie:

1. Non Visitato
2. Visitato

L'algoritmo viene utilizzato per individuare ogni vertice e contrassegnarlo come visitato e allo stesso tempo evitare i cicli.

Ecco come funziona l'algoritmo DFS:

1. Metti qualsiasi vertice particolare del grafico su una pila.
2. L'elemento in cima alla pila dovrebbe essere aggiunto all'elenco visitato.
3. Crea un elenco di nodi adiacenti di quel vertice e aggiungi quelli non nell'elenco visitato in cima allo stack.
4. Continua a ripetere i passaggi precedenti finché lo stack non si svuota.

Ordinazione DFS

Ordinamenti dei vertici: ci sono quattro modi per ordinare linearmente i vertici di un grafo o di un albero in DFS:

1. L'elenco dei vertici disposti come sono stati visitati per primi dall'algoritmo DFS è noto come preordine. È un modo conciso per descrivere l'andamento della ricerca.
2. L'elenco dei vertici nell'ordine in cui sono stati visitati per ultimi dall'algoritmo è noto come post-ordinamento.
3. L'elenco dei vertici nell'ordine opposto alla loro prima visita è un preordine inverso. Pertanto, non deve essere confuso con l'ordine successivo.
4. L'elenco dei vertici nell'ordine opposto alla loro ultima visita è un post-ordinamento inverso. Non deve essere confuso con il preordine.

Inoltre, esiste un ordinamento in ordine e un ordinamento inverso per gli alberi binari.

Profondità prima ricerca o DFS per un grafico

Il DFS per un grafico è quasi lo stesso del DFS per un albero. L'unica differenza è che i grafici possono avere dei cicli, a differenza degli alberi. Un nodo potrebbe essere visitato più volte e per evitare di elaborare il nodo, viene utilizzato un array booleano visitato.

Output di una prima ricerca in profondità

La ricerca in profondità è più facilmente rappresentata in termini di un albero di copertura dei vertici che sono già stati raggiunti nella ricerca. Sulla base di questo spanning tree, gli archi originali del grafo sono divisi in tre classi: gli spigoli anteriori in cui il nodo dell'albero è puntato verso uno dei suoi discendenti, gli spigoli posteriori in cui il nodo è puntato verso uno dei suoi antenati e gli spigoli trasversali , che non svolge nessuna delle funzioni precedenti.

Applicazioni di profondità prima traversata (DFS)

La ricerca in profondità viene utilizzata nei seguenti algoritmi come elemento costitutivo:

• Ricerca di componenti collegati.
• Trovare componenti collegati a 2 (vertice o spigolo).
• Trovare i ponti del grafico.
• Trovare componenti collegati a 3 (vertice o spigolo).
• Ordinamento topologico.
• Trovare componenti fortemente connessi.
• Scoprire se una specie è simile all'una o all'altra specie in un albero filogenetico.
• Test di planarità.
• Produrre parole per determinare il limite impostato di qualsiasi gruppo.
• Risolvere enigmi che hanno una sola soluzione, come i labirinti.
• Generazione di labirinti .
• Ricerca della bi-connettività nei grafici.

Pseudocodice DFS e implementazione in Python

La funzione init() viene eseguita su ogni nodo nello pseudocodice sottostante per garantire che tutti i vertici siano visitati. Ciò è particolarmente importante poiché i grafici potrebbero avere varie aree disconnesse.

Ecco lo pseudocodice:

DFS(G, u)

u.visited = vero

per ogni v ∈ G.Adj[u]

se v.visited == falso

DFS(G,v)

dentro() {

Per ogni u ∈ G

u.visited = falso

Per ogni u ∈ G

DFS(G, u)

}

Ecco l'implementazione DFS in Python:

grafico = {

'5' : ['3','7'],

'2' : ['1', '3'],

'6' : ['7'],

'3' : [],

'4' : ['6'],

'7' : []

}

visitato = set()

def dfs(visited, graph, node):

se il nodo non è visitato:

stampa (nodo)

visitato.add(nodo)

for neighbor in graph[node]:

dfs(visitato, grafico, vicino)

print("Questo è il DFS:")

dfs(visitato, grafico, '5')

Produzione:

Questo è il DFS: 5

Esplora i nostri corsi di ingegneria del software popolari

La complessità della ricerca in profondità

John Reif ha esplorato la complessità computazionale di Depth First Search. Per essere precisi, in un grafico, il fatto dato è G, sia O l'ordine standard determinato dall'algoritmo DFS ripetitivo. G rappresenta il grafico e O rappresenta l'output di ordinamento dell'algoritmo DFS ridondante. Questo output è noto come ordinamento DFS lessicografico.

Conclusione

L'obiettivo principale dell'algoritmo DFS è visitare ogni singolo vertice che evita i cicli nei grafici di destinazione. Se desideri essere coinvolto con implementazioni avanzate di operazioni di ricerca o operazioni di ordinazione, dovresti assolutamente considerare di seguire un corso olistico e premium in Depth First Search e Data Structure.

upGrad ha alcuni corsi DFS di alto livello come Master of Science in Computer Science e Specializzazione in Big Data .

Se stai lottando per fare il tuo prossimo passo e stai cercando un consiglio di esperti, upGrad Mentorship cerca di fornirti sessioni individuali con i migliori consulenti di carriera ed esperti del settore.