En DFS , els nodes que s'estan explorant s'emmagatzemen en una estructura de dades de pila. Les vores que ens dirigeixen cap a nodes inexplorats s'anomenen ' vores de descobriment ' mentre que les vores que conduiran als nodes ja visitats s'anomenen ' vores del bloc ‘. DFS és útil en escenaris en què un programador vol trobar components connectats o cicles en un gràfic.
Seguiu les directrius d'aquest article per implementar-les DFS en C++.
Implementació de DFS en C++
A la secció següent, explicarem com DFS està implementat en C++. Es poden seguir els passos indicats per implementar DFS .
- Inseriu el node arrel d'un arbre o gràfic a la pila.
- Afegiu l'element superior de la pila a la vostra llista visitada.
- Descobriu tots els nodes adjacents al node visitat i afegiu aquells nodes que encara no hagin visitat la pila.
- Repetiu els passos 2 i 3 fins que la pila estigui buida.
Pseudocodi DFS
El DFS el pseudocodi es mostra a continuació. En el calor () funció, executem la nostra DFS funció a cada node. Com que el gràfic pot tenir dues parts desconnectades, podem executar el DFS algorisme a cada node per assegurar-nos que hem cobert cada vèrtex.
DFS ( g a )
a. visitat = veritat
per cada b ∈ g. Adj [ a ]
si b. visitat == fals
DFS ( g,b )
calor ( )
{
Per cada a ∈ g
a. visitat = fals
Per cada a ∈ g
DFS ( g, a )
}
Aquí g, a i b representen el gràfic, el primer node visitat i el node de la pila respectivament.
Implementació de DFS en C++
Un programa C++ per DFS la implementació es detalla a continuació:
#include
#inclou
#include
utilitzant espai de noms std ;
plantilla < nom del tipus t >
classe DepthFirstSearch
{
privat :
mapa < t, llista < t > > adjList ;
públic :
DepthFirstSearch ( ) { }
buit Add_edge ( t a, t b, bool vostè = veritat )
{
adjList [ a ] . fer retrocedir ( b ) ;
si ( vostè )
{
adjList [ b ] . fer retrocedir ( a ) ;
}
}
buit Imprimir ( )
{
per ( automàtic i : adjList ) {
cout << i. primer << '->' ;
per ( t entrada : i. segon ) {
cout << entrada << ',' ;
}
cout << endl ;
}
}
buit dfs_helper ( t node, mapa < t, bool > & visitat ) {
visitat [ node ] = veritat ;
cout << node << ' ' << endl ;
per ( t veí : adjList [ node ] ) {
si ( ! visitat [ veí ] ) {
dfs_helper ( veí, visitat ) ;
}
}
}
buit DFS ( t src )
{
mapa < t, bool > visitat ;
dfs_helper ( src, visitat ) ;
}
} ;
int principal ( ) {
DepthFirstSearch < int > g ;
g. Add_edge ( 0 , 5 ) ;
g. Add_edge ( 0 , 7 ) ;
g. Add_edge ( 4 , 7 ) ;
g. Add_edge ( 7 , 8 ) ;
g. Add_edge ( 2 , 1 ) ;
g. Add_edge ( 0 , 6 ) ;
g. Add_edge ( 2 , 4 ) ;
g. Add_edge ( 3 , 2 ) ;
g. Add_edge ( 3 , 6 ) ;
g. Add_edge ( 7 , 5 ) ;
g. Add_edge ( 5 , 8 ) ;
g. Imprimir ( ) ;
g. DFS ( 6 ) ;
cout << endl ;
}
En aquest codi, hem implementat DFS algorisme seguint el pseudocodi indicat anteriorment. Tenim 12 parells de nodes. Hem definit una classe ' G ” que representa un gràfic que té els vèrtexs a i b que representen nodes visitats i no visitats.
Sortida
Conclusió
DFS és un algorisme de cerca popular útil per a diversos escenaris, com ara trobar els cicles en un gràfic i obtenir informació sobre els components connectats o tots els vèrtexs d'un gràfic. També vam descriure el funcionament del DFS mètode amb un exemple. DFS utilitza piles per executar la tècnica i també es pot utilitzar en arbres.