Genişlik öncelikli arama (BFS)
Bir grafı katman katman gezer. Sıradaki düğüme bir kuyruk karar verir, bu yüzden en yakın düğümler hep önce ziyaret edilir.
- süre O(V + E)
- bellek O(V)
- kuyruk kullanır
Bunlar ne demek?
- Düğüm: grafın bir noktası, burada harfli bir daire olarak çizilir.
- Kenar: iki düğümü birleştiren çizgi. Burada iki yönde de üzerinden geçilebilir.
- Komşular: bir düğüme bir kenarla bağlı düğümler. Alfabetik sırayla bakılırlar.
- Kuyruk: ilk giren ilk çıkar. BFS her zaman en uzun süredir bekleyen düğümü alır.
- Yığıt: son giren ilk çıkar. DFS her zaman en son ulaştığı düğümden devam eder.
- V ve E: düğüm ve kenar sayısı. O(V + E), her düğümün ve her kenarın sabit sayıda işlendiği anlamına gelir.
- kuyrukta
- şimdiki
- bitti
- arama ağacı kenarı
- atlanan kenar
Arama A düğümünden başlar. Oynat tuşuna basın veya adım adım ilerleyin.
Boşluk: oynat veya duraklat. Sol ve sağ oklar: adım adım. Home ve End: atla.
Şunu deneyin: İki parçalı grafı seçin. Başlangıca bağlı olmayan düğümlere hiç ulaşılmaz.
Nasıl çalışır
BFS başlangıç düğümünü bir kuyruğa koyar. Sonra tekrar tekrar kuyruğun önündeki düğümü alır ve yeni komşularını kuyruğun sonuna ekler. Kuyruk geliş sırasına göre çalışır, bu yüzden bir kenar uzaktaki her düğüm, iki kenar uzaktaki herhangi bir düğümden önce biter. Bir düğümün yanındaki sayı, başlangıca olan uzaklığıdır: ona ulaşmak için gereken en az kenar sayısı.
Ne zaman iyi bir seçimdir
En az adımlı yolu bulmanız gerektiğinde BFS kullanın: bir bulmacada en az hamle, bir ağda en az atlama, size iki bağlantı uzaklıktaki kişiler. Büyük bir grafta kuyruk uzayabilir, çünkü aynı anda bütün bir katmanı tutar.