In DFS , i nodi esplorati vengono archiviati in una struttura di dati dello stack. Gli spigoli che ci indirizzano verso nodi inesplorati si chiamano ‘ margini di scoperta ' mentre gli spigoli che portano a nodi già visitati sono chiamati ' bordi del blocco '. DFS è utile negli scenari in cui un programmatore desidera trovare componenti o cicli connessi in un grafico.
Segui le linee guida di questo articolo per l'implementazione DFS in C++.
Implementazione di DFS in C++
Nella sezione seguente, esamineremo come DFS è implementato in C++. Si possono seguire i passaggi indicati per l'implementazione DFS .
- Inserisci il nodo radice di un albero o di un grafico nello stack.
- Aggiungi l'elemento in cima alla pila all'elenco delle visite.
- Scopri tutti i nodi adiacenti al nodo visitato e aggiungi quei nodi che non hanno ancora visitato lo stack.
- Ripetere i passaggi 2 e 3 finché la pila non è vuota.
Pseudocodice DFS
IL DFS lo pseudocodice è mostrato di seguito. Nel Calore() funzione, eseguiamo il nostro DFS funzione su ciascun nodo. Poiché il grafico può avere due parti disconnesse, possiamo eseguire il DFS algoritmo su ogni nodo per assicurarci di aver coperto ogni vertice.
DFS ( g.a )
UN. visitato = VERO
per ogni b ∈ g. agg [ UN ]
Se B. visitato == falso
DFS ( g, b )
Calore ( )
{
Per ogni a ∈ g
UN. visitato = falso
Per ogni a ∈ g
DFS ( g, a )
}
Qui g, a e b rappresentano rispettivamente il grafico, il primo nodo visitato e il nodo nello stack.
Implementazione di DFS in C++
Un programma C++ per DFS l'implementazione è riportata di seguito:
#include
#include
#include
utilizzando spazio dei nomi standard ;
modello < nometipo T >
classe DepthFirstSearch
{
privato :
carta geografica < t,elenco < T > > adjList ;
pubblico :
DepthFirstSearch ( ) { }
vuoto Aggiungi_bordo ( t un, t b, bool Voi = VERO )
{
adjList [ UN ] . respingere ( B ) ;
Se ( Voi )
{
adjList [ B ] . respingere ( UN ) ;
}
}
vuoto Stampa ( )
{
per ( auto io : adjList ) {
cout << io. Primo << '->' ;
per ( ingresso t : io. secondo ) {
cout << iscrizione << ',' ;
}
cout << finel ;
}
}
vuoto dfs_helper ( t nodo,mappa < T, bool > & visitato ) {
visitato [ nodo ] = VERO ;
cout << nodo << ' ' << finel ;
per ( vicino di casa : adjList [ nodo ] ) {
Se ( ! visitato [ vicino ] ) {
dfs_helper ( vicino, visitato ) ;
}
}
}
vuoto DFS ( t src )
{
carta geografica < T, bool > visitato ;
dfs_helper ( src,visitato ) ;
}
} ;
int principale ( ) {
DepthFirstSearch < int > G ;
G. Aggiungi_bordo ( 0 , 5 ) ;
G. Aggiungi_bordo ( 0 , 7 ) ;
G. Aggiungi_bordo ( 4 , 7 ) ;
G. Aggiungi_bordo ( 7 , 8 ) ;
G. Aggiungi_bordo ( 2 , 1 ) ;
G. Aggiungi_bordo ( 0 , 6 ) ;
G. Aggiungi_bordo ( 2 , 4 ) ;
G. Aggiungi_bordo ( 3 , 2 ) ;
G. Aggiungi_bordo ( 3 , 6 ) ;
G. Aggiungi_bordo ( 7 , 5 ) ;
G. Aggiungi_bordo ( 5 , 8 ) ;
G. Stampa ( ) ;
G. DFS ( 6 ) ;
cout << finel ;
}
In questo codice, abbiamo implementato DFS algoritmo che segue lo pseudo codice sopra indicato. Abbiamo 12 coppie di nodi. Abbiamo definito una classe “ G ” che rappresenta un grafico con vertici a e b che rappresentano nodi visitati e non visitati.
Produzione
Conclusione
DFS è un popolare algoritmo di ricerca utile per diversi scenari, come trovare i cicli in un grafico e ottenere informazioni sui componenti connessi o su tutti i vertici in un grafico. Abbiamo anche descritto il funzionamento del DFS metodo con un esempio. DFS impiega pile per eseguire la tecnica e può essere utilizzato anche sugli alberi.