BFS nedir?
BFS, verilerin grafiğini çizmek veya ağaç veya yapıları dolaşmak için arama yapmak için kullanılan bir algoritmadı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. 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. BFS'nin tam biçimi, Genişlik ilk aramadır.
Bu BSF Vs. DFS İkili ağaç öğreticisi, şunları öğreneceksiniz:
- BFS nedir?
- DFS nedir?
- BFS Örneği
- DFS Örneği
- BFS ve DFS İkili Ağaç arasındaki fark
- BFS uygulamaları
- DFS uygulamaları
DFS nedir?
DFS, grafikleri veya ağaçları derinlik yönünde bulmak veya geçmek için bir algoritmadır. Algoritmanın yürütülmesi kök düğümde başlar ve geriye dönük izleme öncesinde her dalı araştırır. Herhangi bir yinelemede bir çıkmaz göründüğünde hatırlamak, sonraki tepe noktasını elde etmek ve bir arama başlatmak için bir yığın veri yapısı kullanır. DFS'nin tam biçimi Derinlik öncelikli aramadır.
BFS Örneği
Aşağıdaki DFS örneğinde, 6 köşeli bir grafik kullandık.
BFS Örneği
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.
DFS Örneği
Aşağıdaki DFS örneğinde, 5 köşesi olan yönsüz bir grafik kullandık.
Aşama 1)
0. köşe noktasından başladık. Algoritma, onu ziyaret edilenler listesine koyarak ve eşzamanlı olarak tüm bitişik köşelerini yığın adı verilen veri yapısına yerleştirerek başlar.
Adım 2)
Yığının en üstünde olan öğeyi ziyaret edeceksiniz, örneğin 1 ve bitişiğindeki düğümlere gideceksiniz. Bunun nedeni, 0'ın zaten ziyaret edilmiş olmasıdır. Bu nedenle, köşe 2'yi ziyaret ediyoruz.
Aşama 3)
Vertex 2'nin 4'te ziyaret edilmemiş bir yakın köşesi var. Bu nedenle, onu yığına ekliyoruz ve ziyaret ediyoruz.
Adım 4)
Son olarak, son köşe 3'ü ziyaret edeceğiz, ziyaret edilmemiş bitişik düğümleri yok. DFS algoritmasını kullanarak grafiğin geçişini tamamladık.
BFS ve DFS İkili Ağaç arasındaki fark
| BFS | DFS |
| BFS, hedefe giden en kısa yolu bulur. | DFS, bir alt ağacın en altına gider, sonra geri döner. |
| BFS'nin tam biçimi Kapsamlı Arama'dır. | DFS'nin tam biçimi İlk Derinlik Aramasıdır. |
| Ziyaret edilecek bir sonraki konumu takip etmek için bir kuyruk kullanır. | Ziyaret edilecek bir sonraki yeri takip etmek için bir yığın kullanır. |
| BFS, ağaç seviyesine göre hareket eder. | DFS, ağaç derinliğine göre hareket eder. |
| FIFO listesi kullanılarak uygulanır. | LIFO listesi kullanılarak uygulanır. |
| DFS'ye kıyasla daha fazla bellek gerektirir. | BFS'ye kıyasla daha az bellek gerektirir. |
| Bu algoritma en sığ yol çözümünü verir. | Bu algoritma, en sığ yol çözümünü garanti etmez. |
| BFS'de geriye dönük izlemeye gerek yoktur. | DFS'de geriye dönük izleme ihtiyacı vardır. |
| Sonlu döngülere asla hapsolamazsınız. | Sonsuz döngülere hapsolabilirsiniz. |
| Herhangi bir hedef bulamazsanız, çözüm bulunmadan önce birçok düğümü genişletmeniz gerekebilir. | Herhangi bir hedef bulamazsanız, yaprak düğüm geri takibi meydana gelebilir. |
BFS uygulamaları
İşte BFS Uygulamaları:
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 kapsama ağacını kolayca oluşturabilir.
P2P Ağları:
BFS, bir uçtan uca 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.
Ağ Yayını:
Yayınlanan bir paket, adresine sahip olduğu tüm düğümleri bulması ve bunlara ulaşması için BFS algoritması tarafından yönlendirilir.
DFS uygulamaları
İşte DFS'nin önemli uygulamaları:
Ağırlıklı Grafik:
Ağırlıklı bir grafikte, DFS grafik geçişi en kısa yol ağacını ve minimum kapsama ağacını oluşturur.
Bir Grafikteki Döngüyü Algılama:
DFS sırasında bir arka kenar bulursak bir grafiğin bir döngüsü vardır. Bu nedenle, grafik için DFS çalıştırmalı ve arka kenarları doğrulamalıyız.
Yol bulma:
İki köşe arasındaki yolu aramak için DFS algoritmasında uzmanlaşabiliriz.
Topolojik Sıralama:
Bu esas olarak iş grubu arasında verilen bağımlılıkları işlerini zamanlamak için kullanılır. Bilgisayar biliminde, komut çizelgeleme, veri serileştirme, mantık sentezinde, derleme görevlerinin sırasını belirlemede kullanılır.
Bir Grafiğin Güçlü Bir Şekilde Bağlı Bileşenlerini Arama:
Grafikteki her bir tepe noktasından diğer kalan tepe noktalarına bir yol olduğunda DFS grafiğinde kullanılır.
Tek Bir Çözümle Bulmacaları Çözme:
DFS algoritması, ziyaret edilen kümedeki mevcut yol üzerindeki düğümleri dahil ederek bir labirente yönelik tüm çözümleri aramak için kolayca uyarlanabilir.
ANAHTAR FARKLAR:
- BFS, hedefe giden en kısa yolu bulur, DFS ise bir alt ağacın altına gider ve ardından geriye doğru izler.
- BFS'nin tam biçimi Kapsamlı Arama iken, DFS'nin tam biçimi İlk Derinlik Aramasıdır.
- BFS, ziyaret edilecek bir sonraki konumu takip etmek için bir kuyruk kullanır. DFS ise ziyaret edilecek bir sonraki konumu takip etmek için bir yığın kullanır.
- BFS, ağaç seviyesine göre hareket ederken, DFS ağaç derinliğine göre hareket eder.
- BFS, FIFO listesi kullanılarak gerçekleştirilirken, DFS LIFO listesi kullanılarak gerçekleştirilir.
- BFS'de, sonlu döngülere asla hapsolamazsınız, oysa DFS'de sonsuz döngülere yakalanabilirsiniz.