Breadth First Search (BFS) Algoritması

Herkese merhaba;

Diğer yazılarımızda bahsi geçen bir algoritmadan bahsedeceğiz.Önceki bfs algoritmasına buraya tıklayarak ulaşabilirsiniz.

Giriş

Algoritmanın temel amacı diğer algoritma senaryolarında olduğu gibi en kısa yolu bulmaktır.En kısa yolu bulurken aranan node göre hareket etmektedir.

Algoritmanın türkçe karşılığı yayılım(Genişlik) ölçekli(Öncelikli) arama olarak literatürde anlatılıyor.Genelde DFS denilen derinlik ölçekli algoritma ile beraber anlatılır.Her iki algoritmada arama optimizasyonu amaçlar.Biri derinliğe göre diğeri genişliğe göre hareket eder.Algoritma arama yaparken genişliği baz aldığı için bütün node ların çocuklarına bakar burada kritik nokta gidilmiş cocuklara tekrar gitmemektir.Burada tüm müsait çocukları gezdiğimizde gezdiğimiz node’ların çocuklarına gideceğiz.Bu şekilde genişlik baz alınarak tüm ağacı dolaşıcaz.

Algoritmayı Çalıştıralım

Yukarıdaki grafta x bizim aranacak node’miz olsun.Şimdi adım adım gidelim;

1.Adım: X aranacak node root’tan başlanacak.

2.Adım:İlk adım node left right şekilde aramaya başlıcaz.

3.Adım:Önce düğüm sonra düğüm solu,sonra sağı

4.Adım:N L R yada N R L şeklinde çalışabilir.

5.Adım:Root gidildi kuyrukda Root’un sağ ve sol çocukları var. Gidilen:A Kuyruk:B,C,D,E,F,X

6. Adım:Önce left sonra right yapalım.Önce B’ye sonra C’ye gidelim ve kuyruğu tazeleyelim.

Gidilen:A,B,C Kuyruk:D,E,F,X

7.Adım:B’nin sol ve sağ cocuklarına gideceğiz.Gidilen:A,B,C,D,E Kuyruk:F,X

8.Adım:C’nin sol ve sağ çocuklarına gideceğiz.Gidilen:A,,B,C,D,E,F Kuyruk:X

9.Adım:Kuyrukta kalan son eleman bizim gidilecek node’muzdur.

Bu arada eğer bir cycle var ise bunun kontrolü gidilen node’lara bir daha gidilmemeli şeklinde çözülür.

2^n derinliğe sahip bir ağaç için karmaşıklık Big O(N) derinlik arttıkca karmaşıklık artar.

O(b^m) = Big o(m)

Son

Umarım faydalı bir yazı olmuştur.Herkese başarılar.