Sa DFS , ang mga node na ginalugad ay iniimbak sa isang stack na istraktura ng data. Ang mga gilid na nagdidirekta sa atin sa hindi pa natutuklasang mga node ay tinatawag na ' mga gilid ng pagtuklas 'Habang ang mga gilid na mangunguna sa binisita nang mga node ay tinatawag na' harangan ang mga gilid '. DFS ay kapaki-pakinabang sa mga sitwasyon kapag ang isang programmer ay gustong maghanap ng mga konektadong bahagi o cycle sa isang graph.
Sundin ang mga alituntunin ng artikulong ito para ipatupad DFS sa C++.
Pagpapatupad ng DFS sa C++
Sa susunod na seksyon, tatalakayin natin kung paano DFS ay ipinatupad sa C++. Maaaring sundin ng isa ang mga ibinigay na hakbang upang ipatupad DFS .
- Ipasok ang root node ng isang puno o graph sa stack.
- Idagdag ang nangungunang item ng stack sa iyong binisita na listahan.
- Tuklasin ang lahat ng mga katabing node sa binisita na node at idagdag ang mga node na hindi pa nakakabisita sa stack.
- Ulitin ang hakbang 2 at 3 hanggang sa walang laman ang stack.
DFS Pseudocode
Ang DFS pseudocode ay ipinapakita sa ibaba. Nasa init() function, isinasagawa namin ang aming DFS function sa bawat node. Dahil ang graph ay maaaring may dalawang nakadiskonektang bahagi, maaari nating patakbuhin ang DFS algorithm sa bawat node upang matiyak na nasasakop namin ang bawat vertex.
DFS ( ga )
a. binisita = totoo
para sa bawat b ∈ g. Adj [ a ]
kung b. binisita == mali
DFS ( g,b )
init ( )
{
Para sa bawat a ∈ g
a. binisita = mali
Para sa bawat a ∈ g
DFS ( ga )
}
Dito kinakatawan ng g, a at b ang graph, unang binisita ang node at node sa stack ayon sa pagkakabanggit.
Pagpapatupad ng DFS sa C++
Isang C++ program para sa DFS ang pagpapatupad ay ibinigay sa ibaba:
#include
#include
#include
gamit namespace std ;
template < typename t >
klase DepthFirstSearch
{
pribado :
mapa < t, listahan < t > > adjList ;
pampubliko :
DepthFirstSearch ( ) { }
walang bisa Add_edge ( t a, t b, bool ikaw = totoo )
{
adjList [ a ] . push_back ( b ) ;
kung ( ikaw )
{
adjList [ b ] . push_back ( a ) ;
}
}
walang bisa Print ( )
{
para sa ( sasakyan i : adjList ) {
cout << i. una << '->' ;
para sa ( t pagpasok : i. pangalawa ) {
cout << pagpasok << ',' ;
}
cout << endl ;
}
}
walang bisa dfs_helper ( t node, mapa < t, bool > at binisita ) {
binisita [ node ] = totoo ;
cout << node << '' << endl ;
para sa ( t kapitbahay : adjList [ node ] ) {
kung ( ! binisita [ kapit-bahay ] ) {
dfs_helper ( kapitbahay, binisita ) ;
}
}
}
walang bisa DFS ( t src )
{
mapa < t, bool > binisita ;
dfs_helper ( src, bumisita ) ;
}
} ;
int pangunahing ( ) {
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. Print ( ) ;
g. DFS ( 6 ) ;
cout << endl ;
}
Sa code na ito, ipinatupad namin DFS algorithm na sumusunod sa pseudo code na ibinigay sa itaas. Mayroon kaming 12 pares ng mga node. Tinukoy namin ang isang klase ' G ” na kumakatawan sa isang graph na may mga vertice a at b na kumakatawan sa binisita at hindi nabisitang mga node.
Output
Konklusyon
DFS ay isang sikat na algorithm sa paghahanap na kapaki-pakinabang para sa ilang mga sitwasyon, tulad ng paghahanap ng mga cycle sa isang graph, at pagkuha ng impormasyon tungkol sa mga konektadong bahagi o lahat ng vertices sa isang graph. Inilarawan din namin ang paggawa ng DFS pamamaraan na may halimbawa. DFS gumagamit ng mga stack upang isagawa ang pamamaraan at maaari ding gamitin sa mga puno.