notri DFS , so vozlišča, ki jih raziskujete, shranjena v podatkovni strukturi sklada. Robovi, ki nas usmerjajo do neraziskanih vozlišč, se imenujejo robovi odkrivanja ' medtem ko se robovi, ki vodijo že obiskana vozlišča, imenujejo ' robovi blokov '. DFS je uporaben v scenarijih, ko želi programer najti povezane komponente ali cikle v grafu.
Za izvedbo upoštevajte smernice tega članka DFS v C++.
Implementacija DFS v C++
V naslednjem razdelku bomo preučili, kako DFS je implementiran v C++. Za izvedbo lahko sledite podanim korakom DFS .
- Vstavite korensko vozlišče drevesa ali grafa v sklad.
- Dodajte najvišji element sklada na seznam obiskanih.
- Odkrijte vsa sosednja vozlišča k obiskanemu vozlišču in dodajte tista vozlišča, ki še niso obiskala sklada.
- Ponavljajte 2. in 3. korak, dokler sveženj ni prazen.
Psevdokoda DFS
The DFS psevdokoda je prikazana spodaj. V toplota () funkcijo, izvajamo svojo DFS funkcijo na vsakem vozlišču. Ker ima graf lahko dva nepovezana dela, lahko izvedemo DFS algoritem na vsakem vozlišču, da zagotovimo, da smo pokrili vsako točko.
DFS ( g a )
a. obiskal = prav
za vsak b ∈ g. prilag [ a ]
če b. obiskal == lažno
DFS ( g, b )
toplota ( )
{
Za vsak a ∈ g
a. obiskal = lažno
Za vsak a ∈ g
DFS ( g, a )
}
Tu g, a in b predstavljajo graf, prvo obiskano vozlišče oziroma vozlišče v skladu.
Implementacija DFS v C++
Program C++ za DFS izvedba je podana spodaj:
#include
#include
#include
uporabo imenski prostor std ;
predlogo < ime tipa t >
razred DepthFirstSearch
{
zasebno :
zemljevid < t, seznam < t > > adjList ;
javnosti :
DepthFirstSearch ( ) { }
praznina Add_edge ( t a, t b, bool ti = prav )
{
adjList [ a ] . porini nazaj ( b ) ;
če ( ti )
{
adjList [ b ] . porini nazaj ( a ) ;
}
}
praznina Tiskanje ( )
{
za ( avto jaz : adjList ) {
cout << jaz. prvi << '->' ;
za ( t vstop : jaz. drugo ) {
cout << vstop << ',' ;
}
cout << konec ;
}
}
praznina dfs_helper ( t vozlišče, zemljevid < t, bool > & obiskal ) {
obiskal [ vozlišče ] = prav ;
cout << vozlišče << ' ' << konec ;
za ( t sosed : adjList [ vozlišče ] ) {
če ( ! obiskal [ sosed ] ) {
dfs_helper ( sosed, obiskal ) ;
}
}
}
praznina DFS ( t src )
{
zemljevid < t, bool > obiskal ;
dfs_helper ( src, obiskano ) ;
}
} ;
int glavni ( ) {
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. Tiskanje ( ) ;
g. DFS ( 6 ) ;
cout << konec ;
}
V tej kodi smo implementirali DFS algoritem, ki sledi zgornji psevdo kodi. Imamo 12 parov vozlišč. Definirali smo razred ' G ”, ki predstavlja graf z vozliščema a in b, ki predstavljata obiskana in neobiskana vozlišča.
Izhod
Zaključek
DFS je priljubljen iskalni algoritem, uporaben za več scenarijev, kot je iskanje ciklov v grafu in pridobivanje informacij o povezanih komponentah ali vseh vozliščih v grafu. Opisali smo tudi delovanje DFS metoda s primerom. DFS uporablja nize za izvajanje tehnike in se lahko uporablja tudi na drevesih.