BFS (Breadth First Search) — Geniş Öncelikli Arama Algoritmasını Tanıyalım.
Herkese selamlar, uzun soluklu bir aradan sonra deneyimlerimi yeniden paylaşmaya başladım, bundan sonraki yazılarda, öyle tahmin ediyorum ki algoritma ve analiz başlıklı konular daha sık gelmeye başlayacak. O zaman hız kesmeden giriş yapalım.
BFS Algoritması Nedir ?
BFS geniş öncelikli aramayı temsil eder. Buradaki temel amaç iki hedef arasındaki en kısa mesafeyi bulmaktır. BFS’yi anlatırken arada küçük karşılaştırmalar için DFS’yi de bilmek gerekir. DFS’de aramaya başladığı node’dan ulaşabileceği en derin node’a kadar gider, gidecek daha derin bir node kalmadığında geri sarar(backtracking) ve derin node’lara öncelik vererek gezmeye devam eder.
BFS’nin Buna istinaden kullandığı memory boyutu DFS’ye göre fazladır. Burada DFS’nin tersine önceliğimiz derinlik değil de genişlik olacak. BFS kullanırken genelde Queue veri yapısı kullanılır. Queue kullanmakta ki motivasyon FIFO (ilk giren ilk çıkar) mantığının olmasıdır.
BFS’de bir root node belirlenir ve aynı anda tüm node’lar ziyaret edilir. Burada ziyaret edilen bir node’un dolaşılabileceği tüm komşuları queue(kuyruk)’a eklenir.
Not: Burada tamamı ile Async bir yapıdan bahsetmiyoruz
Yazı boyunca DFS ile karşılaştırma yapmayacağım, yazının sonunda DFS algoritmasının tüm ayrıntılarının ele alındığı bir kaynak bırakıyor olacağım.
Şimdi gelin bu algoritmayı kod üzerine dökmeden önce, bir resim üzerinden nasıl çalıştığını anlamaya çalışalım.
Yukarıdaki tree’de önce bir root yani başlangıç node’u belirlememiz gerekiyor. 1 olarak seçelim. Seçtiğimiz node üzerinden aynı anda hem 2 hem 3 hem de 4 numaralı node’a erişim sağlayabiliriz. Şimdi gelin kuyruğa ilk önce bir numaralı node’u , daha sonra ise 2,3 ve 4 numaralı node’u ekleyelim. Ekledikten sonra 1 numaralı node kuyruktan ayrılmış oluyor. Neden mi ? queue yapısını hatırlayalım. İlk giren ilk çıkar mantığı ile hareket ediyorduk. Unutulmamalıdır ki her adımda kuyruktan bir node çıkarıyoruz ve bu işleme aynı şekilde kalan node’lar üzerinden devam ediyoruz.
BFS Üzerindeki Time Complexity
Burada her node özelinde bir kez gezdiğimiz için Time complexity O(N) olarak ölçülecektir. Ancak daha önce gezdiğimiz node’u tekrar gezecek durumda kalırsak bu oranlar değişecektir.
CODING TIME
Yapacağımız adımlar sırası ile şöyle olmalı;
- Boş bir kuyruk oluştur ve ilk node’u içeriye koy.
- Kuyruk boş olmadığı müddetçe bundan sonraki adımları yap.
- Kuyruğa ilk giren elemanı çıkar ve ekrana yazdır.
- Ziyaret edilen node’ların komşularını bulun ve daha önce ziyaret edildiyse onu tekrar ziyaret etmeyin.
- Komşu var ise onları da kuyruğa ekleyin.
burada toplam node sayısını, komşuları ve node’ları tuttuğumuz değişkenleri oluşturduk. Şimdi constructor aracılığı ile değerlerimizi initialize edelim.
Şimdi ise her node karşılık gelen komşuyu ekleyebileceğim bir util methoda ihtiyacım var. Yazalım..
Bundan sonraki işlem, gelen değeri kuyruğa eklemek, ekledikten sonra ziyaret edildi notunu düşmek ve en sonda kuyruktan çıkarmak. Bu işlemde methoda geçilen değer eğer daha önce ziyaret edilmemiş koşuluna girerse , değeri ziyaret edildi olarak işaretlenir ve node’a eklenir.
Öneriler
