BFS Algoritması

BFS ALGORİTMASI

BFS Algoritması temel prensip olarak en yakın düğümleri ziyaret etmeyi hedefler. En yakındaki düğümler taranarak uzaktaki düğümlere gidilir. Yakın olan düğümler öncelikli olarak ziyaret edileceği için bizim bir veri yapısı kullanmamızı gerektirmektedir. BFS Algoritmasında Kuyruk Veri Yapısı Kullanılır.

Ziyaret edilen düğümün komşuları kuyruğa atılır. Her adımda kuyruktan bir eleman çıkartılır ve bu mantıkla ziyaret edilmemiş düğümler kuyruğa eklenir. Bu şekilde tüm düğümler dolaşılır. Tabii ki bu algoritmayı adım adım örnekle anlatacağız.

BFS Algoritması Örneği

Yukarıdaki örneği kullanalım. Başlangıç düğümü olarak “2” düğümünü kullanacağız. Şimdi Adım adım nasıl yapacağımıza göz atalım. Her adımda kuyruktan eleman çıkartılır.

1. Adım:

2 düğümü kuyruğa eklenir.

Ziyaret Edilen Düğümler: 2

Kuyruk Durumu: 2

Kuyruktan Çıkan: Yok

Output (Çıktı) : 2

2. Adım:

0 ve 3 düğümü kuyruğa eklenir.

Ziyaret Edilen Düğümler: 2 – 0 – 3

Kuyruk Durumu: 0 – 3

Kuyruktan Çıkan: 2

Output (Çıktı) : 2 – 0 – 3

3. Adım:

1 düğümü kuyruğa eklenir. (Neden? – çünkü kuyruk durumuna bakın, kuyruğun en başında 0 var, bu yüzden 0’ın ziyaret edilmemiş komşusu olan 1 eklenir)

Ziyaret Edilen Düğümler: 2 – 0 – 3

Kuyruk Durumu: 3 – 1

Kuyruktan Çıkan: 0

Output (Çıktı) : 2 – 0 – 3 – 1

4. Adım:

1 düğümü kuyruğa eklenir. ( çünkü kuyruk durumuna bakın, kuyruğun en başında 0 var, bu yüzden 0’ın ziyaret edilmemiş komşusu olan 1 eklenir)

Ziyaret Edilen Düğümler: 2 – 0 – 3

Kuyruk Durumu: 3 – 1

Kuyruktan Çıkan: 0

Output (Çıktı) : 2 – 0 – 3 – 1

5. Adım:

4 düğümü kuyruğa eklenir. (çünkü kuyruk durumuna bakın, kuyruğun en başında 3 var, bu yüzden 3’ün ziyaret edilmemiş komşusu olan 4 eklenir)

Ziyaret Edilen Düğümler: 2 – 0 – 3 – 4

Kuyruk Durumu: 1 – 4

Kuyruktan Çıkan: 3

Output (Çıktı) : 2 – 0 – 3 – 1 – 4

6. Adım:

Bu adımda kuyruğa eleman eklenmez (Neden? – çünkü kuyruk durumuna bakın, kuyruğun en başında 1 var, 1 düğümünün ziyaret edilmemişkomşusu yok.)

Ziyaret Edilen Düğümler: 2 – 0 – 3 – 4

Kuyruk Durumu: 4

Kuyruktan Çıkan: 1

Output (Çıktı) : 2 – 0 – 3 – 1 – 4

7. Adım:

Bu adımda 5 düğümü kuyruğa eklenir (Neden? – çünkü kuyruk durumuna bakın, kuyruğun en başında 4 var, 4 düğümünün ziyaret edilmemiş tek komşusu 5 düğümüdür.)

Ziyaret Edilen Düğümler: 2 – 0 – 3 – 4 – 5

Kuyruk Durumu: 5

Kuyruktan Çıkan: 4

Output (Çıktı) : 2 – 0 – 3 – 1 – 4 – 5

8. Adım:

Bu adımda hiçbir işlem yapılmaz. Çünkü kuyruk boş ve eklenebilecek ziyaret edilmemiş düğüm yoktur. Bu yüzden algoritma burada sonlanır.

Algoritmanın Çıktısı Şu şekildedir. :

2 – 0 – 3 – 1 – 4 – 5