Algoritma

Depth first search

DFS’yi anlatmadan önce bunun bir arama algoritması olduğunu söylemekle başlayalım. Arama algoritmaları birçok yönden birbirinden ayrılsa da ortak noktaları birşeyler aramalarıdır. Bu bazen bir dizideki en büyük sayı olur, bazen de labirentten çıkış yolu. DFS, graflarda arama yapar ve anlaşılması görece kolaydır.

Graflar DFS ile aranırken stack veri yapısı kullanılır. Aşağıda DFS ile aranmış bir graf örneği görüyorsunuz. Algoritmanın daha iyi anlaşılabilmesi için grafın tamamı aranmıştır. Daha önceden ziyaret edilmiş düğümler, yanlışlıkla tekrar ziyaret edilmemesi için karalanmıştır.

Yukarıda gerçekleşen olayları adım adım anlatmak gerekirse;

  1. Başlangıç düğümü olarak 0 numaralı düğüm seçildi.
  2. 0 numaralı düğüm stack veri yapısına push edildi.
  3. 0 numaralı düğüm stack veri yapısından pop edildi ve 0 düğümünün komşuları olan 1 ve 2 numaralı düğüm push edildi.
  4. 2 numaralı düğüm pop edildi ve bu düğümün komşuları olan 4, 5 ve 6 numaralı düğüm push edildi.
  5. Komşuları olmayan 6 ve 5 numaralı düğüm daha sonra da 4 numaralı düğüm pop edildi, 4 numaralı düğümün komşusu olan 3 numaralı düğüm push edildi.
  6. Ziyaret edilmemiş komşusu olmayan 3 ve 1 numaralı düğüm pop edildi, stack’ta düğüm kalmadığı için algoritma sona erdi.

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

Leave a Reply

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