HELLO

Graph adalah data struktur yang bersifat abstrak, di dalam graph suatu titik disebut vertex dan garis penghubung setiap vertex disebut dengan edges, sedangkan degree adalah berapa banyak jumlah edges yang terhubung dengan sebuah vertex.

Selain itu, juga terdapat 2 jenis graph yaitu directed graph dan undirected graph, dimana

Directed graph adalah graph yang edgenya memiliki arah.

Undirected graph hanya memiliki edge berupa garis saja.

Untuk menemukan minimm spanning tree di dalam graph dapat digunakan 2 metode yaitu:

Prim algorithm

Kruskal algorithm

PRIM ALGORITHM

Algotima untuk prim adalah dengan cara memilih 1 titik awal kemudian kita menentukan lagi jalan berikutnya yang harus diambil dengan fee atau cost terkecil. Sehingga pada intinya prim algorithm memiliki cara menentukan jalan step by step.

KRUSKAL ALGORITHM

Algoritma kruskal sedikit berbeda dengan prim meskipun mereka memiliki tujuan yang sama yaitu untuk mendapatkan cost atau fee terkecil untuk dadpat mengelilingi semua vertex yang ada. Pada kruskal yang dilakukan adalah mengumpulkan terlebih dahulu edge edge dengan cost terkecil kemudian barulah setial edge edge tersebut dihubungkan.

Selain itu juga ad acara untuk menemukan the shortest path dimana disebut Dijkstra

Di dalam Dijkstra biasanya akan sedikit berbeda, dimana biasanya kita akan mencari jalan dengan cost terkecil untuk menuju suatu vertex yang telah ditentukan.

Misalnya:

Temukan shoetest path menuju F dari A

maka jawabannya adalah

A-C-D-E-F dengan cost terkecil yaitu 5.