Algoritma

Breadth first search

BFS, arama yaparken önce başlangıç düğümünün yakın çevresini, daha sonra da uzağındaki düğümleri arar. Dolayısıyla aranan düğüm başlangıç noktasına yakınsa arama işini kolaylaştırır.

Aşağıda bir binary tree örneği görüyorsunuz. Konunun daha iyi anlaşılabilmesi için herhangi bir hedef konmadan tüm ağaç aranmıştır. BFS ile arama yaparken kuyruk veri yapısından faydalanıldı.

  1. Ağaç veri yapısının başlangıç durumu.
  2. Kuyruğa 0 numaralı düğüm eklendi.
  3. Kuyruktan 0 numaralı düğüm çıkarıldı, bu düğümün komşuları olan 1 ve 2 numaralı düğüm kuyruğa eklendi.
  4. 1 numaralı düğüm kuyruğa 2 numaralı düğümden önce eklendiği için ilk o çıktı, komşuları olan 3 ve 4 numaralı düğüm kuyruğa eklendi. Artık kuyruğun başında 2 numaralı düğüm var.
  5. 2 numaralı düğüm çıktıktan sonra komşuları olan 4 ve 5 numaralı düğüm kuyruğa katılıyor.
  6. Kuyrukta 3,4,5 ve 6 numaralı düğüm var. Bunların hiçbir komşusu olmadığı için sırayla kuyruktan çıktılar.

Github sayfamdan C ile yazılmış BFS örneğine ulaşabilirsiniz : https://github.com/farukcansaglam/search_algorithms/tree/master/breadth_first_search

Leave a Reply

Your email address will not be published. Required fields are marked *