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.

Yorumlar

  1. Anonim

    yukarıda depth first search sırasına uyulursa 3271985 sırasında olması gerekmez mi hocam yada ben mi yanlışım.

  2. Anonim

    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.

  3. Anonim

    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.

  4. Zeynep

    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

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir