У ДФС , чворови који се истражују се чувају у структури података стека. Ивице које нас усмеравају ка неистраженим чворовима називају се „ ивице открића „док се ивице које воде већ посећене чворове називају „ ивице блока '. ДФС је корисно у сценаријима када програмер жели да пронађе повезане компоненте или циклусе у графу.
Пратите смернице овог чланка да бисте применили ДФС у Ц++.
Имплементација ДФС-а у Ц++
У следећем одељку ћемо прећи на то како ДФС имплементиран је у Ц++. Може се пратити дате кораке за имплементацију ДФС .
- Уметните коријенски чвор стабла или графикона у стек.
- Додајте горњу ставку гомиле на своју посећену листу.
- Откријте све суседне чворове посећеном чвору и додајте оне чворове који још нису посетили стек.
- Поновите кораке 2 и 3 док се гомила не испразни.
ДФС Псеудоцоде
Тхе ДФС псеудокод је приказан испод. У топлота() функцију, ми извршавамо своју ДФС функција на сваком чвору. Пошто граф може имати два неповезана дела, можемо покренути ДФС алгоритам на сваком чвору да би се осигурало да смо покрили сваки врх.
ДФС ( г а )
а. посетила = истина
за свако б ∈ г. Адј [ а ]
ако б. посетила == лажно
ДФС ( г,б )
топлота ( )
{
За свако а ∈ г
а. посетила = лажно
За свако а ∈ г
ДФС ( г, а )
}
Овде г, а и б представљају граф, први посећени чвор и чвор у стеку.
Имплементација ДФС-а у Ц++
Ц++ програм за ДФС имплементација је дата у наставку:
#инцлуде<иостреам>
#инцлуде<мап>
#инцлуде<лист>
Користећи именског простора стд ;
шаблон < типенаме т >
класа ДептхФирстСеарцх
{
приватни :
Мапа < т,лист < т > > адјЛист ;
јавности :
ДептхФирстСеарцх ( ) { }
празнина Адд_едге ( т а, т б, боол ти = истина )
{
адјЛист [ а ] . потисне ( б ) ;
ако ( ти )
{
адјЛист [ б ] . потисне ( а ) ;
}
}
празнина Принт ( )
{
за ( ауто и : адјЛист ) {
цоут << и. први << '->' ;
за ( т улаз : и. друго ) {
цоут << улазак << ',' ;
}
цоут << ендл ;
}
}
празнина дфс_хелпер ( т чвор, мапа < т, боол > & посетила ) {
посетила [ чвор ] = истина ;
цоут << чвор << ' ' << ендл ;
за ( т комшија : адјЛист [ чвор ] ) {
ако ( ! посетила [ комшија ] ) {
дфс_хелпер ( комшија, посећен ) ;
}
}
}
празнина ДФС ( т срц )
{
Мапа < т, боол > посетила ;
дфс_хелпер ( срц,посетио ) ;
}
} ;
инт главни ( ) {
ДептхФирстСеарцх < инт > г ;
г. Адд_едге ( 0 , 5 ) ;
г. Адд_едге ( 0 , 7 ) ;
г. Адд_едге ( 4 , 7 ) ;
г. Адд_едге ( 7 , 8 ) ;
г. Адд_едге ( 2 , 1 ) ;
г. Адд_едге ( 0 , 6 ) ;
г. Адд_едге ( 2 , 4 ) ;
г. Адд_едге ( 3 , 2 ) ;
г. Адд_едге ( 3 , 6 ) ;
г. Адд_едге ( 7 , 5 ) ;
г. Адд_едге ( 5 , 8 ) ;
г. Принт ( ) ;
г. ДФС ( 6 ) ;
цоут << ендл ;
}
У овом коду смо имплементирали ДФС алгоритам који прати псеудо код дат горе. Имамо 12 пари чворова. Дефинисали смо класу „ Г ” који представља граф који има врхове а и б који представљају посећене и непосећене чворове.
Излаз
Закључак
ДФС је популаран алгоритам претраживања користан за неколико сценарија, као што је проналажење циклуса у графу и добијање информација о повезаним компонентама или свим врховима у графу. Такође смо описали рад ДФС метода са примером. ДФС користи стекове за извођење технике и може се користити и на дрвећу.