Graph adalah
konsep matematika yang terdiri dari verteks/node yang dihubungkan oleh edge.
Dalam hal ini, graph akan diimplementasikan dalam struktur data abstrak.
Contoh graph:
Maps, Family
Tree, Tree, Spanning Tree.
Jenis graph:
berarah, tidak berarah
Degree dari
verteks adalah jumlah edge yang tersambung (loop dihitung 2)
Degree dari
setiap verteks dapat diimplementasikan dalam matriks
Tree tanpa arah
Spanning tree
adalah tree dengan weight paling rendah. Weight dihitung dari weight setiap
edge.
Contoh : edge dengan nilai besar akan dihilangkan untuk membentuk tree
dengan weight terendah.
Edge yang tidak diperlukan dihilangkan
Metode untuk
mencari spanning tree adalah Prim dan Kruskal.
Prim memilih 1
node lalu mencari edge terendah dari node yang telah dipilih.
Kruskal
mengurutkan edge paling rendah terlebuh dulu.
Dijkstra
adalah metode mencari path terpendek.
Contoh , A ke
F.
A-D-F = 5
A-D-C-E-F = 5
A-D-E-F
= 4
