Graph

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                                                                               

Tree dengan arah

Tree adalah graph yang tidak ada jalur memutar

Edge merah harus dihapus.

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