Sisään DFS , tutkittavat solmut tallennetaan pinotietorakenteeseen. Reunoja, jotka ohjaavat meidät tutkimattomiin solmuihin, kutsutaan ' löydön reunat 'kun taas reunoja, jotka johtavat jo vierailtuihin solmuihin, kutsutaan' lohkon reunat '. DFS on hyödyllinen skenaarioissa, joissa ohjelmoija haluaa löytää yhdistetyt komponentit tai syklit kaaviosta.
Käytä tämän artikkelin ohjeita DFS C++:ssa.
DFS:n käyttöönotto C++:ssa
Seuraavassa osiossa käymme läpi kuinka DFS on toteutettu C++:ssa. Voidaan noudattaa annettuja vaiheita toteuttaakseen DFS .
- Lisää pinoon puun tai graafin juurisolmu.
- Lisää pinon ylin kohde vierailijoiden luetteloon.
- Etsi kaikki vieraillun solmun viereiset solmut ja lisää ne solmut, jotka eivät ole vielä käyneet pinossa.
- Toista vaiheita 2 ja 3, kunnes pino on tyhjä.
DFS-pseudokoodi
The DFS pseudokoodi näkyy alla. Vuonna lämpö() toiminnon, suoritamme omamme DFS toiminto jokaisessa solmussa. Koska kaaviossa voi olla kaksi erillistä osaa, voimme ajaa DFS Algoritmi jokaisessa solmussa varmistaaksemme, että olemme kattaneet jokaisen kärjen.
DFS ( g a )
a. vieraili = totta
varten jokainen b ∈ g. Adj [ a ]
jos b. vieraili == väärä
DFS ( g,b )
lämpöä ( )
{
Jokaista a ∈ g kohden
a. vieraili = väärä
Jokaista a ∈ g kohden
DFS ( g, a )
}
Tässä g, a ja b edustavat kuvaajaa, ensimmäisenä vierailtua solmua ja pinon solmua.
DFS:n käyttöönotto C++:ssa
C++-ohjelma DFS toteutus on esitetty alla:
#include
#sisällytä
#sisällytä
käyttämällä nimiavaruus std ;
sapluuna < tyypin nimi t >
luokkaa DepthFirstSearch
{
yksityinen :
kartta < t, lista < t > > adjList ;
julkinen :
DepthFirstSearch ( ) { }
mitätön Add_edge ( t a, t b, bool sinä = totta )
{
adjList [ a ] . työnnä takaisin ( b ) ;
jos ( sinä )
{
adjList [ b ] . työnnä takaisin ( a ) ;
}
}
mitätön Tulosta ( )
{
varten ( auto i : adjList ) {
cout << i. ensimmäinen << '->' ;
varten ( t sisäänkäynti : i. toinen ) {
cout << sisääntulo << ',' ;
}
cout << endl ;
}
}
mitätön dfs_helper ( t solmu, kartta < t, bool > & vieraili ) {
vieraili [ solmu ] = totta ;
cout << solmu << ' ' << endl ;
varten ( t naapuri : adjList [ solmu ] ) {
jos ( ! vieraili [ naapuri ] ) {
dfs_helper ( naapuri, vieraili ) ;
}
}
}
mitätön DFS ( t src )
{
kartta < t, bool > vieraili ;
dfs_helper ( src,vieraillut ) ;
}
} ;
int pää ( ) {
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. Tulosta ( ) ;
g. DFS ( 6 ) ;
cout << endl ;
}
Tässä koodissa olemme toteuttaneet DFS algoritmi noudattaa yllä annettua pseudokoodia. Meillä on 12 paria solmuja. Määritimme luokan ' G ', joka edustaa graafia, jonka kärjet a ja b edustavat vierailtuja ja vierailemattomia solmuja.
Lähtö
Johtopäätös
DFS on suosittu hakualgoritmi, joka on hyödyllinen useissa skenaarioissa, kuten kaavion syklien etsimisessä ja tiedon saamisessa liitetyistä komponenteista tai kaikista graafin pisteistä. Kuvasimme myös sen toimintaa DFS menetelmä esimerkin kanssa. DFS käyttää pinoja tekniikan suorittamiseen ja sitä voidaan käyttää myös puissa.