🛣️Praktikum 1

Graf dengan Linked List

Deskripsi

Pada percobaan ini akan diimplementasikan Graph menggunakan linked list untuk merepresentasikan graph adjacency. Struktur data linked list yang digunakan merupakan package / library dari Java.

Langkah Percobaan

• Buatlah kelas Graph.

• Tambakan atribur vertices dan array dengan nama list bertipe list. Jangan lupa import package LinkedList kedalam kelas Graph.

import java.util.LinkedList;

public class Graph {
    int vertex;
    LinkedList<Integer> list[];

• Tambakan konstruktor didalam kelas Graph.

public Graph(int vertex) {
    this.vertex = vertex;
    list = new LinkedList[vertex];
    for (int i = 0; i < vertex; i++) {
        list[i] = new LinkedList<>();
    }
}

• Tambahkan method addEdge(). Jika yang akan dibuat adalah graph berarah, maka yang dijalankan hanya baris pertama saja. Jika graph tidak berarah yang dijalankan semua baris pada method addEdge().

public void addEdge(int source, int destination) {
    // add edge
    list[source].addFirst(destination);
    
    // add back edge ((for undirected)
    list[destination].addFirst(source);
}

• Tambahkan method degree() untuk menampilkan jumlah derajat lintasan pada suatu vertex. Di dalam metode ini juga dibedakan manakah statement yang digunakan untuk graph berarah atau graph tidak berarah. Eksekusi hanya sesuai kebutuhan saja.

public void degree(int source) throws Exception {
        // degree undirected graph
        System.out.println("Degree of " + source + " is " + list[source].size());

        // degree directed graph
        int k, totalIn = 0, totalOut = 0;
        for(int i = 0; i < vertex; i++){
            for(int j = 0; j < list[i].size(); j++){
                if(list[i].get(j) == source)
                    ++totalIn;
            }
            for(k = 0; k < list[source].size(); k++){
                list[source].get(k);
            }
            totalOut = k;
        }
        System.out.println("Indegree of " + source + " is " + totalIn);
        System.out.println("Outdegree of " + source + " is " + totalOut);
        System.out.println("Degree of " + source + " is " + (totalIn + totalOut));
    }

• Tambahkan method removeEdge(). Method ini akan menghapus lintasan ada suatu graph. Oleh karena itu, dibutuhkan 2 parameter untuk menghapus lintasan yaitu source dan destination.

public void removeEdge(int source, int destination) throws Exception {
    for (int i = 0; i < vertex; i++) {
        if (i == destination) {
            list[source].remove(destination);
        }
    }
}

• Tambahkan method removeAllEdges() untuk menghapus semua vertex yang ada di dalam graph.

public void removeAllEdges() {
    for (int i = 0; i < vertex; i++) {
        list[i].clear();
    }
    System.out.println("Graph is cleared");
}

• Tambahkan method printGraph() untuk mencatak graph ter-update.

public void printGraph() {
    for (int i = 0; i < vertex; i++) {
        if (list[i].size() > 0) {
            System.out.print("Vertex " + i + " is connected to: ");
            for (int j = 0; j < list[i].size(); j++) {
                System.out.print(list[i].get(j) + " ");
            }
            System.out.println();
        }
    }
    System.out.println();
}

• Buatlah kelas MainGraph dan tambahkan main method seperti berikut.

public static void main(String[] args) throws Exception {
    Graph graph = new Graph(6);
    graph.addEdge(0, 1);
    graph.addEdge(0, 4);
    graph.addEdge(1, 2);
    graph.addEdge(1, 3);
    graph.addEdge(1, 4);
    graph.addEdge(2, 3);
    graph.addEdge(3, 4);
    graph.addEdge(3, 0);
    graph.printGraph();
    graph.degree(2);
}

• Compile dan jalankan main class. Amati hasilnya.

Vertex 0 is connected to: 3 4 1 
Vertex 1 is connected to: 4 3 2 0 
Vertex 2 is connected to: 3 1 
Vertex 3 is connected to: 0 4 2 1 
Vertex 4 is connected to: 3 1 0 

Degree of 2 is 2
Indegree of 2 is 2
Outdegree of 2 is 2
Degree of 2 is 4

• Tambahkan pemanggilan method removeEdge() sesuai potongan code di bawah ini pada main method. Kemudian tampilkan graph tersebut.

graph.removeEdge(1, 2);
graph.printGraph();

• Amati hasilnya.

Vertex 0 is connected to: 3 4 1 
Vertex 1 is connected to: 4 3 0 
Vertex 2 is connected to: 3 1 
Vertex 3 is connected to: 0 4 2 1 
Vertex 4 is connected to: 3 1 0 

Pertanyaan

1. Sebutkan beberapa jenis (minimal 3) algoritma yang menggunakan dasar graph, dan apakah kegunaan algoritma-algoritma tersebut?

2. Pada class Graph terdapat array bertipe LinkedList, yaitu LinkedList list[]. Apakah tujuan pembuatan variabel tersebut ?

3. Apakah alasan pemanggilan method addFirst() untuk menambahkan data, bukan method add jenis lain pada linked list ketika digunakan pada method addEdge() pada class Graph?

4. Bagaimana cara mendeteksi prev pointer pada saat akan melakukan penghapusan suatu edge pada graph?

5. Kenapa pada praktikum langkah untuk menghapus path yang bukan merupakan lintasan pertama kali (perhatikan main class) menghasilkan output yang salah ? Bagaimana solusinya ?