Graph tak berarah (undirected graph)
Graph yang sisinya tidak mempunyai orientasi arah disebut graph tak berarah. Pada graph tak-berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan. salah satu contoh graph tak berarah dimana sisi-sisi yang menghubungkan antar simpul dalam graph tersebut tidak memiliki orientasi arah
.
Graph Berarah (directed graph)
Graph yang setiap sisinya memiliki orientasi arah disebut sebagai graph berarah. Sisi berarah dalam graph ini dapat dinamakan sebagai busur Lain halnya dengan graph tak-berarah, urutan pasangan simpul disini sangat diperhatikan karena dapat menyatakan hal yang berbeda. contoh dari graph berarah yang memiliki sisi-sisi dengan orientasi arah (busur).
Minimum Spanning Tree
minimum spanning tree adalah tree yang terkoneksi, undirected graph. mereka terhubung dengan semua vertices bersama dengan total weight yang minimum oleh semua edge.
Ada 3 cara mencari Minimum Spanning Tree (MST)
Algoritma Prim
Pada algoritma prim, dimulai pada vertex yang mempunyai sisi (edge) dengan bobot terkecil.
Sisi yang dimasukkan ke dalam himpunan T adalah sisi graph G yang bersisian dengan sebuah simpul di T, sedemikian sehingga T adalah Tree (pohon). Sisi dari Graph G ditambahkan ke T jika ia tidak membentuk cycle.
Algoritma Kruskal
Pada algoritma kruskal, sisi (edge) dari Graph diurut terlebih dahulu berdasarkan bobotnya dari kecil ke besar.
Sisi yang dimasukkan ke dalam himpunan T adalah sisi graph G yang sedemikian sehingga T adalah Tree (pohon). Sisi dari Graph G ditambahkan ke T jika ia tidak membentuk cycle.
- T masih kosong
- pilih sisi (i,j) dengan bobot minimum
- pilih sisi (i,j) dengan bobot minimum berikutnya yang tidak membentuk cycle di T, tambahkan (i,j) ke T
- Ulangi langkah 3 sebanyak (n-2) kali.
- Total langkah (n-1) kali
Algoritma Dijkstra
(dinamai menurut penemunya, seorang ilmuwan komputer, Edsger Dijkstra), adalah sebuah algoritma rakus (greedy algorithm) yang dipakai dalam memecahkan permasalahan jarak terpendek (shortest path problem) untuk sebuah graf berarah (directed graph) dengan bobot-bobot sisi (edge weights) yang bernilai tak-negatif.
Misalnya, bila vertices dari sebuah graf melambangkan kota-kota dan bobot sisi (edge weights) melambangkan jarak antara kota-kota tersebut, maka algoritma Dijkstra dapat digunakan untuk menemukan jarak terpendek antara dua kota.
Input algoritma ini adalah sebuah graf berarah yang berbobot (weighted directed graph) G dan sebuah sumber vertex s dalam G dan Vadalah himpunan semua vertices dalam graph G.
Setiap sisi dari graf ini adalah pasangan vertices (u,v) yang melambangkan hubungan dari vertex u ke vertex v. Himpunan semua tepi disebut E.
