//
Java, Veri Yapıları

Graf Algoritmaları


Gerek ayrık yapılarda gerekse veri yapılarında en önemli konulardan biri de graflar. Bilgisayar mühendisi olsun olmasın günlük yaşantısında insanların bir şekilde mutlaka kullandıkları bu teorinin bazı algoritmalarının java diliyle uygulamasını eclipse projesi olarak şu linkte bulabilirsiniz.

Projenin genelini açıklamayacağım, zaten çok karmaşık değil ama en azından içinde kullanılan algoritmalara bir değinmek isterim.

Projede temel olarak üç tane algoritma kullanılıyor;

  • Dijkstra
  • Prim
  • BFS

Dijkstra

En kısa yol algoritması olarak da bilinir. İki düğüm arasındaki en kısa yolu bulmak için kullanılır genel olarak. Çalışma mantığı şu şekildedir:

  1. Sonuçların tutulacağı boolean tipinde bir dizi ile düğümler arasındaki mesafelerin tutulacağı integer tipinde bir dizi tanımlanır.
  2. Minimum uzaklık, sonsuz olarak atanır.
  3. Sonuç dizisinde kaynak düğüme denk gelen eleman true olarak işaretlenir. (Kaynak düğümden kaynak düğüme giden en kısa yol zaten kendiliğinden bulunmuş olur zira.) Geri kalan düğümlerin elemanları false atanır.
  4.  For döngüsü ile mesafe dizisi uygun şekilde doldurulur.
  5. Kaynak düğümün ağırlık bakımından en yakın olduğu düğüme gidilerek (for döngüsü ile tüm komşuların ağırlıkları karşılaştırılır) başlanır. Gidilen  düğümün sonuc dizisindeki değeri true yapılır.
  6. Bu işlemler hedef düğümün sonuç dizisindeki değeri true olana kadar devam eder.Örnek kodu inceleyerek daha ayrıntılı bir fikre ulaşabilirsiniz.
Prim’s Algorithm
Bu algoritma, temelde, ağırlıklı bir grafın kenarlarından yararlanarak grafın tüm düğümlerini kapsayan en küçük ağacı bulmak üzere tasarlanmıştır. Burada dikkat edilmesi gereken nokta ağacın tüm kenarları kapsamak zorunda olmadığıdır. 
Algoritma işlemeye rastgele bir  düğümden başlar. Biz örneğimizde ilk düğümden başlamayı seçtik. İşleyiş oldukça kolay, ilk olarak 0. düğümden çıkan kenarları bir öncelik kuyruğuna ekliyoruz. Tahmin edersiniz ki bu öncelik kuyruğumuz küçükten büyüğe sıralıyor kenar ağırlıklarını. Daha sonra kuyruktan ilk elemanı alıyoruz.  Şayet kenarın kaynağı ya da hedefi ağaca eklenmemişse bu kenarı ağaca ekliyoruz. Ardından tüm kenarlar ağaca eklenene kadar kuyruktan bir eleman çıkartıp onun komşularını da kuyruğa ekliyoruz.
BFS Algorithm
Aynı seviyedeki düğümlerin ilk dolaşılması üzerine kurulmuş bir algoritmadır. Özyineleme içerir. Kuyruk yerine yığın kullanılırsa DFS algoritması elde edilir.Koddaki çözüm yeterince açıklayıcı olduğundan burada açıklama yapmıyorum bu algoritmayla ilgili.Sorularınızı ve görüşlerinizi yorumlar aracılığı ile belirtebilirsiniz.
About these ads

Tartışma

One thought on “Graf Algoritmaları

  1. graf renklendirme algoritması kullanımı nasıl olur acaba. küçük bir örnek olsa yetecek ama yok.

    Posted by ömer faruk | Şubat 26, 2013, 6:20 pm

Bir Cevap Yazın

Aşağıya bilgilerinizi girin veya oturum açmak için bir simgeye tıklayın:

WordPress.com Logosu

WordPress.com hesabınızı kullanarak yorum yapıyorsunuz. Log Out / Değiştir )

Twitter picture

Twitter hesabınızı kullanarak yorum yapıyorsunuz. Log Out / Değiştir )

Facebook fotoğrafı

Facebook hesabınızı kullanarak yorum yapıyorsunuz. Log Out / Değiştir )

Google+ fotoğrafı

Google+ hesabınızı kullanarak yorum yapıyorsunuz. Log Out / Değiştir )

Connecting to %s

Takip Et

Her yeni yazı için posta kutunuza gönderim alın.

%d blogcu bunu beğendi: