Örneğin hiç bilmediğiniz bir şehirde eve taşındınız. Çevrenizi hiç bilmiyorsunuz. İlk önce ilk kademe sokaklardan başlayarak gezersiniz. Bu sokaklar evinize en yakın sokaklardır. Bu sokakları öğrendikten sonra öğrendiğiniz sokakların komşu sokaklarını gezmeye başlarsınız. BFS algoritması da graph üzerinde tam olarak böyle bir gezinti yapmaktadır. İlk önce başladığı noktanın komşularına, daha sonra onların komşularına gitmektedir.
BFS algoritması tam olarak aşağıdaki gibidir.
DFS gezinmede ise ilk önce gidilebildiği kadar uzak yere gidilir. Daha sonra gidecek başka yer kalmayınca, bir önceki aşamaya dönerek oradan gidilebilecek en uzak noktaya gidilir ve daha sonra ilk başlanılan noktaya dönülür. DFS algoritması tam olarak aşağıdaki gibidir.
Bu algoritmaları bir örnek graph üzerinde göstermeden önce graph yapısını göstermeliyim. Vereceğim kodda aşağıdaki graphın yapısını uygulayacağım.
Her iki algoritmanın C ile nasıl kodlandığını burada bulabilirsiniz. Kodlama graphların array gösterimi ile yapılmıştır. Link list olarak da düzenlenebilir.
Hiç yorum yok:
Yorum Gönder