BFS ve DFS farkı, bir grafın düğümlerinin hangi sırayla keşfedildiğinde ortaya çıkar. BFS, başlangıç düğümünden komşuları katman katman bulur ve FIFO kuyruğu kullanır; DFS ise bir dal boyunca derinleşir, çıkmaza geldiğinde geri döner ve LIFO yığını ya da özyinelemeli çağrı yığınıyla ilerler.
Bu nedenle BFS, kenar geçişleri eşit kabul edilen graflarda belirli kısa yol soruları için uygun bir temel sunabilir. DFS ise bir yapıyı derinlemesine incelemek ve önceki düğümlere geri dönmek için kullanılır; iki yöntemin kesin ziyaret sırası, komşuların ele alınma sırasına bağlıdır.
BFS ve DFS farkı nedir? Temel gezinme mantığı
Graf, düğümler ve bu düğümler arasındaki kenarlardan oluşan bir yapıdır. Düğüm bir varlığı ya da durumu, kenar ise iki düğüm arasındaki ilişkiyi gösterir. Gezinmenin başladığı düğüm başlangıç düğümü olarak adlandırılır. Bir düğüme doğrudan kenarla bağlı olan düğümler ise onun komşularıdır. Yönsüz grafın kenarları iki yönde geçilebilirken yönlü grafta kenarın yönü, geçişin hangi tarafa yapılacağını belirler.
BFS, başlangıç düğümünü keşfettikten sonra önce ona bir kenar uzaklıktaki komşuları, ardından bir sonraki uzaklıktaki düğümleri işler. Böylece grafı katman katman tarar. Bu ilerleme FIFO kuyruğa dayanır: İlk giren düğüm ilk çıkar. Kenar geçişleri eşit kabul edilen bir graf üzerinde, başlangıçtan en az kenarla ulaşılabilen düğümleri bulma bağlamında BFS elverişli bir yöntemdir.
DFS ise seçtiği bir komşu üzerinden mümkün olduğunca derine ilerler. İlerlenecek ziyaret edilmemiş komşu kalmadığında önceki düğüme geri döner ve başka bir dalı dener. Bu düzen, LIFO yığınla açıklanabilir: Son giren düğüm ilk çıkar. DFS, açıkça oluşturulan bir yığınla ya da tamamlanmamış çağrıları tutan özyinelemeli çağrı yığınıyla uygulanabilir.
Bir düğüm BFS'de kuyruğa eklenirken, DFS'de düğüme ilk girildiğinde ziyaret edildi olarak işaretlenir. Bu işaret, özellikle döngü içeren graflarda aynı düğümün tekrar tekrar işlenmesini önler. Özyineleme, bir fonksiyonun aynı işlemi sürdürmek için kendisini çağırmasıdır. Çağrı tamamlandığında kontrol, çağrıyı yapan önceki fonksiyona döner.
Yönsüz bir graf, her düğüm çifti arasında en az bir yol bulunuyorsa bağlı grafdır. Bağlantısız graf ise birden fazla bağlı bileşen içerir. Tek bir başlangıç düğümünden yapılan BFS veya DFS yalnızca başlangıçtan erişilebilen bileşeni tarar. Diğer bileşenleri incelemek için ziyaret edilmemiş düğümlerden yeni gezinmeler başlatmak gerekir.
Komşuluk listesindeki sıra, eşit seçenekler arasındaki kesin ziyaret sırasını değiştirebilir. Algoritmanın temel mantığı aynı kalır; ancak BFS'de düğümlerin kuyruğa giriş sırası, DFS'de seçilen dal ve geri dönüş noktaları farklılaşabilir.
Bu kavramları küçük örnekler üzerinden sınamak ve algoritmik düşünme pratiği yapmak için Algoritmik Düşünme Testi kullanılabilir.
Aynı küçük graf üzerinde BFS ve DFS ziyaret sırası nasıl oluşur?
Şimdi başlangıç düğümü A olan, yönsüz ve bağlı bir grafı ele alalım. Komşuluklar soldan sağa şu sırada işlenecektir: A: B, C, B: A, D, E, C: A, F, D: B, E: B, F, F: C, E.
BFS'de bir düğüm kuyruğa eklenirken ziyaret edildi işareti konur. Özyinelemeli DFS'de ise işaret, düğüme ilk girildiği anda verilir. DFS satırlarında özyineleme yolu, o anda tamamlanmamış çağrı zincirini gösterir.
| Algoritma | Adım | İşlenen düğüm | Komşu işlemi | Kuyruk ya da özyineleme yolu | O ana kadarki ziyaret sırası |
|---|---|---|---|---|---|
| BFS | 1 | A | B ve C işaretlenip kuyruğa eklenir. | B, C |
A |
| BFS | 2 | B | A atlanır; D ve E işaretlenip kuyruğa eklenir. | C, D, E |
A, B |
| BFS | 3 | C | A atlanır; F işaretlenip kuyruğa eklenir. | D, E, F |
A, B, C |
| BFS | 4 | D | B zaten ziyaret edilmiş, atlanır. | E, F |
A, B, C, D |
| BFS | 5 | E | B ve F zaten ziyaret edilmiş, atlanır. | F |
A, B, C, D, E |
| BFS | 6 | F | C ve E zaten ziyaret edilmiş, atlanır. | boş |
A, B, C, D, E, F |
| DFS | 1 | A | A işaretlenir; B ziyaret edilmemiş olduğu için içine girilir. | A |
A |
| DFS | 2 | B | B işaretlenir; A atlanır, D'ye girilir. | A>B |
A, B |
| DFS | 3 | D | D işaretlenir; B atlanır ve D'den B'ye geri dönülür. | A>B>D |
A, B, D |
| DFS | 4 | E | B çağrısına dönülür; E işaretlenip içine girilir. | A>B>E |
A, B, D, E |
| DFS | 5 | F | F işaretlenir; C'ye girilir, dönüşte E atlanır. | A>B>E>F |
A, B, D, E, F |
| DFS | 6 | C | C işaretlenir; A ve F atlanır, dönüşte A'nın C komşusu da atlanır. | A>B>E>F>C |
A, B, D, E, F, C |
Tablo, komşuluk sırasının sonucu nasıl etkilediğini gösterir. Kenar geçişleri eşit kabul edildiğinde A'dan F'ye iki kenarlı A-C-F yolu bulunur. Buna rağmen DFS önce A, B, E, F dalına ilerleyebilir; çünkü DFS en kısa yolu seçmek yerine seçilen komşuyu derinlemesine izler. BFS ise A'nın komşularını ilk katmanda keşfeder ve C işlenirken F'yi ikinci katmanda bulur. Bu nedenle BFS belirli koşullarda kısa yol aramasına, DFS ise derinleşme ve geri izleme gerektiren gezinmelere uygun olabilir; yöntemlerden biri her problemde otomatik olarak üstün değildir.
BFS ve DFS sözde kodu ve çalışan Python örneği
Sözde kod, iki algoritmanın veri yapısını nasıl kullandığını görünür kılar. BFS, yeni düğümleri FIFO kuyruğun sonuna ekler ve baştan çıkarır. DFS ise bir komşuya girer, o dalı derinlemesine izler ve çıkmaza ulaştığında geri döner.
BFS sözde kodu
BFS(G, başlangıç)
ziyaret_edildi = {başlangıç}
kuyruk = FIFO()
kuyruk.ekle(başlangıç)
kuyruk boş değilken
düğüm = kuyruk.çıkar()
düğümü işle
her komşu için
eğer komşu ziyaret_edilmediyse
ziyaret_edildi'ye ekle(komşu)
kuyruk.ekle(komşu)BFS'de bir komşu kuyruğa eklenmeden önce ziyaret edildi olarak işaretlenir. Böylece aynı düğümün farklı komşular tarafından tekrar tekrar kuyruğa alınması önlenir. popleft() işlemi kuyruğun başındaki düğümü çıkarırken yeni düğümler sona eklendiği için FIFO davranışı oluşur.
Özyinelemeli DFS sözde kodu
DFS(G, düğüm, ziyaret_edildi)
ziyaret_edildi'ye düğümü ekle
düğümü işle
her komşu için
eğer komşu ziyaret_edilmediyse
DFS(G, komşu, ziyaret_edildi)DFS'de düğüm, fonksiyona girildiği anda işaretlenir ve işlenir. Özyinelemeli çağrı yığını, tamamlanmamış dalları tutar. Bir düğümün yeni komşusu kalmadığında çağrı önceki düğüme döner ve sıradaki komşu incelenir.
Çalışan Python örneği
Aşağıdaki kod, aynı yönsüz komşuluk haritası üzerinde BFS ve özyinelemeli DFS çalıştırır. collections.deque, Python standart kütüphanesindeki FIFO kuyruk işlemleri için kullanılır.
from collections import deque
graph = {
"A": ["B", "C"],
"B": ["A", "D", "E"],
"C": ["A", "F"],
"D": ["B"],
"E": ["B", "F"],
"F": ["C", "E"]
}
def bfs(graph, start):
visited = {start}
order = []
queue = deque([start])
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return order
def dfs(graph, start):
visited = set()
order = []
def visit(node):
visited.add(node)
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visit(neighbor)
visit(start)
return order
print("BFS:", bfs(graph, "A"))
print("DFS:", dfs(graph, "A"))Beklenen çıktı şöyledir:
BFS: ['A', 'B', 'C', 'D', 'E', 'F']
DFS: ['A', 'B', 'D', 'E', 'F', 'C']BFS'de A'dan sonra B ve C kuyruğa girer. B önce çıkarıldığı için D ve E, C'nin F düğümünü eklemesinden önce işlenir. DFS'de ise A'dan B'ye, B'den D'ye derinleşilir. D'nin yeni komşusu kalmayınca B'ye dönülür, ardından E ve F üzerinden C'ye ulaşılır. Bu çıktı, komşuluk listelerinin sırasına bağlıdır.
Özyinelemeli DFS yerine açık bir yığın kullanılırsa, aynı ziyaret sırasını korumak için her düğümün komşularını ters sırada yığına eklemek gerekir. Başlangıç düğümünden yapılan bu fonksiyonlar yalnızca başlangıçtan erişilebilen bağlı bileşeni tarar. Bağlantısız grafın tamamını gezmek için tüm düğümler üzerinde dış döngü kurulur ve henüz ziyaret edilmemiş her düğümde BFS veya DFS yeniden başlatılır.
Katman, derinleşme ve karmaşıklık: hangi durumda hangisi seçilir?
BFS'nin temel özelliği katmanlı ilerlemesidir. Başlangıç düğümü 0. katmanda kabul edilir; doğrudan komşular 1. katmana, onlardan bir kenar uzaktaki düğümler 2. katmana yerleşir. Kenar ağırlıkları yoksa veya bütün geçişler eşit maliyetli kabul ediliyorsa BFS, başlangıçtan erişilebilir bir hedefe minimum kenar sayısıyla ulaşmayı destekler.
Ağırlıklı graflarda bu sonuç doğrudan geçerli değildir. Düz BFS veya DFS, toplam ağırlık bakımından en kısa yolu otomatik olarak bulmaz. DFS bir dalda derinleşir, çıkmazda geri döner ve ilk bulduğu yol genel olarak minimum kenar sayılı ya da minimum ağırlıklı yol olmak zorunda değildir.
- Hedef: Tek bir düğüme minimum kenar sayısıyla ulaşmak istiyorsan, uygun koşullarda BFS değerlendirilebilir. Bütün dalları veya bir bileşeni incelemek için DFS de kullanılabilir.
- Beklenen yol özelliği: Ağırlıksız veya eşit maliyetli geçişlerde BFS minimum kenar mesafesi özelliğini taşır. Ağırlıklı graflarda ise BFS ve DFS sonucu, ağırlık toplamı bakımından en kısa yol anlamına gelmez.
- İstenen ziyaret sırası: Katman önceliği BFS'nin, dal önceliği DFS'nin doğal ilerleyişidir. Komşuluk sırası kesin ziyaret dizisini değiştirir ve DFS'nin seçtiği ilk yolu etkileyebilir. Ağırlıksız graf koşulunda BFS'nin minimum kenar mesafesi özelliği korunur.
- Bellek kullanımı: BFS geniş bir ön cepheyi kuyruğunda, DFS ise derin bir yolu çağrı yığınında taşıyabilir. Gerçek bellek kullanımı grafın şekline ve gösterimine bağlıdır. Bu nedenle iki algoritmadan birinin her durumda daha az bellek kullandığı söylenemez.
Zaman ve yardımcı bellek karmaşıklığı
Komşuluk listesiyle gösterilen yönlü veya yönsüz bir graf için V düğüm, E kenar sayısını ifade etsin. Her düğümün bir kez ziyaret edildiği, komşuluk girdilerinin tarandığı ve ziyaret kümesinde üyelik kontrolünün ortalama sabit zamanda yapıldığı varsayımıyla BFS ve DFS'nin zaman karmaşıklığı O(V+E)'dir.
Ziyaret kümesi, kuyruk veya özyinelemeli çağrı yığını ve sonuç sırası için gereken yardımcı bellek en kötü durumda O(V)'dir. Grafın komşuluk depolaması bu yardımcı bellek hesabına dahil değildir. Tek başlangıçlı taramada V ve E, erişilebilir altgrafı ifade eder. Tüm bileşenleri dolaşan dış döngü kullanıldığında toplam grafın V ve E değerleri dikkate alınır. Komşuluk matrisi kullanılırsa komşu taramaları en kötü durumda O(V²) zaman alabilir.
Algoritma, veri yapıları ve bilgisayar bilimi konularındaki diğer açıklamalar için Berk Akademi Blogu'ndaki algoritma yazılarına göz atabilirsin.
Sık Sorulan Sorular
BFS hangi koşullarda en kısa yolu bulur?
BFS, hedef başlangıçtan erişilebiliyorsa ve kenarlar ağırlıksız ya da eşit maliyetli kabul ediliyorsa minimum kenar sayılı yolu bulur. Kenar ağırlıkları farklıysa düz BFS sonucu toplam maliyet bakımından en kısa yol olarak kabul edilmez.
Bağlantısız bir grafın bütün düğümleri BFS veya DFS ile nasıl ziyaret edilir?
Tüm düğümler üzerinde dış döngü kurulur. Ziyaret edilmemiş bir düğüm bulunduğunda aynı ziyaret kümesi kullanılarak BFS veya DFS o düğümden yeniden başlatılır. Böylece her bağlı bileşen ayrı bir taramayla gezilir.
Komşuluk sırası değişince BFS ve DFS'nin ziyaret sırası neden değişir?
Her iki algoritma da komşuları komşuluk listesinde bulunan sırayla ele alır. Bu sıra, BFS'de kuyruğa eklenme düzenini, DFS'de ise özyinelemeli çağrının izleyeceği dalı değiştirir. Bu nedenle kesin ziyaret dizisi değişebilir; BFS'nin ağırlıksız graflardaki minimum kenar mesafesi özelliği ise korunur.
BFS ve DFS seçimini, grafın yapısı, aranan yol özelliği ve istenen gezinme sırasını birlikte değerlendirerek yapmak en sağlıklı yaklaşımdır.
