İçinde DFS , keşfedilen düğümler bir yığın veri yapısında depolanır. Bizi keşfedilmemiş düğümlere yönlendiren kenarlara ' keşif kenarları ' daha önce ziyaret edilen düğümlere yol gösterecek kenarlara ise ' denir blok kenarları '. DFS bir programcının bir grafikte bağlı bileşenleri veya döngüleri bulmak istediği senaryolarda kullanışlıdır.
Uygulamak için bu makalenin yönergelerini izleyin DFS C++'da.
DFS'nin C++'da uygulanması
Sonraki bölümde, nasıl olduğunu inceleyeceğiz DFS C++'da uygulanmaktadır. Uygulamak için verilen adımları takip edebilirsiniz. DFS .
- Bir ağacın veya grafiğin kök düğümünü yığına ekleyin.
- Yığının en üst öğesini ziyaret ettiğiniz listeye ekleyin.
- Ziyaret edilen düğüme bitişik tüm düğümleri keşfedin ve yığını henüz ziyaret etmemiş olan düğümleri ekleyin.
- Yığın boşalana kadar 2. ve 3. adımları tekrarlayın.
DFS sözde kodu
bu DFS sözde kod aşağıda gösterilmiştir. İçinde sıcaklık() işlevimizi yürütürüz DFS her düğümde işlev Grafiğin bağlantısız iki parçası olabileceğinden, DFS her köşeyi kapsadığımızdan emin olmak için her düğümde algoritma.
DFS ( g bir )
A. ziyaret = doğru
için her b ∈ g. Sıf. [ A ]
eğer B. ziyaret == YANLIŞ
DFS ( g, b )
sıcaklık ( )
{
her a ∈ g için
A. ziyaret = YANLIŞ
her a ∈ g için
DFS ( g, bir )
}
Burada g, a ve b sırasıyla grafiği, ilk ziyaret edilen düğümü ve yığındaki düğümü temsil eder.
DFS'yi C++'da uygulama
için bir C++ programı DFS uygulama aşağıda verilmiştir:
#include
#include
#include
kullanarak ad alanı std ;
şablon < yazı adı T >
sınıf Derinlik öncelikli arama
{
özel :
harita < t, liste < T > > adjlist ;
halk :
Derinlik öncelikli arama ( ) { }
geçersiz Ekle_kenar ( t bir, t b, bool Sen = doğru )
{
adjlist [ A ] . Geri itmek ( B ) ;
eğer ( Sen )
{
adjlist [ B ] . Geri itmek ( A ) ;
}
}
geçersiz Yazdır ( )
{
için ( Oto Ben : adjlist ) {
cout << Ben. Birinci << '->' ;
için ( giriş : Ben. ikinci ) {
cout << giriş << ',' ;
}
cout << son ;
}
}
geçersiz dfs_helper ( t düğümü, harita < T, bool > & ziyaret ) {
ziyaret [ düğüm ] = doğru ;
cout << düğüm << ' ' << son ;
için ( t komşu : adjlist [ düğüm ] ) {
eğer ( ! ziyaret [ komşu ] ) {
dfs_helper ( komşu ziyaret edildi ) ;
}
}
}
geçersiz DFS ( kaynak )
{
harita < T, bool > ziyaret ;
dfs_helper ( src ziyaret edildi ) ;
}
} ;
int ana ( ) {
Derinlik öncelikli arama < int > G ;
G. Ekle_kenar ( 0 , 5 ) ;
G. Ekle_kenar ( 0 , 7 ) ;
G. Ekle_kenar ( 4 , 7 ) ;
G. Ekle_kenar ( 7 , 8 ) ;
G. Ekle_kenar ( 2 , 1 ) ;
G. Ekle_kenar ( 0 , 6 ) ;
G. Ekle_kenar ( 2 , 4 ) ;
G. Ekle_kenar ( 3 , 2 ) ;
G. Ekle_kenar ( 3 , 6 ) ;
G. Ekle_kenar ( 7 , 5 ) ;
G. Ekle_kenar ( 5 , 8 ) ;
G. Yazdır ( ) ;
G. DFS ( 6 ) ;
cout << son ;
}
Bu kodda, uyguladığımız DFS yukarıda verilen sözde kodu izleyen algoritma. 12 çift düğümümüz var. Bir sınıf tanımladık” G ziyaret edilen ve ziyaret edilmeyen düğümleri temsil eden a ve b köşelerine sahip bir grafiği temsil eder.
Çıktı
Çözüm
DFS bir grafikteki döngüleri bulmak ve bir grafikteki bağlı bileşenler veya tüm köşeler hakkında bilgi almak gibi çeşitli senaryolar için yararlı olan popüler bir arama algoritmasıdır. işleyişini de anlatmıştık. DFS Örnek ile yöntem. DFS tekniği uygulamak için yığınlar kullanır ve ağaçlarda da kullanılabilir.