Genişlik öncelikli arama (BFS)

Bir gölete taş atın: dalgalar halkalar hâlinde eşit şekilde yayılır. Genişlik öncelikli arama bir grafı aynı şekilde keşfeder: önce başlangıçtan bir adım uzaktaki her şey, sonra iki adım uzaktaki her şey ve böyle devam eder. En kısa yolları bulmasını sağlayan da bu basit sıradır.

Harflerle adlandırılmış düğümleri başlangıç düğümüne uzaklıklarına göre halkalar hâlinde renklendirilmiş bir graf ve altında çizilmiş bir düğüm kuyruğu
Harflerle adlandırılmış düğümleri başlangıç düğümüne uzaklıklarına göre halkalar hâlinde renklendirilmiş bir graf ve altında çizilmiş bir düğüm kuyruğu

Temel fikir

Graf, kenarlarla birbirine bağlanmış düğümlerden oluşan bir kümedir: yerler ve yollar, insanlar ve arkadaşlıklar, bir labirentin kareleri ve aralarındaki geçitler. Genişlik öncelikli arama şu soruyu yanıtlar: buradan başlayarak nereye ulaşabilirim ve en az kaç adımda? Ziyaret edilecek düğümlerin bir kuyruğunu tutar. Düğümleri önden alıp yenilerini sona eklemek, düğümlerin keşfedildikleri sırayla işlenmesini sağlar.

Adım adım

Başlangıcı uzaklık 0 ile kuyruğa koyun. Öndeki düğümü alın. Görülmemiş her komşu için uzaklığını mevcut düğümünkinden bir fazla olarak kaydedin, mevcut düğümü ona ulaşılan yol olarak hatırlayın ve onu kuyruğun sonuna ekleyin. Daha önce görülen komşuları atlayın. Kuyruk boşalana ya da hedefe ulaşılana kadar tekrarlayın.

Bir örnek

A–B, A–C, B–D, C–D, C–E ve D–F kenarlarına sahip bir graf alın ve A'dan başlayın. A kuyruktan alınınca B ve C bulunur, uzaklıkları 1'dir. B alınınca D bulunur, uzaklığı 2'dir. C alınınca D'nin zaten görüldüğü anlaşılır ve E bulunur, uzaklığı 2'dir. D alınınca F bulunur, uzaklığı 3'tür. E ve F yeni bir şey bulmaz ve kuyruk boşalır. Hatırlanan düğümleri F'den geriye izlemek F ← D ← B ← A verir; yani A'dan F'ye bir en kısa yol, üç kenar uzunluğundaki A → B → D → F yoludur.

Uzaklıklar neden doğru

Uzaklığı 1 olan her düğüm, uzaklığı 2 olan herhangi bir düğümden önce kuyruğa girer; uzaklığı 2 olan her düğüm de uzaklığı 3 olan herhangi bir düğümden önce girer ve böyle devam eder. Çünkü bir düğümün komşuları ancak düğümün kendisi kuyruktan çıktığında kuyruğa eklenir. Bu yüzden bir düğüme ulaşan ilk yol en az kenarlı yoldur ve BFS hiçbir uzaklığı düzeltmek zorunda kalmaz. Her düğüm bir kez alınır ve her kenara iki ucundan bakılır, bu yüzden iş düğüm sayısı ile kenar sayısının toplamıyla birlikte artar.

Tarihçe ve kullanım alanları

Konrad Zuse genişlik öncelikli aramayı 1945'te, ancak 1972'de yayımlanan Plankalkül dili üzerine çalışmasında tanımladı. Edward F. Moore onu 1959'da bir labirentten çıkan en kısa yolu bulmak için yeniden keşfetti, C. Y. Lee de 1961'de devre kartlarında kabloların yolunu belirlemek için kullandı. Bugün bulmacalarda en az hamleyi, sosyal ağlarda ayrılma derecelerini, bir web örümceğinin ilk ulaştığı sayfaları ve oyunlarda en yakın boş hücreyi bulur. Kenarların uzunlukları olduğunda Dijkstra algoritması onu genelleştirir.

Konrad Zuse (ortada, gözlüklü) ve Heinz Billing (solda), Münih’teki SYSTEMS ’91 fuarında. Zuse, 1945’te Plankalkül dili üzerindeki, ancak 1972’de yayımlanan çalışmalarında genişlik öncelikli aramayı tarif etti.
Konrad Zuse (ortada, gözlüklü) ve Heinz Billing (solda), Münih’teki SYSTEMS ’91 fuarında. Zuse, 1945’te Plankalkül dili üzerindeki, ancak 1972’de yayımlanan çalışmalarında genişlik öncelikli aramayı tarif etti.

Keşfedin

Uygulamayı açın ve Adım'a basın. Şu an ziyaret edilen düğüm vurgulanır, kuyrukta bekleyen düğümler mavi, ziyaret edilmiş düğümler yeşildir ve her birinde uzaklığı yazar. Kuyruk, grafın altında önü başta olacak şekilde gösterilir. Tıklamayı Hedef'e çevirip bir düğüm seçerek orada durun ve en kısa yolu görün ya da daha çok düğüm ve kenarı olan yeni bir graf oluşturun.

Sık sorulan sorular

BFS'nin zaman karmaşıklığı nedir?

V düğüm (vertices) ve E kenar (edges) için O(V + E): her düğüm kuyruğa bir kez girer ve bir kez çıkar, her kenar da iki ucundan incelenir. Kuyruk ve uzaklıklar için O(V) ek bellek gerekir.

BFS neden kuyruk kullanır?

Çünkü ilk giren ilk çıkar kuralı düğümleri keşfedildikleri sırada, yani uzaklıklarının sırasında tutar. Bunun yerine yığın kullanılsaydı arama önce derine dalardı: bu, derinlik öncelikli aramadır.

BFS ağırlıklı graflarda en kısa yolları bulabilir mi?

Genel olarak hayır: kenarları sayar, uzunluklarını değil. Negatif kenarı olmayan ağırlıklı graflar için Dijkstra algoritmasını kullanın. Her ağırlık 0 ya da 1 ise 0-1 BFS adlı bir türevi işe yarar.

BFS nerelerde kullanılır?

Bulmacaları ve labirentleri en az hamleyle çözmekte, sosyal ağlarda arkadaşların arkadaşlarını bulmakta, web'i seviye seviye taramakta, ağlarda yayın yapmakta ve maksimum akış bulma gibi başka algoritmaların yapı taşı olarak.

Denemeye hazır mısınız?

PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.

Genişlik öncelikli aramayı deneyin