BFS ve DFS arasındaki farklara bakmadan önce öncelikle BFS ve DFS'yi ayrı ayrı bilmeliyiz.

BFS nedir?

BFS anlamına gelir Genişlik Öncelikli Arama . Aynı zamanda şu şekilde de bilinir: seviye sırası geçişi . Kuyruk veri yapısı, Önce Genişlik Arama geçişi için kullanılır. Bir grafikte geçiş için BFS algoritmasını kullandığımızda herhangi bir düğümü kök düğüm olarak düşünebiliriz.

Genişlik ilk arama geçişi için aşağıdaki grafiği ele alalım.

ahh sn

0 nolu düğümü kök düğüm olarak ele aldığımızı varsayalım. Bu nedenle geçiş düğüm 0'dan başlatılacaktır.

Düğüm 0 Kuyruktan kaldırıldığında yazdırılır ve şu şekilde işaretlenir: düğümü ziyaret etti.

0 nolu düğüm Kuyruktan çıkarıldığında, 0 nolu düğümün bitişik düğümleri aşağıda gösterildiği gibi bir Kuyruğa eklenecektir:

Şimdi düğüm 1 Kuyruktan kaldırılacak; yazdırılır ve ziyaret edilen düğüm olarak işaretlenir

Düğüm 1 Kuyruktan çıkarıldığında, düğüm 1'in tüm bitişik düğümleri Kuyruğa eklenecektir. 1. düğümün bitişik düğümleri 0, 3, 2, 6 ve 5'tir. Ancak bir Kuyruğa yalnızca ziyaret edilmemiş düğümleri eklememiz gerekir. 3, 2, 6 ve 5 numaralı düğümler ziyaret edilmediğinden; bu nedenle bu düğümler aşağıda gösterildiği gibi bir Kuyruğa eklenecektir:

Bir sonraki düğüm Kuyruktaki 3'tür. Böylece, düğüm 3 Kuyruktan kaldırılacak, yazdırılacak ve aşağıda gösterildiği gibi ziyaret edildi olarak işaretlenecektir:

Düğüm 3 Kuyruktan çıkarıldığında, ziyaret edilen düğümler dışındaki düğüm 3'ün tüm bitişik düğümleri Kuyruğa eklenecektir. 3. düğümün bitişik düğümleri 0, 1, 2 ve 4'tür. 0, 1 numaralı düğümler zaten ziyaret edildiğinden ve 2. düğüm bir Kuyrukta mevcut olduğundan; bu nedenle bir Kuyruğa yalnızca 4. düğümü eklememiz gerekir.

dizi dilimleme java

Şimdi Kuyruktaki bir sonraki düğüm 2'dir. Yani 2, Kuyruktan silinecektir. Aşağıda gösterildiği gibi yazdırılır ve ziyaret edildi olarak işaretlenir:

Düğüm 2 Kuyruktan çıkarıldığında, ziyaret edilen düğümler dışındaki düğüm 2'nin tüm bitişik düğümleri Kuyruğa eklenecektir. 2. düğümün bitişik düğümleri 1, 3, 5, 6 ve 4'tür. 1 ve 3 numaralı düğümler zaten ziyaret edildiğinden ve 4, 5, 6 zaten Kuyruğa eklendiğinden; bu nedenle Kuyruğa herhangi bir düğüm eklememize gerek yok.

Bir sonraki eleman 5'tir. Yani 5, Kuyruktan silinecektir. Aşağıda gösterildiği gibi yazdırılır ve ziyaret edildi olarak işaretlenir:

Düğüm 5 Kuyruktan çıkarıldığında, ziyaret edilen düğümler dışındaki düğüm 5'in tüm bitişik düğümleri Kuyruğa eklenecektir. 5. düğümün komşu düğümleri 1 ve 2'dir. Her iki düğüm de zaten ziyaret edildiğinden; bu nedenle Kuyruğa eklenecek bir tepe noktası yoktur.

Bir sonraki düğüm 6'dır. Yani 6, Kuyruktan silinecektir. Aşağıda gösterildiği gibi yazdırılır ve ziyaret edildi olarak işaretlenir:

Düğüm 6 Kuyruktan çıkarıldığında, ziyaret edilen düğümler dışındaki düğüm 6'nın tüm bitişik düğümleri Kuyruğa eklenecektir. 6. düğümün komşu düğümleri 1 ve 4'tür. 1. düğüm zaten ziyaret edildiğinden ve 4. düğüm zaten Kuyruğa eklendiğinden; bu nedenle Kuyruğa eklenecek köşe yoktur.

Kuyruktaki bir sonraki öğe 4'tür. Yani 4, Kuyruktan silinecektir. Yazdırılır ve ziyaret edildi olarak işaretlenir.

Düğüm 4 Kuyruktan çıkarıldığında, ziyaret edilen düğümler dışındaki düğüm 4'ün tüm bitişik düğümleri Kuyruğa eklenecektir. 4. düğümün komşu düğümleri 3, 2 ve 6'dır. Bitişik düğümlerin tümü zaten ziyaret edildiğinden; dolayısıyla Kuyruğa eklenecek bir tepe noktası yoktur.

DFS nedir?

DFS Derinlik İlk Arama anlamına gelir. DFS geçişinde LIFO (Son Giren İlk Çıkar) prensibine göre çalışan yığın veri yapısı kullanılır. DFS'de çaprazlama herhangi bir düğümden başlatılabilir veya problemde kök düğümden bahsedilmeyene kadar herhangi bir düğümün kök düğüm olarak değerlendirilebileceğini söyleyebiliriz.

Kuyruktan silinen eleman olan BFS durumunda, silinen düğümün bitişik düğümleri Kuyruğa eklenir. Bunun aksine, DFS'de yığından kaldırılan öğe, daha sonra silinen düğümün yalnızca bir bitişik düğümü yığına eklenir.

java istisnaları

Derinlik Önce Arama geçişi için aşağıdaki grafiği ele alalım.

Düğüm 0'ı kök düğüm olarak düşünün.

Öncelikle 0 elemanını aşağıda gösterildiği gibi yığına ekliyoruz:

0 düğümünün iki bitişik düğümü vardır, yani 1 ve 3. Şimdi geçiş için yalnızca bir bitişik düğümü (1 veya 3) alabiliriz. Diyelim ki düğüm 1'i ele alıyoruz; bu nedenle bir yığına 1 eklenir ve aşağıda gösterildiği gibi yazdırılır:

Şimdi 1. düğümün komşu köşelerine bakacağız. 1. düğümün ziyaret edilmemiş komşu köşeleri 3, 2, 5 ve 6'dır. Bu dört köşeden herhangi birini düşünebiliriz. 3. düğümü aldığımızı ve onu aşağıda gösterildiği gibi yığına yerleştirdiğimizi varsayalım:

3. düğümün ziyaret edilmemiş bitişik köşelerini düşünün. 3. düğümün ziyaret edilmemiş bitişik köşeleri 2 ve 4'tür. Köşelerden herhangi birini alabiliriz, yani 2 veya 4. 2. köşeyi aldığımızı ve onu aşağıda gösterildiği gibi yığına yerleştirdiğimizi varsayalım:

2. düğümün ziyaret edilmemiş bitişik köşeleri 5 ve 4'tür. Köşelerden birini seçebiliriz, yani 5 veya 4. 4. köşeyi aldığımızı ve aşağıda gösterildiği gibi yığına yerleştirdiğimizi varsayalım:

join sql'den güncelleme

Şimdi 4. düğümün ziyaret edilmemiş bitişik köşelerini ele alacağız. 4. düğümün ziyaret edilmemiş bitişik köşesi 6. düğümdür. Bu nedenle, 6. öğe yığına aşağıda gösterildiği gibi eklenir:

6. elemanı yığına yerleştirdikten sonra 6. düğümün ziyaret edilmemiş bitişik köşelerine bakacağız. 6. düğümün ziyaret edilmemiş bitişik köşeleri olmadığından 6. düğümün ötesine geçemiyoruz. Bu durumda aşağıdaki işlemi gerçekleştireceğiz: geriye doğru izleme . En üstteki öğe, yani 6, aşağıda gösterildiği gibi yığından dışarı fırlayacaktır:

Yığındaki en üstteki eleman 4'tür. 4 nolu düğümden geriye ziyaret edilmemiş bitişik köşe kalmadığından; bu nedenle, düğüm 4 aşağıda gösterildiği gibi yığından çıkarılır:

Yığındaki bir sonraki en üstteki öğe 2'dir. Şimdi, düğüm 2'nin ziyaret edilmemiş bitişik köşelerine bakacağız. Yalnızca bir ziyaret edilmemiş düğüm, yani 5 kaldığı için, düğüm 5, 2'nin üzerindeki yığına itilecek ve yazdırılacaktır. Aşağıda gösterildiği gibi:

Şimdi 5. düğümün henüz ziyaret edilmemiş olan bitişik köşelerini kontrol edeceğiz. Ziyaret edilecek bir köşe kalmadığından, 5. öğeyi aşağıda gösterildiği gibi yığından çıkarıyoruz:

np.argmax

5'ten fazla ilerleyemeyiz, dolayısıyla geri izleme yapmamız gerekiyor. Geri izlemede, en üstteki öğe yığından dışarı atılır. Yığından çıkarılacak en üstteki öğe 5'tir ve aşağıda gösterildiği gibi düğüm 2'ye geri dönüyoruz:

Şimdi düğüm 2'nin ziyaret edilmemiş bitişik köşelerini kontrol edeceğiz. Ziyaret edilecek bitişik köşe kalmadığından geri izleme gerçekleştiriyoruz. Geri izlemede, en üstteki öğe, yani 2, yığından dışarı atılır ve aşağıda gösterildiği gibi düğüm 3'e geri döneriz:

Şimdi 3. düğümün ziyaret edilmemiş bitişik köşelerini kontrol edeceğiz. Ziyaret edilecek bitişik köşe kalmadığından geri izleme gerçekleştiriyoruz. Geri izlemede, en üstteki öğe, yani 3, yığından dışarı atılır ve aşağıda gösterildiği gibi düğüm 1'e geri döneriz:

3. elemanı çıkardıktan sonra 1. düğümün ziyaret edilmemiş komşu köşelerini kontrol edeceğiz. Ziyaret edilecek bir köşe kalmadığından; bu nedenle geri izleme gerçekleştirilecektir. Geri izlemede, en üstteki öğe, yani 1, yığından dışarı atılır ve aşağıda gösterildiği gibi 0 düğümüne geri döneriz:

Hala ziyaret edilmemiş olan 0 düğümünün bitişik köşelerini kontrol edeceğiz. Ziyaret edilecek bitişik bir köşe kalmadığından geri izleme gerçekleştiririz. Bunda, aşağıda gösterildiği gibi yığından yalnızca bir öğe, yani yığında kalan 0 öğe çıkarılacaktır:

Yukarıdaki şekilde gördüğümüz gibi yığın boştur. Dolayısıyla DFS geçişini burada durdurmamız gerekiyor ve yazdırılan öğeler DFS geçişinin sonucudur.

BFS ve DFS arasındaki farklar

BFS ve DFS arasındaki farklar şunlardır: