BFS - Sevilmesi Kaçınılmaz Search (Arama) Algoritması

Recursion doğru kullanıldığı zaman çok işimize yarayabilir, kullanılmadığında ise öldürebilir, çocukların(işe yeni başlayanların) ulaşamıyacağı yerlerde saklayınız. Özellikle ağaç tipi veri yapılarının tüm düğümlerini dolaşmak istediğimizde recursiondan faydalanabiliriz. Fakat bu ağaç yapısının ne kadar derinliğe sahip olduğunu kestiremediğimiz durumlarda bu yönteme çok da bel bağlamamak lazım zira işlem aslında yığın yapısı ile gerçeklendiğinden (tüm derleyici yapımı işlemlerinde dahil), yığın taşabilir yani overflow hatasıyla karşılaşabiliriz.

Alternatif bir yöntem ise kendi yığınımızı kullanarak bu işi yapmaktır. Zaten olay bu değilmidir ? Kendin pişir kendin ye..
Genel adı ile "Breadth First Search" ("Yayılma Öncelikli Arama" diye çeviriyorum akademisyenlerin affına sığınarak):

• Bir yığın yapısı oluşturulur ve root node bu yığına eklenir. (Queue ile de yapılabilir sadece işleme sıranız değişir, pek alışılagelmemiştir ayrıca)
• Herhangi bir node'un alt node'ları varsa bunlar da yığına eklenir
• Bulunduğumuz node işlenir ve yığından bir sonraki node çekilir.
• Yığın boşalana kadar bu işlem tekrarlanır

Pseudo oluştu sanırım, bundan sonrası standart işler artık, kim olsa yapar :)

Algorithms Book (Memory remains from Course: Analysis of Algorithms)

I just finished a fantastic book called "Algorithms", by Sanjoy Dasgupta, Christos Papadimitriou and Umesh Vazirani. Even better: this book is free and can be downloaded in PDF form.

At 300+ pages, it's not lightweight either, but the authors have done a fantastic job at explaining the main foundations of essential algorithms in simple terms that even developer who don't have a CS degree will find easy to read and to absorb. You will see a few mathematics formulas and proofs here and there, but you can safely skip them if you are not comfortable with them and just take away the very natural and friendly wordings that the authors never omit to make when they are trying to get you to understand the overall idea behind an algorithm.

The book is very extensive and covers the most important algorithms you will ever come across in your life as a developer, starting with the introduction of the "big O" notation, and then progressively moving to more complex topics such as graphs, dynamic programming (nothing to do with dynamic languages), linear programming and culminating this area with the Simplex algorithm (I loved this section).

I would consider the chapters that follow as a "second part" of the book (even though it's not structured as such) since they cover more advanced (and sometimes, still not completely understood yet) problems such as NP completeness and quantum programming.

A must-read for any developer who never got a chance to understand how all these algorithms work or who simply want to get a refresher...

And hats off to Sanjoy, Christos and Umesh for making such a great contribution to the computing world!