Pertemuan ke 9
 6 Juni 2016
Graph 
 
Suatu structure data yang diimplementasikan dari graph dalam matematika 
Graph adalah kumpulan node(vertex) yang di sambung dengan garis yang kita sebut edges
Degree adalah jumlah edges yg terhubung dengan vertex tertentu. 
dari gambar berikut kita dapat menentukan
Degree 2 = 4
Degree 1 = 2
Undirected Graph
Undirected graph adalah graph yang tidak memiliki arah di edge nya.
Setiap vertex / node itu terhubung 2 arah 
contoh 1 - 2 maka kita dapat melihat bahwa 1 bisa ke 2 dan 2 bisa ke 1 
sehingga ini kita sebut sebagai terhubung 2 arah

Directed Graph
Directed Graph adalah graph yang setiap node terhubungan dengan edge yang memiliki arah
seperti contoh dibawah bahwa A terhubung dengan B tetapi B tidak terhubung dengan A 
Directed graph terbagi menjadi 2 jenis:
yaitu in-Degree dan out-Degree. 
In-Degree adalah total edge yang menuju ke verteks / node tersebut, 
out-Degree adalah total edge yang keluar dari vertex / node tersebut

MINIMUM SPANNING TREE
adalah graph dengan nilai terkecil dan path terpendek 
tidak boleh ada loop dan semua vertex harus di lalui semua


Untuk dapat mencari MST terdapat 3 cara, yaitu:
1. Prim's Algorithm
Mencari jalan yg costnya terkecil dari setiap path.dan cukup mengikuti arus dari edge-edge tersebut. terdapat 5 verteks A B C D E  jika kelima verteks telah dikunjungi semua, maka algoritma berhenti.

2. Kruskal's Algorithm
Semua cost dari edges disort terlebih dahulu, lalu dicari path yang costnya terkecil. Verteks yg sudah dikunjungin ditulis, lalu dilanjutkan sampai semua path nya dimasukan tentunya seperti diatas bahwa tidak boleh ada looping pada saat di cek jika ditemukan maka itu tidak di jalankan lalu cek apakan semua vertex sudah di kunjungi
3. Dijkstra's Algorithm
tidak jauh berbeda dengan cara prim yaitu mencari jalan dengan mengikuti arus tetapi dengan dijkstra kita harus menghitung akumulasi nya lalu dari situ kita mengambil nilai terkecil misal A B E total nilai diakumulasi adalah 3 + 1 = 4 , dengan A C E total nilai diakumulasi nya adalah 6 + 4 = 10 , A D E total nya adalah 1 + 2 = 3 dan beberapa path sisa nya dimana dari nilai ini kita dapat melihat path mana dengan nilai terkecil jika dari 3 path ini maka kita dapat menyimpulkan ADE adalah nilai terkecil akan tetapi Di dalam Algorithm ini, semua kemungkinan harus dicoba. kemudian diambil yg costnya paling rendah, cost terkecil itu diambil dari awal sampai selesai ( A - E )