GRAPH
Graph adalah abstract data structure yang dapat mengimplementasikan konsep matematika
dalam suatu graph.
Graph terdiri dari:
- Vertex / Vertices / Nodes
- Edges = Garis penghubung antar nodes
2 Jenis graph :
–> Undirected Graph : graph yang edges-nya tidak memiliki panah.
–> Directed Graph : graph yang edges-nya memiliki panah.
Adjacency List Matrix
Adjacency List Matrix adalah salah satu cara untuk mendeskripsikan hubungan dalam graph.
Minimum Spanning Tree (MST)
Minimum Spanning Tree adalah sebuah tree yang merepresentasikan graph dan tidak memiliki loop.
Algoritma Prim
Langkah-langkah Algoritma Prim :
- Buat array dengan nama T.
- Pilih Vertex awal.
-
Setiap vertex yg ditunjuk, edge yang terhubung dengannya akan dibuat aktif.
- Bandingkan nilai/value setiap edge yang aktif, cari yang valuenya paling kecil.
- Masukkan node yang memiliki edge aktif ke dalam T.
- Lakukan step 3 sampai 5 selama node T lebih sedikit dari jumlah node yg ada.
Algoritma Kruskal
Langkah-langkah Algoritma Kruskal :
- Buat array dengan nama T.
- Sort/urutkan semua edges menggunakan heap (priority queue).
- Ambil value minimum dari edge.
- Kalau ada yang menghasilkan loop, lanjut ke edge selanjutnya.
- Kalau tidak loop, masukkan edge ke T.
- Lakukan step 3 sampai 5 sampai semua vertex sudah di check.
Shortest Path
Shortest path adalah mencari jalan terpendek dari suatu graph dengan vertex awal dan vertex akhir yang spesifik.
Algoritma Dijkstra
- Pilih initial node.
- Define N sebagai set kosong.
- initial node di label sebagai 0, lalu masukkan ke N.
- Lihat setiap node yang tidak ada di N dan yang tersambung oleh suatu edge dari node yang baru dimasukkan tadi.
- Kalau node yang tidak ada di N belum memiliki label maka set label node sama seperti node yang baru di masukkan.
- Ambil node yang tidak ada di N yang memiliki label terkecil yang di assign thd node itu dan masukkan itu ke N.
- Lakukan step 4 sampai 6 sampai node yang dituju ada dalam N atau sampai tidak ada lagi node yang terlabel di N.
