BFS Algoritması (Genişlik-İlk Arama) nedir?
Genişlik-ilk arama (BFS), verilerin grafiğini çizmek veya ağaç veya çapraz yapıları aramak için kullanılan bir algoritmadır. BFS'nin tam biçimi, Genişlik ilk aramadır.
Algoritma, bir grafikteki tüm anahtar düğümleri enine doğru bir şekilde verimli 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ü ziyaret edip işaretlediğinde, en yakın ziyaret edilmemiş düğümlere doğru hareket eder ve onları analiz eder. Ziyaret edildiğinde tüm düğümler işaretlenir. Bu yinelemeler, grafiğin tüm düğümleri başarıyla ziyaret edilene ve işaretlenene kadar devam eder.
Bu Algoritma eğitiminde şunları öğreneceksiniz:
- BFS Algoritması (Genişlik-İlk Arama) nedir?
- Grafik geçişleri nedir?
- BFS algoritmasının mimarisi
- Neden BFS Algoritmasına ihtiyacımız var?
- BFS Algoritması Nasıl Çalışır?
- Örnek BFS Algoritması
- BFS Algoritmasının Kuralları
- BFS Algoritmasının Uygulamaları
Grafik geçişleri nedir?
Grafik geçişi, grafikte tepe konumunu bulmak için yaygın olarak kullanılan bir metodolojidir. 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, geçişi başlatmak için herhangi bir düğümü başlangıç veya ilk düğüm olarak işaretleyebilirsiniz. BFS, düğümü ziyaret edecek ve 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 de kuyruğa eklenir. Kuyruk FIFO modelinde çalışır.
- Benzer şekilde, grafikte kalan en yakın ve ziyaret edilmeyen düğümler analiz edilir ve işaretlenir ve kuyruğa eklenir. Bu öğeler kuyruktan alınır ve sonuç olarak yazdırılır.
Neden BFS Algoritmasına ihtiyacımız var?
Veri kümenizi ararken kullanmak için BFS Algoritmasını kullanmanın birçok nedeni vardır. Bu algoritmayı ilk tercihiniz yapan en hayati yönlerden bazıları şunlardır:
- BFS, bir grafikteki düğümleri analiz etmek ve bunlardan geçmenin en kısa yolunu oluşturmak için kullanışlıdır.
- BFS, en az sayıda yinelemede bir grafikte gezinebilir.
- 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 sorunsuzdur ve bu algoritmanın sonsuz döngü problemine takılma olasılığı yoktur.
BFS Algoritması Nasıl Çalışır?
Grafik geçişi, algoritmanın ağaç benzeri bir yapıdaki her bir ziyaret edilmemiş düğümü ziyaret etmesini, kontrol etmesini ve / veya güncellemesini gerektirir. Grafik geçişleri, grafikteki düğümleri ziyaret 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 tamamen dolaşır. İlk düğümü başarılı bir şekilde geçtikten sonra, grafikteki bir sonraki geçilmemiş köşe ziyaret edilir ve işaretlenir.
Bu nedenle, mevcut 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:
Aşama 1)
Grafikteki her köşe veya düğüm bilinmektedir. Örneğin, düğümü V olarak işaretleyebilirsiniz.
Adım 2)
Köşe V'ye erişilmemesi durumunda, köşe V'yi BFS Kuyruğuna ekleyin
Aşama 3)
BFS aramasını başlatın ve tamamlandıktan sonra, köşe V'yi ziyaret edildi olarak işaretleyin.
Adım 4)
BFS kuyruğu hala boş değil, bu nedenle grafikteki V tepe noktasını kuyruktan kaldırın.
Adım 5)
V tepe noktasına bitişik olan grafikte kalan tüm köşeleri alın
Adım 6)
Her bitişik köşe için V1 diyelim, henüz ziyaret edilmemişse, ardından BFS kuyruğuna V1 ekleyin
Adım 7)
BFS, V1'i ziyaret edecek ve ziyaret edildi olarak işaretleyecek ve kuyruktan silecektir.
Örnek BFS Algoritması
Aşama 1)
0-6 arasında değişen yedi sayıdan oluşan bir grafiğiniz var.
Adım 2)
0 veya sıfır, kök düğüm olarak işaretlendi.
Aşama 3)
0 ziyaret edilir, işaretlenir ve kuyruk veri yapısına eklenir.
Adım 4)
Kalan 0 bitişik ve ziyaret edilmemiş düğüm ziyaret edilir, işaretlenir ve kuyruğa eklenir.
Adım 5)
Geçiş yinelemeleri, tüm düğümler ziyaret edilene kadar tekrarlanır.
BFS Algoritmasının Kuralları
İşte, BFS algoritmasını kullanmak için önemli kurallar:
- BFS tarafından bir kuyruk (FIFO-İlk Giren İlk Çıkar) veri yapısı kullanılır.
- Grafikteki herhangi bir düğümü kök olarak işaretler ve ondan verileri geçmeye başlarsınız.
- BFS, grafikteki tüm düğümleri dolaşır ve bunları tamamlanmış olarak bırakmaya devam eder.
- BFS, bitişik bir ziyaret edilmemiş düğümü ziyaret eder, tamamlandı olarak işaretler ve bir kuyruğa ekler.
- Bitişik köşe bulunmaması durumunda önceki köşeyi kuyruktan kaldırır.
- BFS algoritması, grafikteki tüm köşeler başarıyla geçilene ve tamamlandı olarak işaretlenene kadar yinelenir.
- Herhangi bir düğümden veri geçişi sırasında BFS'nin neden olduğu hiçbir döngü yoktur.
BFS Algoritmasının Uygulamaları
Bir BFS algoritma uygulamasının oldukça etkili olabileceği bazı gerçek hayattaki uygulamalara bir göz atalım.
- Ağırlıksız Grafikler: BFS algoritması, grafiğin tüm köşelerini mümkün olan en kısa sürede yüksek doğrulukla ziyaret etmek için en kısa yolu ve minimum kapsayan ağacı kolayca oluşturabilir.
- P2P Ağları: BFS, bir eşler arası 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 kullanarak kolayca birden çok dizin düzeyi oluşturabilir. BFS uygulaması, web sayfası olan kaynaktan başlar ve daha sonra o kaynaktan gelen tüm bağlantıları ziyaret eder.
- Navigasyon Sistemleri: BFS, ana veya kaynak konumdan tüm komşu konumların bulunmasına yardımcı olabilir.
- Ağ Yayını: Yayınlanan bir paket, adresine sahip olduğu tüm düğümleri bulması ve bunlara erişmesi için BFS algoritması tarafından yönlendirilir.
Özet
- Grafik geçişi, algoritmanın ağaç benzeri bir yapıdaki her bir ziyaret edilmemiş düğümü ziyaret etmesini, kontrol etmesini ve / veya güncellemesini gerektiren benzersiz bir işlemdir. BFS algoritması benzer bir prensipte çalışır.
- Algoritma, bir grafikteki düğümleri analiz etmek ve bunlardan geçmenin en kısa yolunu oluşturmak için kullanışlıdır.
- Algoritma, grafiği en az sayıda yineleme ve mümkün olan en kısa sürede geçer.
- 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 bir kuyruğa alınır. Kuyruk ilk giren ilk çıkar temelinde çalışır. Bu nedenle, önce grafiğe yerleştirilen öğe önce silinir ve sonuç olarak yazdırılır.
- BFS algoritması asla sonsuz 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 çoklu gerçek yaşam çözümlerinde kullanılır.