Graf Teorisi – Arama Algoritmalarına Giriş 1

graf

COVID-19′ un bizi bu denli sarstığı dönemde boş durmuyor, günlerimizi verimli geçirmek adına yeni bilgiler öğrenmeye hızla devam ediyoruz. Neredeyse her gün yeni bir bilgi, yeni bir keşfe çıkıyoruz.

Ve biliyorsunuz ki, her öğrenilen bilginin asıl amacı temelde yapıyı anlaşılır kılarak bilgilerimizi günden güne değerli hale getirmektir. Ben de sizler ile çok sıkıcı olmadan veri yapıları türlerinden olan graflar için belirli arama algoritmaları ile keşfe çıkalım istedim.

Gerek bilgisayar ile ilgili okunan bölümlerde gerek ise veri bilimi adına yapılan hemen hemen tüm çalışmalarda öncelikli olarak yapacağımız belirli adımlar vardır.

  1. Veri Nedir?
  2. Veri Neden İşlenir?
  3. Veri Yapıları Nelerdir?

Tabi ki çözmek zorunda olduğumuz daha birçok soru üretebiliriz. Diğer yazılarımda verinin ne olduğundan ve neden işlendiğinden bahsetmiştik. Bugün ise sizleri farklı bir veri yapısı ile tanıştırmaya geldim. Programlama öğrendiğimiz ilk dönemlerde bizlere anlaşılır olmak adına düğümler ve listeler üzerinde işlemler anlatılmıştı.

Ancak düğümler için internette birçok kaynak var iken bugün bahsedeceğim graf yapısı için ne yazık ki Türkçe kaynak erişimi oldukça az! Bu sebeple gelin biraz daha veriye yaklaşıp neler yapabileceğimize bir bakalım. Ne dersiniz ?

Graf ( Çizge ) Teorisi

Grafları inceleyen bir matematik dalı olan bu teori temelleri 1736 yılında Leonhard Euler tarafından ortaya konulmuştur. Euler ismi sanıyorum ki birçok kişiye yabancı değil! Üniversitede gerek sayısal analiz gerekse veri yapıları dersinde Euler amcamız ile oldukça yakından tanışma fırsatımız olmuştu.

Matematik ve Bilgisayar bilimi adına yaptığı çalışmaları okumanız için sizlere biyografi tadında bir bağlantı bırakıyorum. Şimdi biraz daha teknik konuşmaya başlayacağız 🚀

Bir graf, düğümlerden ve bu düğümleri birbirine bağlayan kenarlardan oluşmaktadır. Aşağıya sizler için yol gösterici olması adına ufak bir görsel bırakıyorum.

Gördüğünüz gibi düğümler komşuları ile kenar olarak adlandırılan bağlar ile bağlanmıştır. Genel yapısını şöyle bir gördüğünüze göre, sizlere graf yapılarınızı çevrim içi hazırlayabileceğiniz bir graf sitesi önereceğim. Graf yapılarınızı görsel olarak görebilir ve birçok avantajlı yapıya sahip olabilirsiniz!

Programlama dili olarak en basit ve temelden gitmek adına C dilini tercih ediyorum. Dilerseniz birçok hazır kütüphanesi bulunan Python’ ı sizlere önerebilirim. Veya birçok farklı programlama dilinde kendi grafınızı oluşturup arama sağlayabilirsiniz.

Yukarıda bulunan görseldeki graf yapısını kendi tercihime göre belirledim. Siz de istediğiniz yapıdaki grafı kolaylıkla oluşturabilirsiniz. Baz alacağımız orijinal grafımız 6 adet düğümden oluşmaktadır. Bu grafın kod üzerinde oluşturulabilmesi için ana fonksiyon içerisinde add_edge( ) fonksiyonu ile verilen tepeler ve kenarlar oluşturulmuştur.

Öncelikle CreateNullGraph fonksiyonu üzerinde boş bir graf oluşturacağız. Ardından düğümleri ve kenarları sırası ile ekleyeceğiz.
add_edge(G,1,2,0,0) fonksiyonunu ele alalım. Burada söylenmek istenen durum; G grafı üzerinde 1 ve 2 numaralı düğümler bir sonraki parametre 0 olduğu için yönsüz ve yine 0 olduğu için ağırlıksız oluşturulmuştur.

Yazımın sonunda kodları GitHub aracılığı ile sizlere erişim sağlamış olacağım. Bu sebeple başlangıç için siz sadece algoritma ve veri yapısı mantığını anlayın, yeterli gelecektir. Daha sonra bir bakmışsınız kodları kendiniz oluşturmaya başlamışsınız!

DFS ( Derin Öncelikli) ARAMA ALGORİTMASI

DFS(Depth-First Search) arama algoritması, ağaç veya graf veri yapılarında arama yapmak için kullanılan bir algoritmadır. Algoritma aramaya başladığı düğümden ulaşabileceği en derin düğüme kadar gider, gidecek daha derin bir düğüm kalmadığında geri sarar ve derin düğümlere öncelik vererek gezmeye devam eder.

Şekilde gösterilen graf add_edge() ile oluşturulduktan sonra DFS arama algoritması arka planda Stack (Yığın) yapısı ile çalışır. Görüldüğü üzere herhangi bir düğümden (tepe) başlanarak derin öncelikli arama yapılacaktır. Bu graf için aşağıdaki görselde belirtildiği gibi başlangıç düğümü 0 olarak belirtilmiştir. Bu görselde DFS fonksiyonunun çağrılması nihai olarak gösterilmiştir.

Çalışma Prensibi ve Akış Şeması

Yapımızı daha iyi anlayabilmek üzere örnek bir problemin DFS arama algoritmasına göre akış şeması ile çözüm yapısı aşağıda verilmektedir.

Psödokodunu vermiş olduğum DFS arama algoritması fonksiyonunun sizler için C koduna da aşağıdaki görselde yer vermekteyim. Her adımda yorum satırı olarak açıklamaları yazdım, keyifle okuyabilirsiniz.

Yukarıda oluşturulan DFS fonksiyonu çalıştırıldığında öncelikle parametre olarak graf (Graph*G), tepeler(köşe) ve visited[ ] dizisini almak zorundadır. Ana fonksiyon içerisinde başlangıç düğümü 0 olarak belirtilen DFS algoritması için Stack içerisinde 0 kabul edilir. 0 düğümü ziyaret edildiği için visited[vertex] dizininde 1 olarak yani gezildi olarak değiştirilir. Bu değişim sırasıyla tepelerin komşuları için de aşağıdaki şekilde görüldüğü gibi gerçekleştirilir. Kutucuklar içerisinde tek tek stack yapısı değişimini göstermiş oldum.

Geçici olarak tepeleri tutmak için tmp adında bir değişken oluşturuyoruz. Seçilen tepelerin arama algoritmasına uyabilmesi için tmp değişkeni NULL olana kadar (komşu bulunmayıncaya kadar) arama yapılması gerekmektedir. Her seferinde fonksiyonun yazılması yerine rekürsif olarak DFS fonksiyonu çağırıldığında arama gerçekleştirilmiş olacaktır.

Ardından ana fonksiyon içerisinde döngü ile tüm tepeler gezilecek şekilde bir döngü aracılığıyla başlangıç için ziyaret edilenler dizisini 0 olarak tanımladık. Fonksiyonu ise aşağıda görüldüğü gibi çağıracağız.

Gezilen tepe ve kenarların kontrol edilmesi için ise printf komutu ile ekrana yazdıracağız.

Konsol ekranında sonuçlarımızı da incelediğimize göre Python dilini kullanmak isteyenler için de ufak bir nüans vermek istedim.

C programlama kodunun yanı sıra Python programlama dilinde de graf sırası ile oluşturulur ve ardından DFS fonksiyonu çağırılır. C’deki gibi Stack yapısı ile tepeler ve komşular push – pop işlemi ile arama algoritması çalıştırılır.

Yukarıda gördüğünüz görselde ise DFS ana fonksiyonuna yer vermekteyim. Derin öncelikli arama için bulabileceğiniz çok güzel kaynaklar mevcuttur. Makinelere bunu anlatmadan önce kendiniz iyice anlayıp pratik yapın ki bir öğretmen gibi onlara algoritmayı anlatabileseniz. Öğrenmek için bir kere o kağıtları kalemleri elimize alacağız ve bol bol pratik çözeceğiz! 

Tavsiyelerime uyarsanız aslında ne kadar kolay olduğunu göreceksiniz. Bu yazımda kullandığım kodların bulunduğu GitHub linkine buradan erişim sağlayabilirsiniz. DFS algoritmasını öğrendik, peki ya BFS algoritmasnı öğrenmeye ne dersiniz? Öyleyse bir sonraki yazımda görüşmek dileğiyle.

REFERANSLAR

Vikipedi, Özgür Ansiklopedi, “Çizge”, https://tr.wikipedia.org/wiki/%C3%87izge_teorisi,

Vikipedi, Özgür Ansiklopedi, “Derin öncelikli https://tr.wikipedia.org/wiki/Derin_%C3%B6ncelikli_arama.

https://graphonline.ru/en/

https://www.biography.com/scientist/leonhard-euler

Leave a Reply

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