In DFS , sú skúmané uzly uložené v dátovej štruktúre zásobníka. Hrany, ktoré nás nasmerujú do nepreskúmaných uzlov, sa nazývajú „ objaviteľské hrany „zatiaľ čo hrany budú viesť už navštívené uzly sa nazývajú“ hrany bloku '. DFS je užitočný v scenároch, keď chce programátor nájsť spojené komponenty alebo cykly v grafe.
Pri implementácii postupujte podľa pokynov v tomto článku DFS v C++.
Implementácia DFS v C++
V nasledujúcej časti si prejdeme ako DFS je implementovaný v C++. Pri implementácii je možné postupovať podľa uvedených krokov DFS .
- Vložte koreňový uzol stromu alebo grafu do zásobníka.
- Pridajte najvyššiu položku zásobníka do svojho navštíveného zoznamu.
- Objavte všetky susediace uzly s navštíveným uzlom a pridajte tie uzly, ktoré ešte nenavštívili zásobník.
- Opakujte kroky 2 a 3, kým nebude zásobník prázdny.
Pseudokód DFS
The DFS pseudokód je uvedený nižšie. V teplo() funkciu, vykonáme našu DFS funkciu na každom uzle. Pretože graf môže mať dve oddelené časti, môžeme spustiť DFS algoritmus na každom uzle, aby sme zaistili, že sme pokryli každý vrchol.
DFS ( g a )
a. navštívil = pravda
pre každé b ∈ g. Adj [ a ]
ak b. navštívil == falošný
DFS ( g,b )
teplo ( )
{
Pre každé a ∈ g
a. navštívil = falošný
Pre každé a ∈ g
DFS ( g, a )
}
Tu g, a a b predstavujú graf, prvý navštívený uzol a uzol v zásobníku.
Implementácia DFS v C++
Program v C++ pre DFS implementácia je uvedená nižšie:
#include
#include
#include
použitím menný priestor std ;
šablóna < typový názov t >
trieda DepthFirstSearch
{
súkromné :
mapa < t,zoznam < t > > adjList ;
verejnosti :
DepthFirstSearch ( ) { }
neplatné Add_edge ( t a, t b, bool vy = pravda )
{
adjList [ a ] . push_back ( b ) ;
ak ( vy )
{
adjList [ b ] . push_back ( a ) ;
}
}
neplatné Tlačiť ( )
{
pre ( auto i : adjList ) {
cout << i. najprv << '->' ;
pre ( t vstup : i. druhý ) {
cout << vstup << ',' ;
}
cout << endl ;
}
}
neplatné dfs_helper ( t uzol, mapa < t, bool > & navštívil ) {
navštívil [ uzol ] = pravda ;
cout << uzol << '' << endl ;
pre ( t sused : adjList [ uzol ] ) {
ak ( ! navštívil [ sused ] ) {
dfs_helper ( sused, navštívil ) ;
}
}
}
neplatné DFS ( t src )
{
mapa < t, bool > navštívil ;
dfs_helper ( src,navštívené ) ;
}
} ;
int Hlavná ( ) {
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. Tlačiť ( ) ;
g. DFS ( 6 ) ;
cout << endl ;
}
V tomto kóde sme implementovali DFS algoritmus podľa vyššie uvedeného pseudokódu. Máme 12 párov uzlov. Definovali sme triedu „ G ” čo predstavuje graf s vrcholmi aab, ktoré predstavujú navštívené a nenavštívené uzly.
Výkon
Záver
DFS je populárny vyhľadávací algoritmus užitočný pre niekoľko scenárov, ako je hľadanie cyklov v grafe a získavanie informácií o pripojených komponentoch alebo všetkých vrcholoch v grafe. Opísali sme aj fungovanie DFS metóda s príkladom. DFS využíva na vykonanie tejto techniky stohy a možno ju použiť aj na stromoch.