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:
- Sonuçların tutulacağı boolean tipinde bir dizi ile düğümler arasındaki mesafelerin tutulacağı integer tipinde bir dizi tanımlanır.
- Minimum uzaklık, sonsuz olarak atanır.
- 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.
- For döngüsü ile mesafe dizisi uygun şekilde doldurulur.
- 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.
- 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.