Breadth first search ve depth first search algoritmaları graph larda gezinme ve arama algoritmalarıdır.

Bu graphlarda ilişkiler iki şekilde tutulabilir. İki boyutlu array ve linked listler ile

Matrix şeklinde ilişkiler

Link List şeklinde ilişkiler

Breadth First Search  (Sığ Öncelikli Arama)

BFS (breadth first search) algoritmasının çalışma mantığı şu şekildedir. Verilen bir node dan başlayarak ilgili node un tüm komşuları gezilir. Daha sonra gezilen komşuların komşuları gezilerek verilen graph gezilmiş olur.

Algoritma

1. Fonksiyona gönderilen node kuyruğa atılır.
2. Kuyruk boşalıncaya kadar döngü sürdürülür.
3. Sıradaki node kuyruktan çıkarılır.
4. Çıkarılan node daha önce gezilmemiş ise, gezildi işareti konur ve gezilmemiş komşuları kuyruğa konur.

Pseudo kodunu şöyle yazabiliriz.

Alttaki şekil de verilen bir graph ın gezilirken nasıl renklendirildiğini görebilirsiniz

Ayrıca buradaki animasyonu izleyebilirsiniz.

Şekil 1

Örneğin şekil 1 için bfs algoritmasıda  c kodunu yazmak istersek şu şekilde bir kod yazabiliriz.
Depth First Search (Derin Öncelikli Arama)

DFS (depth first search) algoritmasının çalışma mantığı şu şekildedir. Verilen graph daki tüm node lar gezilecek şekilde, sırayla ziyaret edilen bir nodun komşularına gidilir, gezilmemiş bir komşusu varsa ona gidilir, ve daha sonra sıradaki kendi komşusundan önce komşusunun komşusuna gidilir. Böylece sürekli derine inilir. Daha sonra gezilmemiş node kalmayınca bir geri noda gelinir ve sıradaki komşu ve komşunun komşusu…. şeklinde devam eder. Bu algoritmada tüm graph gezilir(graphlarda bağlantısız node lar olsa da)

Algoritma

1. İlk olarak birinic node stack a konur.
2. Stack boşalıncaya kadar döngü devam eder.
3. Stack dan node alınır.
4. Eğer alınan node gezilmemiş ise, komşularına bakılır, komşularından gezilmemiş olan varsa alınır ve stack a atılır.
5. Eğer gezilmemiş bir komşu kalmadıysa stackdan yeni node alınır.

Pseudo kodunu şöyle yazabiliriz.

Ayrıca buradaki animasyonu izleyebilirsiniz

Şimdi şekil 1 için dfs algoritmasının c kodunu yazalım

<<< Önceki: C# ile Local Mysql Veritabanı Bağlantısı

Sonraki: ProjeKent 2012 Proje Yarışma Başvuruları Başladı >>>