ALGORITMA &STRUKTUR DATA BAB 11 : ADT GRAPH

Laporan Praktikum algoritma & Struktur Data Bab 11 Fakultas Ilmu Komputer Universitas Brawijaya 2017/2018

Soal :

     1.       Buatlah method untuk mendapatkan tetangga dari suatu node tertentu

     2.       Buatlah method untuk penelusuran Depth-First-Search(DFS)!

    3.       Lakukan modifikasi pada ADT graph di atas sehingga suatu hubungan antar node terdapat nilai jarak.

    4.       Berdasarkan hasil modifikasi pada tugas 5 susun method untuk menghitung jarak terpendek dari suatu node asal ke node tujuan.

Source code :
Soal no.1 & 2
Class Bab11Graph

package asdmodul4;

class nodeGr {

    int data, jarak;
    nodeGr next;

    nodeGr(int data) {
        this.data = data;
        this.next = null;
    }
    nodeGr(int data, int jarak){
        this.data = data;
        this.jarak = jarak;
    }
}

public class Bab11Graph {

    private nodeGr nodeAwal;
    private nodeGr nodeAkhir;

    public Bab11Graph() {
        nodeAwal = nodeAkhir = null;
    }

    public void sisipDiAkhir(int dt) {
        nodeGr newNode = new nodeGr(dt);
        if (kosong()) {
            nodeAkhir = nodeAwal = newNode;
        } else {
            nodeAkhir.next = newNode;
            nodeAkhir = newNode;
        }
    }

    public int hapusDrDepan() {
        int itemDihapus = -99;
        if (!kosong()) {
            itemDihapus = nodeAwal.data;
            if (nodeAwal == nodeAkhir) {
                nodeAwal = nodeAkhir = null;
            } else {
                nodeAwal = nodeAwal.next;
            }
        }
        return itemDihapus;
    }

    public boolean kosong() {
        return nodeAwal == null;
    }
}

Class Bab11Queue

package asdmodul4;

public class Bab11Queue {

    private Bab11Graph listAntrian;

    public Bab11Queue() {
        listAntrian = new Bab11Graph();
    }

    public void enqueue(int dt) {
        listAntrian.sisipDiAkhir(dt);
    }

    public int dequeue() {
        return listAntrian.hapusDrDepan();
    }

    public boolean isEmpty() {
        return listAntrian.kosong();
    }
}

Class Bab11AdjacencyMatrix

package asdmodul4;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

public class Bab11AdjacencyMatrix {

    private int size;
    private boolean[][] adj;
    private LinkedList ad[];
    
    Bab11AdjacencyMatrix(int size) {
        this.size = size;
        this.adj = new boolean[size][size];
        ad = new LinkedList[size];
        for (int i = 0; i < size; ++i) {
            ad[i] = new LinkedList();
        }
    }

    void addEdge(int i, int j) {
        this.adj[i][j] = true;
        this.ad[i].add(j);
    }

    void removeEdge(int i, int j) {
        this.adj[i][j] = false;
    }

    boolean hasEdge(int i, int j) {
        return this.adj[i][j];
    }

    List outEdges(int i) {
        List edges = new ArrayList<>();
        for (int j = 0; j < size; j++) {
            if (this.adj[i][j]) {
                edges.add(j);
            }
        }
        return edges;
    }

    List inEdges(int i) {
        List edges = new ArrayList();
        for (int j = 0; j < size; j++) {
            if (this.adj[j][i]) {
                edges.add(j);
            }
        }
        return edges;
    }

    //BFS menggunakan antrian 
    public void BreadthFirstSearch(int nodeAwal) {
        boolean[] terkunjungi = new boolean[size];
        Bab11Queue q = new Bab11Queue();
        q.enqueue(nodeAwal);
        terkunjungi[nodeAwal] = true;
        System.out.printf("%d ", nodeAwal);
        while (!q.isEmpty()) {
            int i = q.dequeue();
            for (int j : this.outEdges(i)) {
                if (!terkunjungi[j]) {
                    q.enqueue(j);
                    terkunjungi[j] = true;
                    System.out.printf("%d ", j);
                }
            }
        }
        System.out.println("");
    }

    void DFS(int s, boolean terkunjungi[]) {
        terkunjungi[s] = true;
        System.out.print(s + " ");
        Iterator z = ad[s].listIterator();
        while (z.hasNext()) {
            int h = z.next();
            if (!terkunjungi[h]) {
                DFS(h, terkunjungi);
            }
        }
    }

    void DepthFirstSearch(int s) {

        boolean terkunjungi[] = new boolean[size];
        DFS(s, terkunjungi);
    }

    void cetak(int s, int z, int h) {
        ad[s].add(new nodeGr(z, h));
        ad[z].add(new nodeGr(s, h));
        System.out.println("Jarak dari node " + s + " ke node " + z + " : " + h);
    }
    
    public static void main(String[] args) {
        Bab11AdjacencyMatrix graph = new Bab11AdjacencyMatrix(8);
        graph.addEdge(0, 1);
        graph.addEdge(0, 4);
        graph.addEdge(1, 0);
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 5);
        graph.addEdge(3, 1);
        graph.addEdge(3, 5);
        graph.addEdge(3, 7);
        graph.addEdge(4, 2);
        graph.addEdge(4, 6);
        graph.addEdge(6, 4);
        graph.addEdge(6, 7);
        graph.addEdge(7, 5);
        System.out.println("Hasil penelusuran BFS mulai node 0 : ");
        graph.BreadthFirstSearch(0);
        System.out.println("Hasil penelusuran DFS mulai node 0 : ");
        graph.DepthFirstSearch(0);
        System.out.println("\n==========Tetangga terdekat==========");
        System.out.println(graph.inEdges(0) + " , " + graph.outEdges(0));
        System.out.println(graph.inEdges(1) + " , " + graph.outEdges(1));
        System.out.println(graph.inEdges(2) + " , " + graph.outEdges(2));
        System.out.println(graph.inEdges(3) + " , " + graph.outEdges(3));
        System.out.println(graph.inEdges(4) + " , " + graph.outEdges(4));
        System.out.println(graph.inEdges(5) + " , " + graph.outEdges(5));
        System.out.println(graph.inEdges(6) + " , " + graph.outEdges(6));
        System.out.println(graph.inEdges(7) + " , " + graph.outEdges(7));
        System.out.println("\n===========Jarak Antara Node===========");
        graph.cetak(0, 1, 6);               
        graph.cetak(0, 4, 5);        
        graph.cetak(1, 0, 3);        
        graph.cetak(1, 2, 4);
        graph.cetak(1, 3, 4);
        graph.cetak(2, 5, 2);
        graph.cetak(3, 1, 6);
        graph.cetak(3, 5, 4);
        graph.cetak(3, 7, 3);
        graph.cetak(4, 2, 4);
        graph.cetak(4, 6, 6);
        graph.cetak(6, 4, 2);
        graph.cetak(6, 7, 4);
        graph.cetak(7, 5, 5);      
    }
}

Soal no.3 & 4

package asdmodul4;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

class Vertex implements Comparable {

    public final String data;
    public Edge[] adjacencies;
    public double minDistance = Double.POSITIVE_INFINITY;
    public Vertex previous;

    public Vertex(String argName) {
        data = argName;
    }

    public String toString() {
        return data;
    }

    @Override
    public int compareTo(Vertex dll) {
        return Double.compare(minDistance, dll.minDistance);
    }
}

class Edge {

    public final Vertex v;
    public final double jarak;

    public Edge(Vertex ve, double jar) {
        v = ve;
       jarak = jar;
    }
}

public class BEYUAN {

    public static void hitungJarak(Vertex src) {
        src.minDistance = 0.;
        PriorityQueue vq = new PriorityQueue();
        vq.add(src);
        while (!vq.isEmpty()) {
            Vertex u = vq.poll();
            for (Edge e : u.adjacencies) {
                Vertex v = e.v;
                double weight = e.jarak;
                double distanceThroughU = u.minDistance + weight;
                if (distanceThroughU < v.minDistance) {
                    vq.remove(v);
                    v.minDistance = distanceThroughU;
                    v.previous = u;
                    vq.add(v);
                }
            }
        }
    }

    public static List jalanTikus(Vertex target) {
        List path = new ArrayList();
        for (Vertex vertex = target; vertex != null; vertex = vertex.previous) {
            path.add(vertex);
        }

        Collections.reverse(path);
        return path;
    }

    public static void main(String[] args) {
        Vertex A = new Vertex("0");
        Vertex B = new Vertex("1");
        Vertex D = new Vertex("2");
        Vertex E = new Vertex("4");        
        Vertex K = new Vertex("3");        
        Vertex O = new Vertex("7");
        Vertex P = new Vertex("5");
        Vertex R = new Vertex("6");
        Vertex Z = new Vertex("4");
        
        A.adjacencies = new Edge[]{new Edge(B, 8), new Edge(E, 18)};
        B.adjacencies = new Edge[]{new Edge(A, 10), new Edge(D, 11), new Edge(O, 20)};
        D.adjacencies = new Edge[]{new Edge(P, 11)};        
        K.adjacencies = new Edge[]{new Edge(B, 13), new Edge(P, 7), new Edge(O, 40)};
        E.adjacencies = new Edge[]{new Edge(D, 10), new Edge(R, 16)};
        R.adjacencies = new Edge[]{new Edge(E, 15), new Edge(O, 23)};
        O.adjacencies = new Edge[]{new Edge(P, 40)};      
        
        P.adjacencies = new Edge[]{new Edge(Z, 18)};
        R.adjacencies = new Edge[]{new Edge(P, 15)};
        Z.adjacencies = new Edge[]{new Edge(P, 18)};

        hitungJarak(A); 
        System.out.println("Jarak dari node " + A + " ke " + B + ": " + B.minDistance);
        hitungJarak(A); 
        System.out.println("Jarak dari node " + A + " ke " + E + ": " + E.minDistance);
        hitungJarak(B); 
        System.out.println("Jarak dari node " + B + " ke " + A + ": " + A.minDistance);
        hitungJarak(B); 
        System.out.println("Jarak dari node " + B + " ke " + D + ": " + D.minDistance);
        hitungJarak(B);
        System.out.println("Jarak dari node " + B + " ke " + K + ": " + K.minDistance);
        hitungJarak(D); 
        System.out.println("Jarak dari node " + D + " ke " + P + ": " + P.minDistance);
        hitungJarak(K); 
        System.out.println("Jarak dari node " + K + " ke " + B + ": " + B.minDistance);
        hitungJarak(K); 
        System.out.println("Jarak dari node " + K + " ke " + P + ": " + P.minDistance);
        hitungJarak(K); 
        System.out.println("Jarak dari node " + K + " ke " + O + ": " + O.minDistance);
        hitungJarak(E); 
        System.out.println("Jarak dari node " + E + " ke " + D + ": " + D.minDistance);
        hitungJarak(E); 
        System.out.println("Jarak dari node " + E + " ke " + R + ": " + R.minDistance);        
        hitungJarak(R);
        System.out.println("Jarak dari node " + R + " ke " + E + ": " + E.minDistance);        
        hitungJarak(R);
        System.out.println("Jarak dari node " + R + " ke " + O + ": " + O.minDistance);        
        hitungJarak(O);
        System.out.println("Jarak dari node " + O + " ke " + P + ": " + P.minDistance);                
        System.out.println();
        List jl1 = jalanTikus(A);
        System.out.println("Jarak terdekat A: " + jl1);
        List jl2 = jalanTikus(B);
        System.out.println("Jarak terdekat B: " + jl2);
        List jl3 = jalanTikus(D);
        System.out.println("Jarak terdekat D: " + jl3);
        List jl4 = jalanTikus(K);
        System.out.println("Jarak terdekat K: " + jl4);
        List jl5 = jalanTikus(E);
        System.out.println("Jarak terdekat E: " + jl5);
        List jl6 = jalanTikus(O);
        System.out.println("Jarak terdekat O: " + jl6);
    }
}

Download the file here