Graph adalah sebuah struktur data yang abstrak dimana didalamnya menggunakan fungsi-fungsi graph matematika. Didalam sebuah graph terdapat node dan edges. Edge adalah "tangan" yang dimilliki oleh suatu node.
Ada dua macam graph, yaitu:
Directed Graph
Undirected Graph
Seperti yang dapat dilihat dua graph diatas, Directed graph memiliki panah di edge(s) nya sedangkan di undirected graph lalu karena terdapat panah maka node yang menunjuk disebut sebagai in-degree dan yang ditunjuk sebgai out-degree. Sedangkan undirected graph memiliki degree yaitu adalah jumlah "tangan" dari sebuah node.
Minimum Spanning Tree (MST)
Minimum Spanning Tree adalah graph dimana tidak ada loop terbentuk didalamnya. Tujuan dari penggunaan MST adalah untuk menentukan cost dari jalan yang paling kecil pada suatu graph.
Minimum Spanning Tree dapat ditentukan melalui tiga cara yaitu Prim's Algorithm, Kruskal's Algorithm, dan Djikstra's Algorithm. Berikut adalah cara-cara menentukan MST:
Djikstra Algorithm
Tidak ada komentar:
Posting Komentar