Derin Öncelikli Arama (Depth First Search , DFS)
Yazan : Şadi Evren ŞEKER
Bir ağaç dolaşma algoritmasının (tree traverse algorithm, tree traversal) ilk önce alt seviyesinde bulunan komşularını araması durumudur.
Örneğin aşağıdaki ağacı ele alalım:
Ağacı dolaşma sırlaması örneğin 3, 2, 7, 1, 9 , 8 , 5 şeklindeyse bu dolaşmaya derin öncelikli arama (deep first search) ismi verilebilir.
Bu arama sıralamasında, dolaşma sıralaması aşağıdaki ihtimallerden birisi olabilir:
LRN : Left Right Node (Sol Sağ Düğüm)
RLN : Right Left Node (Sağ Sol Düğüm)
RNL : Right Node Left (Sağ Düğüm Sol)
RLN : Right Left Node (Sağ Sol Düğüm)
Yani öncelikle düğüm sonra altındaki üyelere hareket edilir.
Sığ Öncelikli Arama (Breadth First Search) algoritma tipine göre ise :
NLR : Node Left Right (Düğüm Sol Sağ)
NRL : Node Right Left (Düğüm Sağ Sol)
ihtimallerinden birisi tercih edilebilir. Buradaki fark ilk bakılan düğümün, mevcut düğümün altında olan bir düğüm yerine aynı seviyede olmasıdır. Yani derin öncelikli aramada, sığ aramadan farklı olarak önce düğümün alt seviyedeki düğümlerden aramaya başlanır.
yukarıda depth first search sırasına uyulursa 3271985 sırasında olması gerekmez mi hocam yada ben mi yanlışım.
Evet LRN sırasına göre haklısınız hatayı düzeltiyorum teşekkürler.
Hocam merhabalar, RLN : Right Left Node (Sağ Sol Düğüm) tabiri iki defa kullanılmış. Sanırım LNR: Left Right Node(Sol Sağ Düğüm) eksik.
hocam merhabalar..
preorder(önce kök) ve postorder (sonrakök)’ü DFS’de nasıl uygulayabiliriz?
kodlarını bulamadım ve açıkçası kafam karıştı… teşekkürler şimdiden.
Depth-first search algoritmasının kaba kodunu, tekrarlı (recursive) yapıyı ortadan kaldıracak şekilde bir stack kullanarak tekrar yazan bir c ++ kodunu nasıl yazıcaz hocam mantık yürütemedim dili tam olarak almadığım için henüz zorlanıyorum