Şekillerde Sığ Öncelikli Arama

Yazan : Şadi Evren ŞEKER

Bu yazının amacı genel amaçlı şekillerde (graphs) sığ öncelikli aramayı (breadth first search , BFS) açıklamaktır.

Bu yazı, ağaçlardaki sığ öncelikli arama ile karıştırılmamalıdır. Ağaçlar (trees) bilindiği üzere yönlü dairesel olmayan şekillerdir (directed acyclic graph) dolayısıyla ağaçlar üzerinde bu yazıda anlatılan sıra (queue) yapısına ihtiyaç duyulmaz.

Sığ öncelikli arama bir başlangıç düğümünden başlayarak sıradaki komşuları dolaşan arama algoritmasıdır. Bu arama algoritmasında amaç önce başlangıç düğümüne yakın düğümlere bakmaktır.

Bu arama şekli suya atılan bir damlanın suda çıkardığı halkalara benzetilebilir. Başlangıç düğümüne en yakın halka sonra ikinci yakın halka ve sonra diğerleri şeklinde giden bir arama algoritmasıdır.

Bu durumu aşağıdaki örnek üzerinden anlamaya çalışalım:

Örnek olarak yukarıda bulunan şekli ele alalım. Örneğimizde başlangıç düğümü (node) olarak A düğümünü seçtiğimizi ve aranan düğümün E düğümü olduğunu düşünelim .

A düğümünün komşuluk listesini (adjacency list) çıkarıyoruz:

komşu(A) = {C,B}

Bu komşulara sırasıyla bakılıyor ve bu komşuların komşuluk listeleri çıkarılıyor:

bakılanlar: {A,B,C}

komşular = komşu (B) , komşu (C) = {D,F,E}

Arana düğüm E, bu adımda bulunmuştur.

Yukarıdaki örnekte görüldüğü üzere bir sonraki derinliğe inilmeden önce, o derinlikte olan (başlangıç düğümüne o uzaklıkta olan) bütün düğümler dolaşılıyor ve ardından bir alt seviyeye iniliyor.

Yukarıdaki örnekte bütün ağaç dolaşılmış gibi düşünülebilir. Örneğin şekil (graph) aşağıdaki gibi olsaydı:

Bu durumda Z düğümüne hiçbir zaman bakılmayacaktı çünkü aranan düğüm, Z düğümünden daha sığ bir derinlikte olacaktı.

Kısacası BFS arama algoritması ile aranan düğümün derinliğine kadar olan bütün düğümlere bakılır ancak bu derinlikten daha aşağıda olan düğümlere bakılmasına gerek yoktur.