24 Mart 2016 Perşembe

BFS and DFS Algoritmaları ve C Kodu ( Graph )

Bu yazımda graphlarda gezinme algoritmaları olan BFS ( Breadth First Search ) ve DFS ( Depth First Search )’nin bir örnek graph üzerinde uygulamasının C kodu ile nasıl yapılacağından bahsedeceğim. İlk önce BFS algoritması ile başlayacağım.

Ö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.