ÖRNEK ile Genişlik Öncelikli Arama (BFS) Algoritması
Sarah Chen
BFS Algoritması (Genişlik-Önce Arama) Nedir?
Genişlik öncelikli arama (BFS), veriyi grafiklemek veya ağaç veya geçiş yapılarını aramak için kullanılan bir algoritmadır. BFS'nin tam biçimi Genişlik öncelikli aramadır.
Algoritma, bir grafikteki tüm anahtar düğümleri doğru bir genişlikte etkili bir şekilde ziyaret eder ve işaretler. Bu algoritma, bir grafikte tek bir düğümü (başlangıç veya kaynak noktası) seçer ve ardından seçilen düğüme bitişik tüm düğümleri ziyaret eder. Unutmayın, BFS bu düğümlere tek tek erişir.
Algoritma başlangıç düğümünü ziyaret edip işaretledikten sonra, en yakın ziyaret edilmemiş düğümlere doğru hareket eder ve onları analiz eder. Ziyaret edildikten sonra, tüm düğümler işaretlenir. Bu yinelemeler, grafiğin tüm düğümleri başarıyla ziyaret edilip işaretlenene kadar devam eder.
Grafik geçişleri nedir?
Grafik geçişi, grafikteki tepe noktası konumunu bulmak için yaygın olarak kullanılan bir yöntemdir. Ziyaret edilen köşelerin sırasını işaretlemenin yanı sıra grafiği hızlı ve hassas bir şekilde analiz edebilen gelişmiş bir arama algoritmasıdır. Bu işlem, sonsuz bir döngüye kilitlenmeden, bir grafikteki her düğümü hızlı bir şekilde ziyaret etmenizi sağlar.
BFS algoritmasının mimarisi
- Verinin çeşitli düzeylerinde herhangi bir düğümü, geçişe başlamak için başlangıç veya ilk düğüm olarak işaretleyebilirsiniz. BFS, düğümü ziyaret edecek ve onu ziyaret edildi olarak işaretleyecek ve kuyruğa yerleştirecektir.
- Şimdi BFS en yakın ve ziyaret edilmemiş düğümleri ziyaret edecek ve onları işaretleyecek. Bu değerler ayrıca kuyruğa eklenir. Kuyruk şu şekilde çalışır: FIFO modeli.
- Benzer şekilde, grafikteki kalan en yakın ve ziyaret edilmemiş düğümler işaretlenerek analiz edilir ve kuyruğa eklenir. Bu öğeler kuyruktan alındı olarak silinir ve sonuç olarak yazdırılır.
Neden BFS Algoritmasına ihtiyacımız var?
Veri kümenizi ararken BFS Algoritmasını kullanmak için sayısız neden vardır. Bu algoritmayı ilk tercihiniz yapan en önemli yönlerden bazıları şunlardır:
- BFS, bir grafikteki düğümleri analiz etmek ve bunlar arasında geçiş yapmanın en kısa yolunu oluşturmak için kullanışlıdır.
- BFS, en az sayıda yinelemeyle bir grafikte geçiş yapabilir.
- BFS algoritmasının mimarisi basit ve sağlamdır.
- BFS algoritmasının sonucu, diğer algoritmalara kıyasla yüksek düzeyde doğruluk sağlar.
- BFS yinelemeleri kusursuzdur ve bu algoritmanın sonsuz döngü problemine kapılma ihtimali yoktur.
BFS Algoritması Nasıl Çalışır?
Grafik geçişi, algoritmanın ziyaret edilmeyen her düğümü ağaç benzeri bir yapıda ziyaret etmesini, kontrol etmesini ve/veya güncellemesini gerektirir. Grafik geçişleri, grafikteki düğümleri ziyaret etme sırasına göre kategorize edilir.
BFS algoritması, işlemi bir grafikteki ilk veya başlangıç düğümünden başlatır ve onu baştan sona kat eder. İlk düğümü başarılı bir şekilde geçtikten sonra, grafikteki bir sonraki geçilmeyen köşe ziyaret edilir ve işaretlenir.
Dolayısıyla, geçerli tepe noktasına bitişik tüm düğümlerin ilk yinelemede ziyaret edildiğini ve geçildiğini söyleyebilirsiniz. Bir BFS algoritmasının çalışmasını uygulamak için basit bir kuyruk metodolojisi kullanılır ve aşağıdaki adımlardan oluşur:
) 1 Adım
Grafikteki her köşe veya düğüm bilinmektedir. Örneğin düğümü V olarak işaretleyebilirsiniz.
) 2 Adım
V tepe noktasına erişilmemesi durumunda V köşe noktasını BFS Kuyruğuna ekleyin
) 3 Adım
BFS aramasını başlatın ve tamamlandıktan sonra V köşe noktasını ziyaret edildi olarak işaretleyin.
) 4 Adım
BFS kuyruğu hala boş değil, dolayısıyla grafiğin V tepe noktasını kuyruktan kaldırın.
) 5 Adım
Grafikte V tepe noktasına bitişik kalan tüm köşe noktalarını alın
) 6 Adım
Her bitişik köşe için V1 diyelim, henüz ziyaret edilmemiş olması durumunda BFS kuyruğuna V1 ekleyin
) 7 Adım
BFS, V1'i ziyaret edecek ve onu ziyaret edildi olarak işaretleyecek ve kuyruktan silecektir.
Örnek BFS Algoritması
) 1 Adım
0 – 6 arasında değişen yedi sayıdan oluşan bir grafiğiniz var.
) 2 Adım
0 veya sıfır kök düğüm olarak işaretlendi.
) 3 Adım
0 ziyaret edilir, işaretlenir ve kuyruk veri yapısına eklenir.
) 4 Adım
Geriye kalan 0 bitişik ve ziyaret edilmemiş düğüm ziyaret edilir, işaretlenir ve kuyruğa eklenir.
) 5 Adım
Geçiş yinelemeleri tüm düğümler ziyaret edilene kadar tekrarlanır.
BFS Algoritmasının Kuralları
BFS algoritmasını kullanmanın önemli kuralları şunlardır:
- Bir kuyruk (FIFO-İlk Giren İlk Çıkar) veri yapısı BFS tarafından kullanılmaktadır.
- Grafikteki herhangi bir düğümü kök olarak işaretlersiniz ve verileri oradan geçirmeye başlarsınız.
- BFS, grafikteki tüm düğümlerden geçer ve bunları tamamlandığı gibi bırakmaya devam eder.
- BFS, bitişikteki ziyaret edilmemiş bir düğümü ziyaret eder, bunu tamamlandı olarak işaretler ve kuyruğa ekler.
- Bitişik bir köşe bulunamaması durumunda önceki köşeyi sıradan kaldırır.
- BFS algoritması, grafikteki tüm köşeler başarıyla geçilene ve tamamlandı olarak işaretlenene kadar yinelenir.
- Verilerin herhangi bir düğümden geçişi sırasında BFS'nin neden olduğu döngüler yoktur.
BFS Algoritmasının Uygulamaları
Bir BFS algoritması uygulamasının son derece etkili olabileceği bazı gerçek hayat uygulamalarına bir göz atalım.
- Ağırlıklandırılmamış Grafikler: BFS algoritması, grafiğin tüm köşelerini mümkün olan en kısa sürede ve yüksek doğrulukla ziyaret etmek için en kısa yolu ve minimum yayılan ağacı kolayca oluşturabilir.
- P2P Ağları: BFS, eşler arası bir ağdaki tüm en yakın veya komşu düğümleri bulmak için uygulanabilir. Bu, gerekli verileri daha hızlı bulacaktır.
- Web Tarayıcıları: Arama motorları veya web tarayıcıları, BFS'yi kullanarak kolayca birden fazla düzeyde dizin oluşturabilir. BFS uygulaması kaynaktan, yani web sayfasından başlar ve ardından bu kaynaktan gelen tüm bağlantıları ziyaret eder.
- Navigasyon Sistemleri: BFS, ana veya kaynak konumdan tüm komşu konumları bulmanıza yardımcı olabilir.
- Ağ Yayını: Yayınlanan bir paket, adresine sahip olduğu tüm düğümleri bulmak ve ulaşmak için BFS algoritması tarafından yönlendirilir.
ÖZET
- Grafik geçişi, algoritmanın ziyaret edilmeyen her düğümü ağaç benzeri bir yapıda ziyaret etmesini, kontrol etmesini ve/veya güncellemesini gerektiren benzersiz bir süreçtir. BFS algoritması da benzer prensipte çalışır.
- Algoritma, bir grafikteki düğümleri analiz etmek ve bunlar arasında geçiş yapmanın en kısa yolunu oluşturmak için kullanışlıdır.
- Algoritma, grafiği mümkün olan en az sayıda yinelemede ve mümkün olan en kısa sürede dolaşır.
- BFS, bir grafikte tek bir düğümü (başlangıç veya kaynak noktası) seçer ve ardından seçilen düğüme bitişik tüm düğümleri ziyaret eder. BFS bu düğümlere tek tek erişir.
- Ziyaret edilen ve işaretlenen veriler BFS tarafından sıraya alınır. Kuyruk ilk giren ilk çıkar prensibine göre çalışır. Dolayısıyla grafiğe ilk yerleştirilen eleman önce silinir ve sonuç olarak yazdırılır.
- BFS algoritması asla sonsuz bir döngüye giremez.
- Yüksek hassasiyet ve sağlam uygulama nedeniyle BFS, P2P ağları, Web Tarayıcıları ve Ağ Yayını gibi birçok gerçek hayat çözümünde kullanılır.
