Veri Yapıları Laboratuvar Sınavı

Merhaba arkadaşlar

Bu yazıda aşağıda verilen uygulama sınavı için geliştirdiğim çözümü paylaşmak istiyorum. Amaç Merkez’den diğer noktalara en kısa mesafeyi bulmaktır. Bunun için Veri Yapıları dersindeki yöntemlerden faydalanarak bir çözüm ürettik. Umarım faydalı olur.

Uygulama Sınav Sorusu

Veri yapıları uygulama sınav sorusu şöyledir.

Bu tür Veri Yapıları sorularında genelde Dijkstra algoritması ile bir çözüm geliştirilmiştir. Burada farklı olarak Bellman-Ford algoritması ile bir çözüm üretildi. Ancak her iki algoritmanın aynı amacı gerçekleştirdiğini belirtmek isterim.

Geliştirdiğim çözüm dört farklı sınıf ile yapılabilir. Burada aşağıda verilen sınıflara ait kodları belirtilen sıralama ile sizlere vereceğim. Sizde bu sınıfları sıralamayı uyarak geliştiriniz.

Sınıfların Listesi

1- Node.java

2- SinglyLinkedList.java

3- Graph.java

4- Home.java

Şimdi sınıflara ait kodları tek tek paylaşalım. Her sınıfın açıklaması kodlar ile birlikte verilmiştir.

Node.java

package finaldeneme5;

/*Tek yönlü bağlı liste tanımı
data: Mevcut elemanın içeriği.
next: Bağlı listede sonraki elemanı gösteren pointer.*/
public class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }    
}

SinglyLinkedList.java

package finaldeneme5;
/*Tek Yönlü Liste*/
public class SinglyLinkedList {
    /*head: Listenin ilk elemanı.
    last: Listenin son elemanı*/
    Node head,last;

    /*Kurucu metod
    Listenin ilk ve son elemanı null yapılır.*/
    public SinglyLinkedList() {
        this.head = null;
        this.last = null;
    }
    
    /*Listenin başına eleman eklemeyi sağlar.*/
    public void addNodeHeadList(Node newNode){
        if(last==null)
            last=newNode;
        newNode.next=head;
        head=newNode;
    }    
    
    /*Listede bulunan elemanları ekrana yazar.*/
    public void displayData(String[] points){
        if(head==null){
            return;
        }else{
            Node temp=head;
            while(temp!=null){
                System.out.print(points[temp.data]);
                temp=temp.next;
                if(temp!=null){
                    System.out.print("-");
                }
            }
            System.out.print("\n");
        }
    }    
}

Graph.java

package finaldeneme5;

/*Çizge yani Graph sınıfı*/
public class Graph {
    
    /*Graph, komşu matris yöntemiyle gösterildi.
    İki boyutlu bir dizi ile bu işlem yapılır.*/
    int[][] edge;
    
    /*Dizinin eleman sayısı.*/
    int N;

    /*Kurucu metot*/
    public Graph(int N) {
        
        int i,j;
        
        /*N değişkenine değer dışarıdan gelecek.*/
        this.N = N;
        
        /*NxN büyüklüğünde iki boyutlu bir dizi 
        dolayısıyla matris tanımladık.*/
        edge=new int[N][N];
        for(i=0;i<N;i++)
            for(j=0;j<N;j++)
                edge[i][j]=0;//Matrisin tüm elemanları başlangıçta 0 olsun.
    }
    
    /*Graph'a kenar eklemeyi sağlayan metod.*/
    public void addEdge(int start,int finish, int distance){
        /*Başlangıç ve bitiş arasındaki mesafeyi 
        matrisin elemanı olarak belirledik.*/
        edge[start][finish]=distance;
    }   
}

Home.java

package finaldeneme5;

/*Diziler için bu kütüphaneyi import edelim.*/
import java.util.Arrays;
public class Home {

    /*Dizinin boyutu*/
    static int lengthArry=10;
    
    /*points isminde ve lengthArry boyutunda bir dizi tanımladık.*/
    static String[] points = new String[lengthArry];
    
    /*Herbir noktaya taşınacak konteynır sayısı.*/
    static int[] containers = new int[]{0,13,5,22,35,8,66,47,30,24};
    
    /*lengthArry değeri Graph sınıfında bulunan kurucu metoda gönderilir.
    Bu aşamada Graph oluşturulur.*/
    static Graph graph=new Graph(lengthArry);
    
    /*Bellman-Ford algoritması için ihtiyacımız olan değişkenler*/
    static int i,u,v,dy,d[],prev[];
    
    public static void main(String[] args) {
        fillArray();  
        addEdges();
        bellmanFord();
        printShortestPath();
        
    }
    /*points dizisini veriyle dolduran metot.*/
    public static void fillArray(){
        /*points dizinin ilk elemanı Merkez, 
        diğer elemanları ise D1, D2, D3, D4, D5, D6, D7, D8 ve D9*/
        for(int k=0;k<points.length;k++)
        {
            if(k==0)
                points[k]="Merkez";
            else
                points[k]="D"+k;
        }
    }
    
    /*Graph'a kenar eklemeyi sağlayan metot.
    Sorudaki bilgilere göre doldurduk.*/
    public static void addEdges(){
        graph.addEdge(getIndex("Merkez"), getIndex("D1"), 4);
        graph.addEdge(getIndex("D6"), getIndex("D9"), 3);
        graph.addEdge(getIndex("D2"), getIndex("D9"),4 );
        graph.addEdge(getIndex("D5"), getIndex("D4"), 3);
        
        graph.addEdge(getIndex("D1"), getIndex("D7"), 6);
        graph.addEdge(getIndex("Merkez"), getIndex("D2"),8 );
        graph.addEdge(getIndex("D5"), getIndex("D8"), 7);
        graph.addEdge(getIndex("D3"), getIndex("D6"), 5);
        
        graph.addEdge(getIndex("Merkez"), getIndex("D4"), 3);
        graph.addEdge(getIndex("D3"), getIndex("D7"), 2);
        graph.addEdge(getIndex("D4"), getIndex("D3"), 6);
        graph.addEdge(getIndex("D9"), getIndex("D5"), 4);
        
        graph.addEdge(getIndex("D5"), getIndex("D2"), 5);
        graph.addEdge(getIndex("D6"), getIndex("D5"), 2);
        graph.addEdge(getIndex("D2"), getIndex("D1"), 5);
        graph.addEdge(getIndex("D1"), getIndex("D4"), 2);
        
        graph.addEdge(getIndex("Merkez"), getIndex("D7"), 11);
        graph.addEdge(getIndex("Merkez"), getIndex("D5"),10 );
        graph.addEdge(getIndex("D8"), getIndex("D9"), 10);
        graph.addEdge(getIndex("D6"), getIndex("D8"), 4);
        
    }
    
    /*points dizisinde bulunan bir elemana ait index
    bilgisini bulan metot. Örneğin "Merkez" için bu değer sıfırdır.*/
    public static int getIndex(String point){
        return Arrays.asList(points).indexOf(point);
    }
    
    /*Bu algortima hazır olup başlangıç noktasından 
    diğer tüm noktalara olan en kısa yolu bulmayı sağlar.*/
    public static void bellmanFord(){
        d=new int[points.length];
        prev=new int[points.length];
        for(i=0;i<points.length;i++){
            d[i]=Integer.MAX_VALUE;
            prev[i]=-1;
        }
        d[0]=0;
        for(u=0;u<points.length;u++){
            for(v=0;v<points.length;v++){
                dy=graph.edge[u][v]+d[u];
                if(d[v]>dy){
                    d[v]=dy;
                    prev[v]=u;
                }
            }
        }
    }
    
    /*Merkez noktasından diğer tüm noktalara
    en kısa yolu bulmak için ilk adım*/
    public static void printShortestPath(){
        for(int x=1;x<points.length;x++)
            shortestPath(x);
    }
    
    /*Bu metot Merkez'den hedef noktaya olan en kısa 
    mesafeyi bulup ekrana yazar. Hedef noktaya ulaşmak
    için geçilecek tüm noktalar tek yönlü bir listeye eklenir.
    Sonrasında Merkez ve hedef nokta arasındaki kısa mesafe 
    ekrana yazdırılır.*/
    public static void shortestPath(int finish){
        SinglyLinkedList path = new SinglyLinkedList();
        Node e;
        i=finish;
        while(prev[i]!=-1){
            e=new Node(i);
            path.addNodeHeadList(e);
            i=prev[i];
        }
        e=new Node(i);
        path.addNodeHeadList(e);
        System.out.print(points[finish]+": "+containers[finish]
                                   +" konteynır\nEn az maliyetli yol:");
        path.displayData(points);
    }
        
}

Yukarıda verilen kodlar ile uygulamanızın ekran çıktısı aşağıdaki gibi olur.

Kaynak

http://inonu.edu.tr/tr/oguz.sen/3403/content

http://inonu.edu.tr/media/cms/announcement/62/2019/1/lab_s%C4%B1nav%C4%B1_v1.1.pdf

Paylaşmak İster misiniz
  •  
  •  
  •  
  •  

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

four × two =