Heap Java

Pengertian:

Heap Adalah struktur data yang berbentuk pohon yang memenuhi sifat-sifat heap yaitu jika B adalah anak dari A, maka nilai yang tersimpan di simpul A lebih besar atau sama dengan nilai yang tersimpan di simpul B.

 

Jenis-jenis heap:

Min Heap  : Nilai setiap node lebih kecil dari anak-anaknya

Contoh Min Heap:

Max Heap : Nilai setiap node lebih besar dari anak-anaknya

Operasi-operasi yang digunakan untuk heap adalah:

1. Delete-max atau delete-min: menghapus simpul akar dari sebuah max atau min heap.  
2. Increase-key atau decrease-key: mengubah nilai yang tersimpan di suatu simpul. 
3. Insert: menambahkan sebuah nilai ke dalam heap.  
4. Merge: menggabungkan dua heap untuk membentuk sebuah heap baru yang berisi semua elemen pembentuk heap tersebut. 

Implementasi pada array:

1. Unsur-unsur disimpan berurutan dari indeks 1 sampai N dari atas ke bawah dan dari kiri ke kanan node pohon.
2. Root disimpan dalam indeks 1 (kita membiarkan indeks 0 menjadi kosong / tidak terpakai).

Representasi array:

Memasukkan Min-Heap

• Masukkan unsur baru pada akhir heap
• Naikkan heap baru/angka yang perlu dinaikkan

Penghapusan pada Min-Heap

• Perhatikan penghapusan elemen terkecil yang terletak pada akar.
• Ganti root dengan elemen terakhir dari heap
• Penurunan jumlah elemen dalam tumpukan
• Memperbaiki properti heap nya

Min-Max Heap

• Kondisi tumpukan bergantian antara tingkat minimum dan maksimum untuk tingkat
• Tujuan min-max tumpukan adalah untuk memungkinkan kita untuk menemukan keduaelemen terkecil 

   dan terbesar dari tumpukan pada waktu yang sama. 

Penghapusan pada Min-Max Heap

• Penghapusan elemen terkecil:
  - Ganti root dengan elemen terakhir dalam tumpukan.
  - Penurunan jumlah elemen dalam tumpukan.
  - Downheapmin dari root.

• Penghapusan elemen terbesar:
  - Ganti anak kiri atau kanan-anak dari akar (tergantung pada mana yang lebih besar) dengan elemen

     terakhir dalam tumpukan.
  - Penurunan jumlah elemen dalam tumpukan.
  - Downheapmax dari node.

Graph

Definisi Graph

Graph adalah kumpulan dari simpul dan busur yang secara matematis dinyatakan sebagai :

G = (V, E)

Dimana :  

G = Graph

V = Simpul atau Vertex, atau Node

E = Busur atau Edge, atau arc

Sifat-Sifat Graph

žSebuah graph mungkin hanya terdiri dari satu simpul

 

 

 

 

 

žSebuah graph belum tentu semua simpulnya terhubung dengan busur

 

  

ž

žSebuah graph mungkin mempunyai simpul yang tak terhubung dengan simpul yang lain 

 

 

 

žSebuah graph mungkin semua simpulnya saling berhubungan

 

  

 

Contoh Graph

 

 

V terdiri dari V1, V2, V3 .....,V5 

E terdiri dari e1, e2, e3, .....,e5

Dimana :

V = Vertex

E = Edge

 

 

Istilah-Istilah dalam Graph

 

žIncident

  Jika e merupakan busur dengan simpul-simpulnya adalah v dan w yang ditulis e=(v,w), maka v dan w disebut “terletak” pada e, dan e disebut incident dengan v dan w.

žDegree

  Degree dari suatu verteks x dalam undigraph adalah jumlah busur yang incident dengan simpul tersebut.

 

žIndegree

  Indegree dari suatu verteks x dalam digraph adalah jumlah busur yang kepalanya incident dengan simpul tersebut, atau jumlah busur yang “masuk” atau menuju simpul tersebut.

 

žOut Degree

  Outdegree dari suatu verteks x dalam digraph adalah jumlah busur yang ekornya incident dengan simpul tersebut, atau jumlah busur yang “keluar” atau berasal dari simpul tersebut.

 

žAdjacent

      Pada graph tidah berarah, 2 buah simpul disebut adjacent bila ada busur yang  menghubungkan kedua simpul tersebut. Simpul v dan w disebut adjacent.

 

 

     Pada graph berarah, simpul v disebut adjacent dengan simpul w bila ada busur dari w ke v.

žSuccessor dan Predecessor

  Pada graph berarah, bila simpul v adjacent dengan simpul w, maka simpul v adalah successor simpul w, dan simpul w adalah predecessor dari simpul v.

žPath

  Sebuah path adalah serangkaian simpul-simpul berbeda yang adjacent secara berturut-turut dari simpul satu ke simpul berikutnya.

 Representasi Graph dalam Matrik

 

 

    Kotak yang berisi angka satu menunjukan bahwa dalam dua vertex tersebut terdapat edge yang menghubungkannya. Dan jika dalam kotak terdapat angka nol, maka hal tersebut menandakan tidak ada edge yang mengubungkan secara langsung dua vertex tersebut.

 

    Pada Weighted Direct Graph, penulisan matrix tidak menggunakan angka no 1 dan 0 lagi, melainkan menggunakan nilai (bobot) jika ada edge yang menghubungkan dua buah verterx dan nilai 0 jika tidak ada edge yang menghubungkan vertex - vertex tersebut.

 

 

Jenis-Jenis Graph

 

Derected Graph

 

Sebuah Graph yang sisi atau busurnya berlaku satu arah saja, sesuai dengan arah tanda panah.

Misal :

e1 = (A,B)

Berarti hanya berlaku untuk Graph A ke B saja, tidak berlaku

Untuk B ke A

 

 

 

 

 

 

 

 

 

 

Undirect Graph

 

Graph yang sisi atau busurnya bisa berlaku ke dua Arah. Secara Grafik dapat dilihat tidak ada arah panah pada Busur.

Edge pada Undigraph bisa direpresentasikan sebagai garis dengan panah 2 arah.

Misal :

e1 = (A,B)

e1 = Bisa dikatakan Graph A ke B atau Graph B ke A

 

 

 

Weighted Graph

ž

  

 

 

Weighted Graph adalah Graph yang sisi / busurnya memiliki nilai (bobot). Weighted Graph terdiri dua jenis :

  - Weighted Direct Graph

          Bobot berlaku satu arah saja

  - Weighted Undirect Graph

Bobot Berlaku 2 arah

Metode Pencarian Vertex

 

Depth first search (DFS)

 

žPencarian dengan metode ini dilakukan dari node awal secara mendalam   hingga yang paling akhir (dead-end) atau sampai ditemukan

  

 

 

žKelebihan :

  - Cepat Mencapai kedalaman ruang pencarian

  - Tidak boros waktu, jika lintasannya panjang

  - Lebih efisien

žKekurangan

  - Memungkinkan tidak ditemukan tujuan yang di harapkan

  - Pada setiap pencarian hanya menghasilkan 1 solusi saja

ž

BREADTH FIRST SEARCH (BFS)

žProsedur Breadth First Search merupakan pencarian yang dilakukan dengan mengunjungi tiap-tiap node secara sistematis pada setiap  level  hingga  keadaan tujuan (goal  state) ditemukan.

 

 

 

žKelebihan

  - Tidak akan menemukan jalan Buntu

  - Jika lebih dari solusi, maka BFS akan solusi minimum akan ditemukan

žKekurangan

  - Menyimpan memori yang besar karena menyimpan semua node yang ada dalam satuatu pohon. 

 

 

 Minimmum Spanning Tree

žSpanning Tree adalah sebuah cabang yang terbentuk dari subset edge-edge serta menghubungkan setiap vertex dalam suatu Graph.

ž

žMinimum Spanning Tree adalah total bobot minimal dari edge-edge yang menghubungkan setiap vertex.

 

žAlgoritma MST :

  1. Algoritma Kruskal

  2. Algoritma Prim

žContoh Minimum Spanning Tree

  Unweighted Undirect Graph

 

Kemungkinan MST

GRAPH pada JAVA

žUntuk pengaplikasian teori Graph dapat di lakukan pada program Java.  

Software yang kita gunakan pada Program yang kita buat adalah Eclipse žUntuk pengaplikasian teori Graph dapat di lakukan pada program Java.

Software yang kita gunakan pada Program yang kita buat adalah Eclipse.

žPada Package GRAPH_BASIC

  Terdapat 5 file berextensi .java yang saling berhubungan.

 

Untuk melakukan Logika pada package GRAPH_BASIC

terdapat pada file main.java

Output yang di hasilkan akan seperti di Bawah ini

 

Referensi:

http://gallerycode.files.wordpress.com/2010/11/graph1.pptx‎