Bu makale, sağlanan bir ağaç veya grafik için DFS'yi uygulama prosedürünü gösterir.
Java'da Bir Grafik İçin Derinlik Önce Arama veya DFS Nasıl Uygulanır?
DFS, öncelikle her dalı/köşeyi tam olarak bir kez ziyaret ederek bir grafik aramak için kullanılır. Kilitlenmeleri önlemeye yardımcı olan bir grafikteki döngüleri algılayabilir veya tanımlayabilir. Bulmacaları veya labirent problemlerini çözmek için kullanılabilir. DFS, grafik algoritmalarında, web taramasında ve derleyici tasarımında uygulanabilir/kullanılabilir.
Açıklama için Derinlik Önce Arama veya DFS'nin aşağıdaki kodunu ziyaret edin:
sınıf grafik {
özel Bağlantılı liste ek düğüm [ ] ;
özel mantıksal geçti [ ] ;
grafik ( int köşeler ) {
ek düğüm = yeni Bağlantılı liste [ köşeler ] ;
geçti = yeni mantıksal [ köşeler ] ;
için ( int Ben = 0 ; Ben < köşeler ; Ben ++ )
ek düğüm [ Ben ] = yeni Bağlantılı liste ( ) ;
}
geçersiz ek kenar ( int kaynak, int başlangıç ) {
ek düğüm [ kaynak ] . eklemek ( başlangıç ) ;
}
Yukarıdaki kodun açıklaması:
- İlk olarak, “adlı sınıf grafik ' yaratıldı. İçinde, bir “ Bağlantılı liste ”adlı” ek düğüm[] ” ve “ adlı bir boole tipi dizi geçildi[] ”.
- Ardından, “ yapıcısı için köşeleri iletin. grafik ” parametresi olarak sınıf.
- Bundan sonra “ için Seçilen dalın her bir düğümü arasında hareket etmek için ” döngüsü oluşturulur.
- Sonunda, boşluk türü ' kenar ekle() ” Köşeler arasına kenar eklemek için kullanılır. Bu işlev iki parametre alır: tepe noktasının kaynağı ' kaynak ” ve hedef tepe noktası “ başlangıç ”.
Grafiği oluşturduktan sonra, şimdi yukarıda oluşturduğumuz graf için derinlik öncelikli arama veya DFS kodunu ekleyelim:
geçersiz DFS ( int köşe ) {
geçti [ köşe ] = doğru ;
Sistem . dışarı . Yazdır ( köşe + ' ' ) ;
Yineleyici Bu = ek düğüm [ köşe ] . listyineleyici ( ) ;
sırasında ( Bu. hasSonraki ( ) ) {
int sıfat = Bu. Sonraki ( ) ;
eğer ( ! geçti [ sıfat ] )
DFS ( sıfat ) ;
}
}
Yukarıdaki kod bloğunda:
- İlk önce ' DFS() 'işlevi oluşturulur ve elde edilir' köşe ” parametresi olarak. Bu tepe noktası ziyaret edildi olarak işaretlendi.
- Ardından, “ kullanarak ziyaret edilen tepe noktasını yazdırın. çıktı.baskı() ' yöntem.
- Ardından, “ örneğini oluşturun Yineleyici ”, geçerli tepe noktasının bitişik köşeleri üzerinde yinelenir.
- Köşe ziyaret edilmezse, o tepe noktasını “ DFS() ' işlev.
Şimdi bir '' oluşturalım. ana() Grafiği oluşturmak ve ardından buna DFS uygulamak için ' işlev bölümü:
halk statik geçersiz ana ( Sicim argümanlar [ ] ) {
grafik k = yeni grafik ( 4 ) ;
k. ek kenar ( 0 , 1 ) ;
k. ek kenar ( 1 , 2 ) ;
k. ek kenar ( 2 , 3 ) ;
k. ek kenar ( 3 , 3 ) ;
Sistem . dışarı . yazdır ( 'Aşağıdaki Derinlik İlk Geçişidir' ) ;
k. DFS ( 1 ) ;
}
}
Yukarıdaki kodun açıklaması:
- İlk olarak, bir nesne oluşturun ' k ' için ' Grafik() ' yöntem.
- Sonra, “ kenar ekle() ” yöntemi, birden çok köşe arasına kenar eklemek için kullanılır. Bu, grafiğimizin yapısını oluşturur.
- Sonunda, herhangi bir köşe değerini, önceden oluşturulmuş olana bağımsız değişken olarak iletin ' DFS() ' işlev. Bu köşe yolunu kökten bulmak için, bir derinlik öncelikli arama algoritması kullanın. Örneğin, “değeri 1 ” şuraya geçirilir: DFS() ' işlev.
Derleme aşamasının bitiminden sonra:
Çıktı, derinlik öncelikli aramanın başarıyla uygulandığını gösterir.
Çözüm
Derinlik Önce Arama, en kısa yolu bulma, ağaçları kapsayan ve bağlantı analizi gibi birçok grafik algoritmasının temelini oluşturan bir grafik geçiş algoritmasıdır. Kök düğümden başlar ve ardından geri izlemeden önce ayrılma düğümüne veya o dalın son düğümüne kadar mümkün olduğu kadar derine iner. Bu makale, Java'da bir grafik için derinlik öncelikli aramayı veya DFS'yi uygulama prosedürünü göstermiştir.