Genişlik Öncelikli Arama (BFS)

Genişlik öncelikli arama (BFS) nedir?

Breadth-first search (BFS), bir graf veya ağaç yapısını katman katman dolaşan temel bir arama algoritmasıdır. Başlangıç düğümünden işe başlar, önce o düğümün tüm doğrudan komşularını ziyaret eder, ardından komşuların komşularına geçer. Yani aramayı derinlemesine değil, genişlemesine yürütür: bir seviyedeki tüm düğümler bitmeden bir sonraki seviyeye geçmez.

Bu "önce en yakınlar" davranışı BFS'i birçok klasik problemde ayrı bir yere koyar. Çünkü düğümleri başlangıca olan uzaklık sırasına göre keşfeder.

Nasıl çalışır?

BFS'in kalbinde bir FIFO (first-in, first-out) queue vardır:

• Başlangıç düğümünü queue''ya ekle ve ziyaret edildi olarak işaretle.
• Queue''nun başındaki düğümü çıkar, henüz ziyaret edilmemiş komşularını queue''ya ekle ve her birini işaretle.
• Queue boşalana (ya da hedef bulunana) kadar tekrarla.

visited (ziyaret edildi) kümesi kritik bir rol oynar: graflar döngü içerebilir ve bu küme olmadan algoritma aynı düğümleri tekrar tekrar işleyip sonsuz döngüye girer. Komşuluk listesiyle zaman karmaşıklığı O(V + E), bellek maliyeti ise en kötü durumda O(V)''dir (V düğüm, E kenar sayısı).

Neden önemli?

BFS''in en büyük gücü şu: ağırlıksız bir grafta başlangıçtan her düğüme giden en kısa yolu, yani en az kenarla ulaşılan yolu garanti eder. Düğümler zaten uzaklık sırasına göre, yakından uzağa doğru keşfedildiği için ilk ulaşıldıkları an en kısa mesafeyle ulaşılmış olurlar. Bu basit garanti, BFS''i yol bulma problemlerinde ilk akla gelen yöntem yapar.

Kullanım alanları

• Ağırlıksız graflarda en kısa yol hesabı
• Web crawler''ların sayfaları link link gezmesi
• Sosyal ağlarda iki kişi arasındaki bağlantı mesafesi ("kaç adım uzakta")
• Ağ yayını (broadcast) ve eş-eş dağıtım senaryoları
• Oyun ve bulmaca durum uzaylarında en az hamleli çözümü bulma

DFS ile farkı net: DFS bir stack kullanır ve bir dalı sonuna kadar iner; BFS ise queue kullanır ve seviye seviye yayılır. En kısa yol garantisi BFS''te vardır, DFS''te yoktur.