Dalam DFS , nod yang diterokai disimpan dalam struktur data tindanan. Tepi yang mengarahkan kita ke nod yang belum diterokai dipanggil ' tepi penemuan ' manakala tepi yang akan mendahului nod yang sudah dilawati dipanggil ' tepi blok '. DFS berguna dalam senario apabila pengaturcara ingin mencari komponen atau kitaran yang bersambung dalam graf.
Ikuti garis panduan artikel ini untuk dilaksanakan DFS dalam C++.
Pelaksanaan DFS dalam C++
Dalam bahagian berikut, kami akan membincangkan caranya DFS dilaksanakan dalam C++. Seseorang boleh mengikuti langkah-langkah yang diberikan untuk melaksanakan DFS .
- Masukkan nod akar pokok atau graf ke dalam timbunan.
- Tambahkan item teratas timbunan pada senarai yang anda lawati.
- Temui semua nod bersebelahan dengan nod yang dilawati dan tambahkan nod tersebut yang belum melawati tindanan.
- Ulangi langkah 2 dan 3 sehingga timbunan kosong.
Pseudokod DFS
The DFS pseudokod ditunjukkan di bawah. Di dalam haba() fungsi, kami melaksanakan kami DFS berfungsi pada setiap nod. Kerana graf mungkin mempunyai dua bahagian yang terputus, kita boleh menjalankan DFS algoritma pada setiap nod untuk memastikan bahawa kami telah merangkumi setiap bucu.
DFS ( g a )
a. dilawati = benar
untuk setiap b ∈ g. Adj [ a ]
jika b. dilawati == salah
DFS ( g,b )
haba ( )
{
Untuk setiap a ∈ g
a. dilawati = salah
Untuk setiap a ∈ g
DFS ( g, a )
}
Di sini g, a dan b mewakili graf, nod dan nod yang pertama kali dilawati masing-masing dalam timbunan.
Melaksanakan DFS dalam C++
Program C++ untuk DFS pelaksanaan diberikan di bawah:
#include
#include
#include
menggunakan ruang nama std ;
templat < nama taip t >
kelas DepthFirstSearch
{
persendirian :
peta < t, senarai < t > > adjList ;
awam :
DepthFirstSearch ( ) { }
batal Add_edge ( t a, t b, bool awak = benar )
{
adjList [ a ] . menolak kembali ( b ) ;
jika ( awak )
{
adjList [ b ] . menolak kembali ( a ) ;
}
}
batal Cetak ( )
{
untuk ( auto i : adjList ) {
cout << i. pertama << '->' ;
untuk ( kemasukan t : i. kedua ) {
cout << kemasukan << ',' ;
}
cout << endl ;
}
}
batal dfs_helper ( nod t, peta < t, bool > & dilawati ) {
dilawati [ nod ] = benar ;
cout << nod << ' ' << endl ;
untuk ( t jiran : adjList [ nod ] ) {
jika ( ! dilawati [ jiran ] ) {
dfs_helper ( jiran, melawat ) ;
}
}
}
batal DFS ( t src )
{
peta < t, bool > dilawati ;
dfs_helper ( src, melawat ) ;
}
} ;
int utama ( ) {
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. Cetak ( ) ;
g. DFS ( 6 ) ;
cout << endl ;
}
Dalam kod ini, kami telah melaksanakan DFS algoritma mengikut kod pseudo yang diberikan di atas. Kami mempunyai 12 pasang nod. Kami menentukan kelas ' G ” yang mewakili graf mempunyai bucu a dan b yang mewakili nod yang dilawati dan tidak dilawati.
Pengeluaran
Kesimpulan
DFS ialah algoritma carian popular yang berguna untuk beberapa senario, seperti mencari kitaran dalam graf dan mendapatkan maklumat tentang komponen yang disambungkan atau semua bucu dalam graf. Kami juga menerangkan cara kerja DFS kaedah dengan contoh. DFS menggunakan tindanan untuk melaksanakan teknik dan juga boleh digunakan pada pokok.