Veri Yapısı - Genişlik İlk Geçiş
Genişlik İlk Arama (BFS) algoritması, geniş bir hareketle bir grafiği gezer ve herhangi bir yinelemede bir çıkmaz meydana geldiğinde, bir aramayı başlatmak için sonraki tepe noktasını almayı hatırlamak için bir kuyruk kullanır.
Yukarıda verilen örnekte olduğu gibi, BFS algoritması önce A'dan B'ye, E'den F'ye, sonra C'ye ve en son olarak D'ye gider. Aşağıdaki kuralları kullanır.
Rule 1- Bitişikteki ziyaret edilmemiş köşeyi ziyaret edin. Ziyaret edildi olarak işaretleyin. Gösterin. Bir sıraya ekleyin.
Rule 2 - Bitişik köşe bulunamazsa, ilk tepe noktasını kuyruktan çıkarın.
Rule 3 - Sıra boşalana kadar Kural 1 ve Kural 2'yi tekrarlayın.
| Adım | Geçiş | Açıklama |
|---|---|---|
| 1 |
|
Sırayı başlatın. |
| 2 |
|
Ziyaretten başlıyoruz S (başlangıç düğümü) ve ziyaret edildi olarak işaretleyin. |
| 3 |
|
Daha sonra ziyaret edilmemiş bir bitişik düğüm görüyoruz. S. Bu örnekte, üç düğümümüz var ancak alfabetik olarak seçiyoruzA, ziyaret edildi olarak işaretleyin ve sıralayın. |
| 4 |
|
Ardından, ziyaret edilmeyen bitişik düğüm S dır-dir B. Ziyaret edildi olarak işaretler ve sıraya koyarız. |
| 5 |
|
Ardından, ziyaret edilmeyen bitişik düğüm S dır-dir C. Ziyaret edildi olarak işaretler ve sıraya koyarız. |
| 6 |
|
Şimdi, Sziyaret edilmemiş bitişik düğümler olmadan bırakılır. Böylece sırayı çözer ve buluruzA. |
| 7 |
|
Nereden A sahibiz Dziyaret edilmemiş bitişik düğüm olarak. Ziyaret edildi olarak işaretler ve sıraya koyarız. |
Bu aşamada, işaretlenmemiş (ziyaret edilmemiş) düğümler kalmadı. Ancak algoritmaya göre, tüm ziyaret edilmemiş düğümleri elde etmek için kuyruğundan çıkarmaya devam ediyoruz. Kuyruk boşaldığında program biter.
Bu algoritmanın C programlama dilinde uygulanması burada görülebilir .