Anasayfa » Algoritmalar, Veri Yapıları

Breadth First Search ve Depth First Search Algoritmaları

30 Aralık 2011 27.903 kez okundu 2 yorum
1 Star2 Stars3 Stars4 Stars5 Stars (2 oy,5 üzerinden : 4,00 )
Loading...

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:

Sonraki: >>>


Facebookta Paylaş

2 yorum »

  • Furkan dedi ki:

    Çok güzel bir yazı olmuş. Elinize sağlık

  • Ahmet Selim dedi ki:

    Emeğinize sağlık hocam. Güzel bir anlatım olmuş. Allah razı olsun.

Yorum Bırakın!

Yorum yaz, yada kendi sitende trackback (Geri besleme) olarak ekle. Ayrıca RSS ile bu konuya üye olabilirsin. .

Nazik olun. Temiz tutun. Konu dışına çıkmayın. Spam yaratmayın.

Bu tagları kullanabilirsiniz:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Bloğumuz gavatarı desteklemektedir. Kendi gavatarınızı edinmek için lütfen Gravatar a üye olun.