BFS (genişlik öncelikli arama), hem basit hem de gelişmiş algoritmalarda sıklıkla kullanılan bir grafik çaprazlama yöntemidir. Genişlik Öncelikli Arama, kaynak düğümden başlayarak ve kademeli olarak ondan uzaklaşarak grafiğin bireysel seviyeleri arasında adım atarak çalışır. Bu, animasyonda açıkça gösterilmiştir.
Basit bir BFS yazmak için, bir kuyrukla çalışabilmeniz, baştan alıp sona koymanıza olanak tanıyan bir veri yapısı ve ayrıca formda bir grafik depolayabilmeniz gerekir. bir komşuluk listesi.
Algoritmanın resmi açıklaması
1) Aramanın başladığı köşe numarasını başlangıçta boş olan kuyruğa yerleştirin.
2) Kuyruğun başından U köşesini çıkarın ve ayrı bir dizide kullanılmış olarak işaretleyin.
3) Kuyruğun sonuna, U köşesinden kenarı kullanarak ulaşabileceğimiz ve henüz işaretlenmemiş tüm köşeleri ekleyin.
4) Kuyruk boşsa, bağlı grafiğin tüm düğümleri taranmıştır, aksi halde 2. adıma dönün.
İşin zorluğu
En kötü durumda, algoritma grafiğin tüm düğümlerini ziyaret ettiğinden, grafiği bitişik listeler biçiminde saklarken, algoritmanın zaman karmaşıklığı O(|V| + |E|), burada V kümedir grafiğin köşelerinin sayısı ve E kenarların kümesidir. ;
Başka bir deyişle, algoritma kenar sayısı + köşe sayısı için en kötü durumda çalışır.