Yan yana
Genişlik Öncelikli AramavsDerinlik Öncelikli Arama
BFS ile DFS arasındaki fark nedir?
Güncellendi 2 dk okuma7 fark
Kısaca
BFS çizgeyi kuyrukla seviye seviye gezer ve ağırlıksız çizgede en kısa yolu bulur; DFS ise bir dalda olabildiğince derine iner, sonra geri döner.
Genişlik Öncelikli Arama
Genişlik öncelikli arama, düğümleri başlangıca uzaklık sırasıyla ziyaret eden ve derine inmeden önce tüm komşuları keşfeden bir çizge gezinme algoritmasıdır.
Genişlik Öncelikli Arama sayfasını okuDerinlik Öncelikli Arama
Derinlik öncelikli arama, bir yolu gidebildiği kadar izleyip sonra geri dönerek sıradaki ziyaret edilmemiş dalı keşfeden bir çizge gezinme algoritmasıdır.
Derinlik Öncelikli Arama sayfasını okuGenişlik Öncelikli Arama ve Derinlik Öncelikli Arama karşılaştırması
| Özellik | Genişlik Öncelikli Arama | Derinlik Öncelikli Arama |
|---|---|---|
| Gezinme sırası | Seviye seviye, önce en yakın düğümler | Olabildiğince derin tek bir dal, sonra geri dönüş |
| Veri yapısı | Kuyruk (FIFO) | Yığın (LIFO) ya da özyineleme |
| En kısa yol | Ağırlıksız çizgelerde garanti | Garanti değil |
| Bellek kullanımı | Çizgenin en geniş seviyesiyle birlikte büyür | Geçerli yolun derinliğiyle birlikte büyür |
| Zaman karmaşıklığı | O(V + E) | O(V + E) |
| Çok derin çizgeler | Uzun bir dalda asla kaybolmaz | Derin özyineleme çağrı yığınını taşırabilir |
| Tipik kullanımlar | En kısa yollar, en yakın eşleşmeler, seviye sıralı gezinme | Döngü tespiti, topolojik sıralama, bulmacalar ve labirentler |
Fark, açıklamalı
Genişlik öncelikli arama (BFS) ve derinlik öncelikli arama (DFS), bir çizgenin ya da ağacın her düğümünü ziyaret etmenin iki temel yoludur. BFS önce başlangıç düğümünün tüm komşularını, sonra onların komşularını ziyaret eder ve halkalar hâlinde dışarı doğru yayılır. DFS bir komşu seçer ve çıkmaz sokağa varana kadar derine gitmeyi sürdürür, sonra geri dönüp sıradaki seçeneği dener.
Fark, her birinin arkasındaki veri yapısından gelir. BFS bir kuyruk kullanır; düğümler keşfedildikleri sırayla işlenir ve bu, her düğüme mümkün olan en az kenarla ulaşmasını garanti eder. DFS ise bir yığın kullanır, çoğu zaman özyineleme yoluyla çağrı yığınını; bu yüzden her zaman en son keşfedilen düğümden devam eder.
İkisi de O(V + E) sürede çalışır; burada V köşe (düğüm) sayısı, E kenar sayısıdır ve ikisinin de döngü içeren çizgelerde sonsuza kadar dönmemesi için bir ziyaret edilenler kümesine ihtiyacı vardır. Birçok algoritma bunların üzerine kurulur: BFS ağırlıksız çizgelerde en kısa yolları ve arkadaşın arkadaşı önerilerini besler, DFS ise döngü tespitini, topolojik sıralamayı ve labirent çözmeyi.
Sık yapılan bir yanlış, DFS'nin en kısa yolu bulduğu düşüncesidir. Bir yol bulur, ama mutlaka en kısasını değil; kenarların yol mesafeleri gibi ağırlıkları olduğunda ise ikisi de tek başına yetmez, bunun yerine Dijkstra gibi algoritmalar kullanılır.
Hangisini kullanmalısınız?
Genişlik Öncelikli Arama şu durumlarda doğru seçim:
- Ağırlıksız bir çizgede en kısa yolu bulmanız gerekiyor.
- Hedef büyük olasılıkla başlangıç düğümüne yakın.
- Düğümleri seviye seviye işlemek istiyorsunuz.
Derinlik Öncelikli Arama şu durumlarda doğru seçim:
- Bulmacalarda ya da geri izlemede olduğu gibi olası her yolu keşfetmeniz gerekiyor.
- Döngü tespit ediyor ya da bağımlılıkları sıralıyorsunuz.
- Çizge çok geniş ve tam bir seviye belleğe sığmaz.
Bir çizgenin her düğümünü ziyaret etmek
from collections import deque
def bfs(graph, start):
visited, queue = {start}, deque([start])
while queue:
node = queue.popleft() # oldest node first
print(node)
for n in graph[node]:
if n not in visited:
visited.add(n)
queue.append(n)def dfs(graph, node, visited=None):
if visited is None:
visited = set()
visited.add(node)
print(node)
for n in graph[node]:
if n not in visited:
dfs(graph, n, visited) # go deeper first
return visitedSık sorulan sorular
BFS mi DFS mi daha hızlı?
İkisi de her düğümü ve kenarı bir kez ziyaret eder, bu yüzden ikisi de O(V + E) zaman alır. Hangisinin hedefi daha erken bulacağı hedefin yerine bağlıdır: yakın hedefler için BFS, derindekiler için DFS.
BFS mi DFS mi daha çok bellek kullanır?
Geniş çizgelerde genellikle BFS, çünkü kuyruğu bir seviyenin tamamını tutabilir. DFS yalnızca geçerli yolu saklar; yine de çok derin bir çizge bu yolu uzatabilir.
BFS ve DFS ağaçlarda çalışır mı?
Evet. Bir ağaçta BFS'ye seviye sıralı gezinme de denir; DFS ise önce, ara ve sonra sıralı (preorder, inorder, postorder) gezinmeleri kapsar.