algorithm
Profondità prima ricerca

Introduzione alla ricerca approfondita

La ricerca di profondità è un algoritmo per attraversare o cercare strutture di dati di alberi o grafici. Uno inizia alla radice ed esplora il più lontano possibile lungo ogni ramo prima di tornare indietro. Una versione della ricerca approfondita è stata studiata nel matematico francese del XIX secolo Charles Pierre Trémaux come strategia per risolvere labirinti.

La ricerca in profondità è un modo sistematico per trovare tutti i vertici raggiungibili da un vertice sorgente. Come per la ricerca in ampiezza, DFS attraversa un componente connesso di un dato grafico e definisce uno spanning tree. L'idea di base della ricerca in profondità è esplorare metodicamente ogni lato. Ricominciamo da un altro vertice, se necessario. Non appena scopriamo un vertice, DFS inizia ad esplorare da esso (a differenza di BFS, che mette un vertice su una coda in modo che esplori da esso in seguito).

Diamo un'occhiata a un esempio. Attraverseremo questo grafico:

Attraverseremo il grafico seguendo queste regole:

• Inizieremo dalla fonte.
• Nessun nodo sarà visitato due volte.
• I nodi che non abbiamo ancora visitato, saranno colorati di bianco.
• Il nodo che abbiamo visitato, ma non ha visitato tutti i suoi nodi figli, sarà colorato in grigio.
• I nodi completamente attraversati saranno colorati di nero.

Diamo un'occhiata passo dopo passo:

Possiamo vedere una parola chiave importante. Questo è backedge . Puoi vedere. 5-1 è chiamato backedge. Questo perché, non abbiamo ancora finito con il nodo 1 , quindi passare da un altro nodo al nodo 1 significa che c'è un ciclo nel grafico. In DFS, se possiamo passare da un nodo grigio a un altro, possiamo essere certi che il grafico abbia un ciclo. Questo è uno dei modi per rilevare il ciclo in un grafico. A seconda del nodo di origine e dell'ordine dei nodi che visitiamo, possiamo scoprire qualsiasi spigolo in un ciclo come backedge . Ad esempio: se siamo andati prima a 5 da 1 , avremmo scoperto 2-1 come backedge.

Il bordo che prendiamo per passare dal nodo grigio al nodo bianco si chiama bordo dell'albero . Se manteniamo solo il bordo dell'albero e ne rimuoviamo gli altri, otterremo un albero DFS .

Nel grafico non orientato, se possiamo visitare un nodo già visitato, questo deve essere un backedge . Ma per i grafici diretti, dobbiamo controllare i colori. Se e solo se possiamo passare da un nodo grigio ad un altro nodo grigio, questo è chiamato backedge .

In DFS, possiamo anche mantenere i timestamp per ciascun nodo, che può essere utilizzato in molti modi (ad es. Ordinamento topologico).

1. Quando un nodo v viene cambiato da bianco a grigio, il tempo viene registrato in d [v] .
2. Quando un nodo v viene cambiato da grigio a nero, il tempo viene registrato in f [v] .

Qui d [] significa tempo di scoperta e f [] significa finire il tempo . Il nostro pesudo-codice sarà simile a:

Procedure DFS(G):
for each node u in V[G]
    color[u] := white
    parent[u] := NULL
end for
time := 0
for each node u in V[G]
    if color[u] == white
        DFS-Visit(u)
    end if
end for

Procedure DFS-Visit(u):
color[u] := gray
time := time + 1
d[u] := time
for each node v adjacent to u
    if color[v] == white
        parent[v] := u
        DFS-Visit(v)
    end if
end for
color[u] := black
time := time + 1
f[u] := time

Complessità:

Ogni nodo e spigolo viene visitato una sola volta. Quindi la complessità di DFS è O (V + E) , dove V indica il numero di nodi ed E indica il numero di spigoli.

Applicazioni di profondità Prima ricerca:

• Trovare tutti i percorsi più corti in un grafico non orientato.
• Rilevazione del ciclo in un grafico.
• Ricerca del percorso
• Ordinamento topologico.
• Verificare se un grafico è bipartito.
• Trovare un componente fortemente connesso.
• Risolvi i puzzle con una soluzione.