Data Structure – Pertemuan 9
Graph
Graph merupakan suatu struktur data yang biasanya diimplementasi dalam konsep matematika.
Graph biasa digunakan dalam membuat maps, family tree, dan game.
Graph berfungsi sebagai penentu jarak terpendek/jalan pintas.
Di dalam graph terdapat edge yaitu berupa garis penghubung dan vertex yaitu berupa bentuknya yang dihubungkan oleh edge.
Contoh :
Bentuk matrix
Bentuk link list
Di dalam graph ada yang namanya degree yaitu berapa edge yang terhubung dari suatu vertex ke vertex lain.
Contoh dari bentuk link list(angka 2 memiliki degree 1 yaitu 3 sedangkan angka 3 memiliki degree 2 yaitu 1 dan 4).
Di dalam graph juga terdapat weight yaitu berat dari setiap edge.
Contoh dari bentuk matrix(angka 2, 3, 15, 13, 9 yang terdapat di edge merupakan weight).
Di dalam graph juga terdapat minimum spanning tree(MST).
Ada 2 macam MST :
- MST prism’s algorithm
- MST kruskal’s algorithm
Contoh :
Minimum Spanning Tree
Prism’s algorithm
Kruskal’s algorithm
Ada 1 lagi algoritma untuk menentukan rute terpendek yaitu Dijkstra’s Algorithm.
Contoh Dijkstra :
Dijkstra sama seperti minimum spanning tree yang bertujuan untuk mencari rute terpendek/harus melewati rute dengan weight terkecil.
