BFS ve DFS – Aralarındaki Fark
Sarah Chen
BFS ve DFS Arasındaki Temel Fark
- BFS hedefe giden en kısa yolu bulurken DFS bir alt ağacın altına gider ve ardından geriye doğru izler.
- BFS'nin tam biçimi Genişlik Öncelikli Arama'dır, DFS'nin tam biçimi ise Derinlik Öncelikli Arama'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 geçiş yaparken, DFS ağaç derinliğine göre geçiş yapar.
- BFS, bir FIFO listesi kullanılarak uygulanır; Öte yandan DFS, bir LIFO listesi kullanılarak uygulanır.
- BFS'de asla sonlu döngülere hapsolamazsınız, oysa DFS'de sonsuz döngülere hapsolabilirsiniz.
BFS nedir?
BFS, veriyi grafiklemek veya ağaç veya geçiş yapılarını aramak için kullanılan bir algoritmadır. Algoritma, bir grafikteki tüm anahtar düğümleri doğru bir genişlikte biçimde etkin 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ünü ziyaret edip işaretledikten sonra, ziyaret edilmemiş en yakın düğümlere doğru hareket eder ve bunları 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. BFS'nin tam biçimi Genişlik öncelikli aramadır.
DFS nedir?
DFS, grafikleri veya ağaçları derinliğe doğru bulmak veya bunlar arasında geçiş yapmak için kullanılan bir algoritmadır. Algoritmanın yürütülmesi kök düğümde başlar ve geri izlemeden önce her bir dalı araştırır. Herhangi bir yinelemede bir çıkmaz nokta göründüğünde hatırlamak, sonraki köşeyi almak ve bir arama başlatmak için yığın veri yapısını kullanır. DFS'nin tam biçimi Derinlik öncelikli aramadır.
BFS ve DFS İkili Ağacı arasındaki fark
İşte BFS ve DFS arasındaki önemli farklar.
| BFS | DFS |
|---|---|
| BFS hedefe giden en kısa yolu bulur. | DFS bir alt ağacın altına gider ve ardından geriye doğru izler. |
| BFS'nin tam biçimi Genişlik Öncelikli Arama'dır. | DFS'nin tam biçimi Derinlik İlk Arama'dır. |
| Ziyaret edilecek bir sonraki konumu takip etmek için bir kuyruk kullanır. | Ziyaret edilecek bir sonraki konumu takip etmek için bir yığın kullanır. |
| BFS ağaç seviyesine göre geçiş yapar. | 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 geri izlemeye gerek yoktur. | DFS'de geri izleme ihtiyacı vardır. |
| Hiçbir zaman sonlu döngülere 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ün geri izlemesi meydana gelebilir. |
BFS örneği
Aşağıdaki BFS örneğinde 6 köşesi olan bir grafik kullandık.
BFS örneği
) 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.
DFS örneği
Aşağıdaki DFS örneğinde 5 köşesi olan yönlendirilmemiş bir grafik kullandık.
) 1 Adım
0. köşeden başladık. Algoritma, onu ziyaret edilen listeye koyarak ve aynı anda tüm bitişik köşelerini veri yapısı yığın denir.
) 2 Adım
Yığının en üstünde yer alan elemanı örneğin 1’i ziyaret edecek ve onun bitişik düğümlerine gideceksiniz. Bunun nedeni 0'ın zaten ziyaret edilmiş olmasıdır. Bu nedenle 2. köşeyi ziyaret ediyoruz.
) 3 Adım
Vertex 2'nin 4'te ziyaret edilmemiş yakın bir köşesi var. Bu nedenle bunu yığına ekleyip ziyaret ediyoruz.
) 4 Adım
Son olarak son köşe 3'ü ziyaret edeceğiz, ziyaret edilmemiş bitişik düğümleri yoktur. Grafiğin geçişini DFS algoritmasını kullanarak tamamladık.
BFS Uygulamaları
İşte BFS Uygulamaları:
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.
Ağ Yayıncılığı
Yayınlanan bir paket, adresine sahip olduğu tüm düğümleri bulmak ve ulaşmak 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 yayılan ağacı oluşturur.
Grafikteki Döngüyü Tespit Etme
DFS sırasında bir arka kenar bulursak 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
Öncelikle iş grupları arasında verilen bağımlılıklardan işleri planlamak için kullanılır. Bilgisayar bilimlerinde talimat planlamada, veri serileştirmede, mantık sentezinde, derleme görevlerinin sırasının belirlenmesinde kullanılır.
Bir Grafiğin Güçlü Bağlantılı Bileşenlerini Arama
DFS grafiğinde, grafikteki her köşeden diğer kalan köşelere bir yol olduğunda kullanılır.
Bulmacaları Tek Bir Çözümle Çözmek
DFS algoritması, ziyaret edilen kümedeki mevcut yol üzerindeki düğümleri dahil ederek bir labirentin tüm çözümlerini arayacak şekilde kolayca uyarlanabilir.