BFS Algoritması graflarda arama algoritmalarından bir tanesidir. Temel hedefi graftaki tüm düğümleri gezmektir. Bu algoritma ağaçlarda da kullanılabilir. Mantığı Aynıdır.
 |
| Gelişmiş Graf Yapısı |
BFS Algoritması
1. Adım: Başlangıç düğümü seç, kuyruğa ekle, düğümü beklemede olarak işaretle
2. Adım: Kendine komşu olan düğümleri kuyruğa ekle, eklenen düğümleri beklemede olarak işaretle
3. Adım: Tüm komşuları kuyruğa eklenmiş olan düğümü ziyaret edilmiş olarak işaretle ve ekrana bas.
4. Adım: kuyruktan eleman çıkar ve top elemanı için aynı adımları uygula.
BFS Algoritması Adım Adım Uygulama
 |
| Graf Yapısı |
1. Adım
Başlangıç düğümü seçilir(A) ve kuyruğa eklenir.
A Düğümü Beklemede olarak işaretlenir
Mevcut Kuyruk Yapısı [front=> A => rear]
2. Adım
Kuyruktan Eleman çıkarılır, Çıkartılan Eleman (A) Ziyaret Edildi olarak işeretlenir.
A düğümünün komşuları kuyruğa eklenir (S, B)
Eklenen Düğümler Beklemede olarak işaretlenir.
Mevcut Kuyruk Yapısı [front=> S, B => rear]
Ziyaret Edilen Düğümler [A]
Beklemede Olan Düğümler [S,B]
3. Adım
Kuyruktan eleman çıkartılır, çıkartılan eleman (S) Ziyaret Edildi olarak işaretlenir
S düğümünün Komşuları kuyruğa eklenir. (C,G)
Eklenen düğümler Beklemede olarak işaretlenir
Mevcut Kuyruk Yapısı [front=> B, C, G => rear]
Ziyaret Edilen Düğümler [A, S]
Beklemede Olan Düğümler [B, C, G]
4. Adım
Kuyruktan eleman çıkartılır. Çıkartılan Eleman (B) Ziyaret Edildi olarak işaretlenir.
B düğümünün komşusu olmadığından, ekleme yapılmaz. (A düğümü ziyaret edildiğinden eklenmez)
Mevcut Kuyruk Yapısı [front=> C, G => rear]
Ziyaret Edilen Düğümler [A, S, B]
Beklemede Olan Düğümler [C, G]
5. Adım
Kuyruktan eleman çıkartılır. Çıkartılan Eleman (C) Ziyaret Edildi olarak işaretlenir.
C düğümünün Komşuları kuyruğa eklenir. (D, E, F)
Eklenen düğümler beklemede olarak işaretlenir.
Mevcut Kuyruk Yapısı [front=> G, D, E, F => rear]
Ziyaret Edilen Düğümler [A, S, B, C]
Beklemede Olan Düğümler [G, D, E, F]
6. Adım
Kuyruktan eleman çıkartılır. Çıkartılan Eleman (G) Ziyaret Edildi olarak işaretlenir.
G düğümünün komşuları kuyruğa eklenir. (H)
Eklenen düğümler beklemede olarak işaretlenir.
Mevcut Kuyruk Yapısı [front=> D, E, F, H => rear]
Ziyaret Edilen Düğümler [A, S, B, C, G]
Beklemede Olan Düğümler [D, E, F, H]
7. Adım
Kuyruktan Eleman Çıkartılır. Çıkartılan Eleman (D) Ziyaret Edildi olarak işaretlenir.
D düğümünün Komşusu olmadığından ekleme yapılmaz.
Mevcut Kuyruk Yapısı [front=> E, F, H => rear]
Ziyaret Edilen Düğümler [A, S, B, C, G, D]
Beklemede Olan Düğümler [E, F, H]
8. Adım
Kuyruktan Eleman Çıkartılır. Çıkartılan Eleman (E) Ziyaret Edildi olarak işaretlenir.
E düğümünün komşusu olmadığından ekleme yapılmaz.
Mevcut Kuyruk Yapısı [front=> F, H => rear]
Ziyaret Edilen Düğümler [A, S, B, C, G, D, E]
Beklemede Olan Düğümler [F, H]
9. Adım
Kuyruktan Eleman Çıkartılır. Çıkartılan Eleman (F) Ziyaret Edildi olarak işaretlenir.
F düğümünün komşusu olmadığından ekleme yapılmaz.
Mevcut Kuyruk Yapısı [front=> H => rear]
Ziyaret Edilen Düğümler [A, S, B, C, G, D, E, F]
Beklemede Olan Düğümler [H]
10. Adım
Kuyruktan Eleman Çıkartılır. Çıkartılan Eleman (H) Ziyaret Edildi olarak işaretlenir.
H düğümünün komşusu olmadığından ekleme yapılmaz.
Mevcut Kuyruk Yapısı [front=> NULL=> rear]
Ziyaret Edilen Düğümler [A, S, B, C, G, D, E, F, H]
Beklemede Olan Düğümler [NULL]
Beklemede olan düğüm kalmadığına göre işlem bitmiştir demektir. Ziyaret edilen düğümler kullanıcıya çıktı olarak verilir. Bu çıktı, BFS algoritması ile grafın dolaşılma şeklini gösterir.
A => S => B => C => G => D => E => F => H
Mutlaka Okuyun!
Etiketler: bfs algoritması, bfs algoritması adım adım, bfs graf algoritması, enine arama algoritması
