BFS — Genişlik Öncelikli Arama Algoritması

Genişlik öncelikli arama ya da BFS, düğümleri bir başlangıç düğümüne olan uzaklıklarına göre ziyaret eden bir grafik algoritmasıdır. İki kenar uzaklıktaki düğümlere geçmeden önce, bir kenar uzaklıktaki tüm düğümleri kontrol eder; sonra üç kenar uzaklıktakilere geçer ve bu böyle devam eder.

Katman katman ilerleyen bu sıra, temel fikirdir. Grafik ağırlıksızsa ya da her kenarın maliyeti aynıysa, BFS başlangıç düğümünden erişilebilen her düğüme olan en kısa yol uzunluğunu da verir.

Genişlik Öncelikli Arama Ne Yapar

BFS bir kuyruk kullanır; bu, ilk giren ilk çıkar mantığıyla çalışan bir listedir. Katman sırasını koruyan şey kuyruktur: daha önce keşfedilen düğümler daha önce işlenir.

Genel kalıp şöyledir:

• başlangıç düğümünü ziyaret edildi olarak işaretle
• onu kuyruğa ekle
• öndeki düğümü çıkar
• ziyaret edilmemiş her komşuyu kuyruğun sonuna ekle
• kuyruk boşalana kadar tekrarla

Her düğümün ebeveynini de saklarsanız, arama bittikten sonra en kısa yollardan birini yeniden oluşturabilirsiniz.

Kuyruk Neden Katmanlar Oluşturur

Diyelim ki başlangıç düğümü $A$ olsun. Doğrudan komşuları, $A$'ya uzaklık olarak $1$ birimdir; bu yüzden önce kuyruğa girerler. Ancak bu düğümler işlendikten sonra onların ziyaret edilmemiş komşuları kuyruğa girer; yani sonraki dalga uzaklık $2$ olur.

Bu yüzden BFS, düğümleri başlangıca olan uzaklıklarına göre doğal olarak gruplar. Hangi yolun kısa olduğunu tahmin etmeye çalışmaz. Kuyruk, daha uzun yolları düşünmeden önce daha az kenarlı tüm yolların tamamlanmasını zorunlu kılar.

BFS Örneği: Kenar Sayısına Göre En Kısa Yolu Bulma

Şu grafiği kullanın:

$$A \to \{B, C\}, \qquad B \to \{D\}, \qquad C \to \{E\}, \qquad D \to \{F\}, \qquad E \to \{F\}$$

$A$'dan başlayın. Kuyruk şu şekilde değişir:

$$[A] \to [B, C] \to [C, D] \to [D, E] \to [E, F] \to [F]$$

Bunun anlamı şudur:

Önce $A$ işlenir, sonra $B$ ve $C$ eklenir. Ardından $B$, sonra da $C$ işlenir; bu da $D$ ve $E$'yi ekler. Bundan sonra $D$ ve $E$ işlenir ve $F$'ye ulaşılır.

Dolayısıyla BFS ziyaret sırası şöyledir:

$$A,\ B,\ C,\ D,\ E,\ F$$

$A$'ya olan uzaklıklar şunlardır:

$$\operatorname{dist}(A)=0,\quad \operatorname{dist}(B)=1,\quad \operatorname{dist}(C)=1,\quad \operatorname{dist}(D)=2,\quad \operatorname{dist}(E)=2,\quad \operatorname{dist}(F)=3$$

Bu, asıl kazancı gösterir. BFS, $F$'ye uzaklık $3$ iken ulaşır; yani $A$'dan $F$'ye en kısa yol $3$ kenar kullanır. En kısa yollardan biri $A \to B \to D \to F$'dir. Bir diğeri ise $A \to C \to E \to F$'dir.

BFS'te Sık Yapılan Hatalar

BFS'in Her Zaman En Ucuz Yolu Bulduğunu Sanmak

Bu yalnızca her kenarın maliyeti aynı olduğunda ya da grafik ağırlıksız kabul edildiğinde doğrudur. Kenarların ağırlıkları farklıysa, BFS daha az kenarlı ama toplam maliyeti daha yüksek bir yol bulabilir.

Bir Düğümü Çok Geç İşaretlemek

Standart BFS'te bir düğüm genellikle kuyruktan daha sonra çıkarıldığında değil, kuyruğa eklendiği anda ziyaret edildi olarak işaretlenir. Bu, aynı düğümün kuyruğa birçok kez eklenmesini önler.

BFS ile DFS'i Karıştırmak

BFS katmanlar halinde ilerler. Derinlik öncelikli arama yani DFS ise geri dönmeden önce tek bir dal boyunca ilerlemeye devam eder. Bu iki yöntem, farklı türde sorulara iyi cevap verir.

Sıranın Komşu Sırasına Bağlı Olabileceğini Unutmak

Aynı katman içindeki tam ziyaret sırası, komşuların nasıl listelendiğine göre değişebilir. Uzaklık garantileri yine geçerlidir, ancak dolaşma sırası farklı olabilir.

Genişlik Öncelikli Arama Ne Zaman Kullanılır

BFS; erişilebilirlikle, ağaçlarda seviye sıralı dolaşmayla ya da kenar sayısına göre ölçülen en kısa yol uzunluklarıyla ilgilendiğinizde kullanışlıdır.

Ayrıca her hamlenin aynı maliyete sahip olduğu durum uzayı problemlerinde de karşınıza çıkar. Bu koşul altında, BFS çoğu zaman minimum hamle sayısını bulmanın en açık yoludur.

BFS'i Hatırlamanın Basit Bir Yolu

BFS'i, başlangıç düğümünden dışarı doğru yayılan bir dalga gibi düşünün. Her dalga adımı, uzaklığa bir kenar daha ekler.

Kendi sürümünüzü denemek için küçük bir grafik çizin, bir başlangıç düğümü seçin ve her adımdan sonra kuyruğu yazın. Bir sonraki adımı isterseniz, benzer bir grafik dolaşma problemi çözün ve grafik ağırlıklı olduğunda en kısa yol iddiasının hâlâ geçerli olup olmadığını kontrol edin.