Ban ben DFS , a feltárt csomópontok verem adatstruktúrában vannak tárolva. Azokat az éleket, amelyek a feltáratlan csomópontokhoz irányítanak, az úgynevezett ' felfedezési élek 'míg a már meglátogatott csomópontokhoz vezető éleket' blokk élei '. DFS hasznos olyan forgatókönyvekben, amikor a programozó egy grafikonon szeretne összekapcsolt komponenseket vagy ciklusokat találni.
Kövesse ennek a cikknek az irányelveit a megvalósításhoz DFS C++ nyelven.
DFS megvalósítása C++ nyelven
A következő részben megvizsgáljuk, hogyan DFS C++ nyelven van megvalósítva. A megvalósításhoz a megadott lépéseket lehet követni DFS .
- Illessze be egy fa vagy gráf gyökércsomópontját a verembe.
- Adja hozzá a verem legfelső elemét a látogatott listához.
- Fedezze fel az összes szomszédos csomópontot a meglátogatott csomóponthoz, és adja hozzá azokat a csomópontokat, amelyek még nem látogatták meg a veremet.
- Ismételje meg a 2. és 3. lépést, amíg a köteg ki nem ürül.
DFS pszeudokód
A DFS pszeudokód lent látható. Ban,-ben hőség() függvényt hajtjuk végre DFS funkciót minden csomóponton. Mivel a gráfnak két szétválasztott része lehet, futtathatjuk a DFS algoritmust minden csomóponton, hogy biztosítsuk, hogy minden csúcsot lefedtünk.
DFS ( g a )
a. meglátogatta = igaz
számára minden b ∈ g. Adj [ a ]
ha b. meglátogatta == hamis
DFS ( g,b )
hőség ( )
{
Minden a ∈ g-re
a. meglátogatta = hamis
Minden a ∈ g-re
DFS ( g, a )
}
Itt g, a és b jelenti a gráfot, az elsőként meglátogatott csomópontot és a csomópontot a veremben.
DFS megvalósítása C++ nyelven
C++ program ehhez DFS a megvalósítást az alábbiakban mutatjuk be:
#include
#include
#include
segítségével névtér std ;
sablon < típusnév t >
osztály DepthFirstSearch
{
magán :
térkép < t, lista < t > > adjList ;
nyilvános :
DepthFirstSearch ( ) { }
üres Add_edge ( t a, t b, bool te = igaz )
{
adjList [ a ] . visszavet ( b ) ;
ha ( te )
{
adjList [ b ] . visszavet ( a ) ;
}
}
üres Nyomtatás ( )
{
számára ( auto én : adjList ) {
cout << én. első << '->' ;
számára ( t belépés : én. második ) {
cout << belépés << ',' ;
}
cout << endl ;
}
}
üres dfs_helper ( t csomópont,térkép < t, bool > & meglátogatta ) {
meglátogatta [ csomópont ] = igaz ;
cout << csomópont << ' ' << endl ;
számára ( t szomszéd : adjList [ csomópont ] ) {
ha ( ! meglátogatta [ szomszéd ] ) {
dfs_helper ( szomszéd, meglátogatta ) ;
}
}
}
üres DFS ( t src )
{
térkép < t, bool > meglátogatta ;
dfs_helper ( src, látogatott ) ;
}
} ;
int fő- ( ) {
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. Nyomtatás ( ) ;
g. DFS ( 6 ) ;
cout << endl ;
}
Ebben a kódban valósítottuk meg DFS algoritmus követi a fent megadott pszeudo kódot. 12 pár csomópontunk van. Meghatároztunk egy osztályt ' G ”, amely egy olyan gráfot jelöl, amelynek a és b csúcsai meglátogatott és nem látogatott csomópontokat képviselnek.
Kimenet
Következtetés
DFS egy népszerű keresőalgoritmus, amely számos forgatókönyv esetén hasznos, például a ciklusok megkereséséhez egy gráfban, és információk megszerzéséhez a kapcsolódó összetevőkről vagy a gráf összes csúcsáról. Leírtuk a működését is DFS módszer egy példával. DFS veremeket alkalmaz a technika végrehajtásához, és fákon is használható.