Regina
1901457321
1901457321
Hari: Rabu, 01/06/2016
Kelas: CD01-CL
Lecturer:
Rulyna ( D4689 ) dan Henry Chong ( D4460 )
GRAPH
·
Graph
adalah struktur data yang abstrak yang digunakan untuk implementasi konsep graph
secara matematis.
·
Graph
adalah koleksi dari vertices (node) dan edges yang menghubungkan vertices.
 |
| Degree pada graph dihitung pada jumlah edges yang terhubung dengan suatu vertex. |
·
 |
| Vertex A memiliki 2 degree, Vertex B memiliki 4 degree dan seterusnya. |
·
Undirected
graph merupakan graph yang tiap edge tidak ada arahnya.
·
Directed
graph merupakan graph yang tiap edge ada arahnya.
·
Pada
directed graph, ada 2 macam degree:
o
Out-degree
: degree suatu edge yang mengarah keluar vertex
o
In-degree
: degree suatu vertex yang menuju ke vertex
Contoh
in-degree dan out-degree pada gambar directed graph diatas:
o
Out-degree:
1 : 1 , 2 : 2 , 3 : 1, 4 : 1 , 5 : 0
o
In-degree:
1 : 1 , 2 : 1 , 3 : 0 , 4 : 2 , 5 : 1
·
Adjecency
list adalah salah satu cara untuk mendeskripsikan koneksi pada graph. Dapat
di-implementasikan dengan array dan linked-list.
·
Minimum
Spanning Tree (MST) adalah tree yang merepresentasikan graph tanpa loop dan
dalam bentuk tree.
·
Ada
beberapa metode untuk membuat MST, Prim’s Algorithm dan Kruskal’s Algorithm.
PRIM’S
ALGORITHM
1. Buat array dengan nama T
2. Pilih vertex awal
3. Kapanpun tiap vertex ditunjuk, edge yang
terhubung akan ditandai sebaga aktif.
4. Bandingkan semua value edges yang aktif
lalu, cari value terkecil
5. Tambahkan node yang memiliki edge aktif terkecil
ke T
6. Ulang step 3-5 selama node di T masih
kurang dari total node yang ada.
KRUSKAL’S
ALGORITHM
1. Buat array dengan nama T
2. Sortir semua edge dengan menggunakan heap
(priority queue)
3. Ambil value paling kecil pada edge
4. Jika ada loop, lanjut ke edge berikutnya
5. Jika tidak ada loop, tambahkan edge
tersebut ke T
6. Ulang step 3-5 sampai semua vertex
dikunjungi
·
Shortest
path adalah metode untuk menemukan jalur terpendek dari graph dengan awal dan
akhir vertex yang spesifik.
·
Metodenya
menggunakan Dijkstra’s Algorithm
DIJKSTRA’S
ALGORITHM
1. Pilih node inisial/awal.
2. Definisikan N sebagai empty set.
3. Label node inisial tersebut dengan 0, dan
masukkan ke N
4. Lakukan step 5-7 sampai node akhir sudah
di N atau tidak adalahi mode labelled nodes di N
5. Pertimbangkan semua node yang tidak ada
di N dan yang terhubung dengan edge dari node yang baru di tambahkan
6. Ada 2 kemungkinan:
a. Jika
node yang tidak ada di N tidak ada label lalu, set label pada node = label dari node yang baru di
insert + panjang edge
b. Jika
node yang tidak ada di N ada label
lalu, set label node = minimum (label dari vertex yang baru di insert + panjang
edge, label lama)
7. Ambil node yang tidak ada di N yang
memiliki label terkecil dan tambahkan pada N
