Graf Teorisi – Arama Algoritmalarına Giriş 2

Graf Teorisi Arama Algoritmaları

Herkese merhaba, kahvelerimizden yudumlayıp kaldığımız yerden haznemize yeni bilgileri almaya devam ediyoruz. Geldik yine graf teorisi arama algoritmalarını incelemeye. DFS algoritması öğrenildiğine göre yeni içeriğimiz olan BFS algoritmasına başlayabiliriz. Peki BFS ve DFS graf teorisi arama  algoritmalarının birbirinden farkı ne olabilir? Sizlerle farklı kaynaklardan topladığım bilgilere hızlıca bir göz atalım, ne dersiniz?

BFS (BREADTH-FIRST SEARCH) ARAMA ALGORİTMASI

Sığ öncelikli arama (enine arama) olarak geçen bu terim; bir grafın düğümlerini, başlangıç noktasına daha yakın olanlara öncelik vererek arayan bir algoritmadır. Algoritma ziyaret ettiği düğümlerin bütün komşularını bir kuyruğa ekler ve ziyaret edeceği düğümleri kuyruktaki sıraya göre seçer. Eğer arama yapılan çizge bir ağaç ise kuyruk kullanmaya gerek olmaz. Ancak dikkat ettiyseniz bu sefer graf teorimizde yığın (stack) yapısı değil kuyruk (queue) kullanıyoruz.

DFS algoritmasında hatırlarsanız düğüm belirleyip o düğümün kenarı üzerinde gidilebilecek en uzak düğüme kadar gidilip daha sonra diğer düğümler gezilmekteydi. Fakat BFS algoritması bu mantık ile çalışmamaktadır. Gelin biraz daha derine inelim.

BFS sıralama algoritmasında, başlangıç düğümünden başlanarak o düğümün tüm komşuları ziyaret edilir. Ardından bulunduğun komşunun da komşuları ziyaret edilir. Bu şekilde tüm graf gezilmiş olur.

Çalışma Prensibi ve Akış Diyagramı

BFS arama algoritmasına göre akış şeması ile çözüm yapısı altındadır.

Breadth-first search

Projede kullanacağımız orijinal graf DFS arama algoritmasında kullanıldığı gibi benzer şekilde bu yazımda da kullanılacaktır.

DFS arama algoritması grafiği

DFS arama algoritması içerikli yazımda gösterdiğim gibi graftaki kenarlar add_edge( ) ile oluşturulduktan sonra BFS arama algoritması kuyruk (queue) yapısı ile çalışır. BFS algoritması kuyruk ile çalıştığı için FIFO (First in First out) mantığı ile hareket eder. Diğer bir ifade ile çalışma mantığı ilk giren ilk çıkar biçimindedir. Herhangi bir düğümden (tepe) başlanarak sığ öncelikli arama yapılacaktır ve bu graf için şekilde belirtildiği gibi başlangıç düğümü 0 olarak belirtilmiştir.

Bu durum tamamen kodu yazan kişiye bağlıdır bu sebeple kullanıcı ne isterse o düğümü yazabilmektedir. Aşağıda gösterdiğim C kodunda BFS fonksiyonuna başlangıç parametresi olarak 2 düğümü gönderilmiştir.

Hemen aşağıda gösterdiğim C kodunda ise değişkenler grafın tepe sayısı kadar değer alarak oluşturulur ve graftaki tüm tepeler gezilene kadar ziyaret edilen ve uzaklık matrisi dizileri 0 olarak atanır.

BFS Fonksiyonunun Oluşturulması

visited dizisindeki 0 düğümü başlangıçta ziyaret edilmedi(0) olarak fonksiyona gönderilir ve tepeye uğrandığı için visited dizisinde bu tepe artık 1 olarak gösterilir. BFS algoritmasına göre arama yapılırken seçilen düğümün komşularına gidilmelidir.

Örneğin, 0 düğümünün komşuları 1 ve 2 olsun. Bu tepelerin listede olup olmadığı kontrol edildikten sonra kuyruğa ekleme (enqueue) yapılmalıdır. ve komşu olan 1 ve 2 tepeleri geçici olarak tmp değişkenindetutulur. Ardından aşağıdaki şekil incelendiğinde  tmp != NULL yapılarak komşuların boş olup olmadığı kontrolü gerçekleştirilir.

Komşuların Yazdırılması

0 tepesinin komşuları olan 1 ve 2 tepelerinin yazdırılabilmesi için komşular değişkeni ise aşağıdaki şekildeki gibi yazdırılmalıdır. Bu şekilde bütün tepelerin komşuları arama süresi boyunca yazdırılacaktır.

BFS fonksiyonunda ziyaret edilen düğümlerin listede olup olmadığının kontrolü yapılırken tepeler arası mesafeler de güncellenmektedir ve bu değişimler sonucunda en son kat edilen mesafeler aşağıdaki şekilde verilen değerler biçimindedir.

Mesafe Değişkenlerinin Arama Boyunca Güncellenmesi
Mesafe Değişkeninin Ekrana Yazdırılması

Haydi gelin, bu mesafe değişkenlerini konsol ekranında görüp sizin için çizdiğim grafik üzerinde kontrol edelim 🚀

Tepeler Arası En Kısa Mesafe Çıktıları
0 Tepesinin Diğer Tepelere Mesafesinin Şekillendirilmesi

Her şeyden önce grafları iyi öğrenerek yola çıkmamız gerekmektedir. Graf Teorisi Arama Algoritmalarını anlatmaya çalıştım bundan sonra veri yapıları iyi kavranıldıktan sonra kod yazmaya geçebilirsiniz.
Sonuç olarak ise anlatacaklarım bu kadardı fakat durmak yok, çalışmaya devam ediyoruz! Sağlıcakla kalmanız dileğiyle.

REFERANSLAR

Vikipedi, Özgür Ansiklopedi, “Sığ öncelikli https://tr.wikipedia.org/wiki/S%C4%B1%C4%9F_%C3%B6ncelikli_arama.

VivaDifferences, “8 Difference Between DFS (Depth First Search) And BFS (Breadth-First Search) In Artificial Intelligence”, https://vivadifferences.com/difference-between-dfs-and-bfs-in- artificial-intelligence/.

https://web.karabuk.edu.tr/hakankutucu/BLM222notes.html

Leave a Reply

Your email address will not be published. Required fields are marked *