Į DFS , tiriami mazgai saugomi kamino duomenų struktūroje. Kraštai, nukreipiantys mus į neištirtus mazgus, vadinami ' atradimų kraštai 'o kraštai, vedantys į jau aplankytus mazgus, vadinami' bloko kraštai “. DFS yra naudinga tais atvejais, kai programuotojas nori grafike rasti prijungtus komponentus arba ciklus.
Norėdami įgyvendinti, vadovaukitės šio straipsnio gairėmis DFS C++ kalboje.
DFS diegimas C++
Kitame skyriuje apžvelgsime, kaip tai padaryti DFS yra įdiegtas C++. Galima atlikti nurodytus įgyvendinimo veiksmus DFS .
- Į krūvą įterpkite šakninį medžio ar grafiko mazgą.
- Pridėkite aukščiausią kamino elementą į aplankytų sąrašą.
- Atraskite visus gretimus aplankyto mazgo mazgus ir pridėkite tuos mazgus, kurie dar neaplankė krūvos.
- Kartokite 2 ir 3 veiksmus, kol krūva bus tuščia.
DFS pseudokodas
The DFS pseudokodas parodytas žemiau. Viduje karštis () funkciją, mes vykdome savo DFS funkcija kiekviename mazge. Kadangi grafike gali būti dvi atskirtos dalys, galime paleisti DFS algoritmą kiekviename mazge, kad įsitikintume, jog apėmėme kiekvieną viršūnę.
DFS ( g a )
a. aplankė = tiesa
dėl kas b ∈ g. Adj [ a ]
jeigu b. aplankė == klaidinga
DFS ( g, b )
karštis ( )
{
Už kiekvieną a ∈ g
a. aplankė = klaidinga
Už kiekvieną a ∈ g
DFS ( g, a )
}
Čia g, a ir b žymi grafiką, atitinkamai pirmą kartą aplankytą mazgą ir mazgą.
DFS diegimas C++
C++ programa, skirta DFS įgyvendinimas pateiktas žemiau:
#include
#įtraukti<žemėlapį>
#įtraukti
naudojant vardų erdvė std ;
šabloną < tipo pavadinimas t >
klasė DepthFirstSearch
{
privatus :
žemėlapį < t, sąrašas < t > > adjList ;
viešas :
DepthFirstSearch ( ) { }
tuštuma Pridėti_kraštą ( t a, t b, bool tu = tiesa )
{
adjList [ a ] . pastumti atgal ( b ) ;
jeigu ( tu )
{
adjList [ b ] . pastumti atgal ( a ) ;
}
}
tuštuma Spausdinti ( )
{
dėl ( automatinis i : adjList ) {
cout << i. Pirmas << '->' ;
dėl ( t įėjimas : i. antra ) {
cout << įrašas << ',' ;
}
cout << endl ;
}
}
tuštuma dfs_helper ( t mazgas, žemėlapis < t, bool > & aplankė ) {
aplankė [ mazgas ] = tiesa ;
cout << mazgas << ' ' << endl ;
dėl ( t kaimynas : adjList [ mazgas ] ) {
jeigu ( ! aplankė [ kaimynas ] ) {
dfs_helper ( kaimynas, lankėsi ) ;
}
}
}
tuštuma DFS ( t src )
{
žemėlapį < t, bool > aplankė ;
dfs_helper ( src, lankėsi ) ;
}
} ;
tarpt pagrindinis ( ) {
DepthFirstSearch < tarpt > g ;
g. Pridėti_kraštą ( 0 , 5 ) ;
g. Pridėti_kraštą ( 0 , 7 ) ;
g. Pridėti_kraštą ( 4 , 7 ) ;
g. Pridėti_kraštą ( 7 , 8 ) ;
g. Pridėti_kraštą ( 2 , 1 ) ;
g. Pridėti_kraštą ( 0 , 6 ) ;
g. Pridėti_kraštą ( 2 , 4 ) ;
g. Pridėti_kraštą ( 3 , 2 ) ;
g. Pridėti_kraštą ( 3 , 6 ) ;
g. Pridėti_kraštą ( 7 , 5 ) ;
g. Pridėti_kraštą ( 5 , 8 ) ;
g. Spausdinti ( ) ;
g. DFS ( 6 ) ;
cout << endl ;
}
Šiame kode mes įdiegėme DFS algoritmas pagal aukščiau pateiktą pseudo kodą. Turime 12 porų mazgų. Mes apibrėžėme klasę ' G “, kuris reiškia grafiką, turintį viršūnes a ir b, kurios žymi aplankytus ir neaplankytus mazgus.
Išvestis
Išvada
DFS yra populiarus paieškos algoritmas, naudingas keliems scenarijams, pvz., ieškant ciklų grafike ir gauti informaciją apie prijungtus komponentus arba visas grafiko viršūnes. Taip pat aprašėme, kaip veikia DFS metodas su pavyzdžiu. DFS Technikai atlikti naudojami kaminai, taip pat gali būti naudojami ant medžių.