ÖRNEK ile Genişlik Öncelikli Arama (BFS) Algoritması
Sarah Chen
⚡ Akıllı Özet
Genişlik Öncelikli Arama (BFS), bir grafı seviye seviye tarayan ve daha derine inmeden önce bir düğümün tüm komşularını ziyaret eden bir algoritmadır. FIFO kuyruğu kullanır ve sonsuz döngüler olmadan ağırlıksız grafiklerde en kısa yolu bulur.
BFS Algoritması (Genişlik-Önce Arama) Nedir?
Genişlik öncelikli arama (BFS), grafik verilerini aramak, ağaç yapılarını incelemek veya yapıları dolaşmak için kullanılan bir algoritmadır. BFS'nin açılımı Genişlik Öncelikli Arama'dı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
- Verilerin çeşitli seviyelerinde, gezinmeye başlamak için herhangi bir düğümü başlangıç veya ilk düğüm olarak işaretleyebilirsiniz. BFS, düğümü ziyaret edecek, ziyaret edildi olarak işaretleyecek ve kuyruğa yerleştirecektir.
- Şimdi BFS, en yakın ve ziyaret edilmemiş düğümleri ziyaret edecek ve işaretleyecektir. Bu değerler de kuyruğa eklenir. Kuyruk şu şekilde çalışır: FIFO modeli.
- Benzer şekilde, grafikteki kalan en yakın ve ziyaret edilmemiş düğümler analiz edilir, işaretlenir ve kuyruğa eklenir. Bu öğeler alındıkça kuyruktan silinir ve sonuç olarak yazdırılır.
Neden BFS Algoritmasına ihtiyacımız var?
Veri kümenizde arama yapmak için BFS algoritmasını kullanmanın birçok nedeni vardır. Bu algoritmayı ilk tercihiniz yapan en önemli özelliklerden 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, mevcut düğüme bitişik tüm düğümlerin ilk yinelemede ziyaret edildiğini ve tarandığını söyleyebilirsiniz. Bir BFS algoritmasının çalışma prensibini uygulamak için basit bir kuyruk metodolojisi kullanılır ve bu metodoloji 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
Eğer V düğümüne erişilmemişse, V düğümünü BFS kuyruğuna ekleyin.
) 3 Adım
BFS aramasını başlatın ve tamamlandıktan sonra V düğümünü ziyaret edilmiş 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 düğümüne bitişik olan kalan tüm düğümleri alın.
) 6 Adım
Her bir bitişik köşe için, diyelim ki V1, henüz ziyaret edilmemişse, V1'i BFS kuyruğuna ekleyin.
) 7 Adım
BFS, V1'i ziyaret edecek, ziyaret edilmiş olarak işaretleyecek ve kuyruktan silecektir.
Örnek BFS Algoritması
) 1 Adım
0 ile 6 arasında 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'a bitişik ve ziyaret edilmemiş düğümler 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ı kullanırken dikkat edilmesi gereken ö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 o düğümden başlayarak incelemeye başlarsınız.
- BFS, grafikteki tüm düğümleri dolaşır ve gereksiz olanları atar.ping Onları tamamlanmış olarak görün.
- BFS, bitişikteki ziyaret edilmemiş bir düğümü ziyaret eder, bunu tamamlandı olarak işaretler ve kuyruğa ekler.
- Komşu bir köşe bulunamazsa, önceki köşeyi kuyruktan kaldırır.
- BFS algoritması, grafikteki tüm köşeler başarıyla taranıp tamamlanmış olarak işaretlenene kadar döngüye girer.
- 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ı, grafın 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 kapsayan ağacı kolayca oluşturabilir.
- P2P Ağları: BFS, eşler arası bir ağdaki en yakın veya komşu düğümleri bulmak için uygulanabilir. Bu, gerekli veriyi daha hızlı bulmayı sağlayacaktı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.
