Di dalam DFS , node yang sedang dieksplorasi disimpan dalam struktur data tumpukan. Tepi yang mengarahkan kita ke node yang belum dijelajahi disebut ' tepi penemuan 'sementara ujung-ujungnya mengarah ke node yang sudah dikunjungi disebut' blok tepi '. DFS berguna dalam skenario ketika seorang programmer ingin menemukan komponen atau siklus yang terhubung dalam grafik.
Ikuti panduan artikel ini untuk diterapkan DFS dalam C++.
Implementasi DFS di C++
Di bagian berikut, kita akan membahas caranya DFS diimplementasikan dalam C++. Seseorang dapat mengikuti langkah-langkah yang diberikan untuk diterapkan DFS .
- Masukkan simpul akar pohon atau grafik ke dalam tumpukan.
- Tambahkan item teratas tumpukan ke daftar yang Anda kunjungi.
- Temukan semua simpul yang berdekatan ke simpul yang dikunjungi dan tambahkan simpul yang belum mengunjungi tumpukan.
- Ulangi langkah 2 dan 3 hingga tumpukan kosong.
Kode Pseudo DFS
Itu DFS pseudocode ditunjukkan di bawah ini. Dalam panas() fungsi, kami mengeksekusi kami DFS fungsi pada setiap node. Karena grafik mungkin memiliki dua bagian yang tidak terhubung, kita dapat menjalankan DFS algoritma pada setiap node untuk memastikan bahwa kita telah mencakup setiap simpul.
DFS ( g a )
A. dikunjungi = BENAR
untuk setiap b ∈ g. Adj [ A ]
jika B. dikunjungi == PALSU
DFS ( g, b )
panas ( )
{
Untuk setiap a ∈ g
A. dikunjungi = PALSU
Untuk setiap a ∈ g
DFS ( g, a )
}
Di sini g, a dan b mewakili grafik, masing-masing simpul dan simpul yang dikunjungi pertama dalam tumpukan.
Menerapkan DFS di C++
Program C++ untuk DFS implementasi diberikan di bawah ini:
#termasuk
#sertakan
#sertakan
menggunakan ruang nama std ;
templat < ketik nama T >
kelas DepthFirstSearch
{
pribadi :
peta < t, daftar < T > > adjList ;
publik :
DepthFirstSearch ( ) { }
ruang kosong Add_edge ( t a, t b, bool Anda = BENAR )
{
adjList [ A ] . push_back ( B ) ;
jika ( Anda )
{
adjList [ B ] . push_back ( A ) ;
}
}
ruang kosong Mencetak ( )
{
untuk ( mobil Saya : adjList ) {
cout << Saya. Pertama << '->' ;
untuk ( masuk : Saya. Kedua ) {
cout << pintu masuk << ',' ;
}
cout << endl ;
}
}
ruang kosong dfs_helper ( simpul t,peta < T, bool > & dikunjungi ) {
dikunjungi [ simpul ] = BENAR ;
cout << simpul << ' ' << endl ;
untuk ( t tetangga : adjList [ simpul ] ) {
jika ( ! dikunjungi [ tetangga ] ) {
dfs_helper ( tetangga, dikunjungi ) ;
}
}
}
ruang kosong DFS ( t src )
{
peta < T, bool > dikunjungi ;
dfs_helper ( src, dikunjungi ) ;
}
} ;
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. Mencetak ( ) ;
G. DFS ( 6 ) ;
cout << endl ;
}
Dalam kode ini, kami telah menerapkan DFS algoritma mengikuti kode pseudo yang diberikan di atas. Kami memiliki 12 pasang node. Kami mendefinisikan kelas ' G ” yang merepresentasikan graf yang memiliki simpul a dan b yang merepresentasikan node yang telah dikunjungi dan yang belum dikunjungi.
Keluaran
Kesimpulan
DFS adalah algoritma pencarian populer yang berguna untuk beberapa skenario, seperti menemukan siklus dalam grafik, dan mendapatkan informasi tentang komponen yang terhubung atau semua simpul dalam grafik. Kami juga menjelaskan cara kerja dari DFS metode dengan contoh. DFS mempekerjakan tumpukan untuk mengeksekusi teknik dan juga dapat digunakan pada pohon.