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