GRAF DAN POHON

      Dalam pembuatan graf atau pohon dapat menggunakan algoritma dijkstra atau kruskal. Kedua algoritma ini dapat digunakan untuk pembuatan graf pada kasus yang ada di lingkungan sekitar, biasanya algoritma ini digunakan untuk mengukur jarak antar tempat yang menghasilkan suatu graf atau pun pohon.
      Algoritma dijkstra (pencarian jalur terpendek), merupakan suatu algoritma yang disebut sebagai single-source shortest path yang digunakan dalam menentukan jalur terpendek dari simpul sumber menuju simpul tujuan berdasarkan bobot pada sisi. Bobot pada sisi dapat berupa jarak, waktu, biaya, ataupun bobot yang lainnya. Algoritma dijkstra bekerja dengan cara mengujungi semua simpul-simpul yang terdapat pada graf, dimulai pada simpul sumber. Secara berulang, algoritma ini akan memilih simpul-simpul terdekat dan menghitung total bobot semua sisi yang dilewati untuk mencapai simpul tujuan.
      Algoritma ini bertujuan untuk menemukan jalur terpendek berdasarkan bobot terkecil dari satu titik ke titik lainnya. Misalkan titik mengambarkan gedung dan garis menggambarkan jalan, maka algoritma Dijkstra melakukan penghitungan terhadap semua kemungkinan-kemungkinan adanya bobot terkecil dari setiap titik.
      Sedangkan algoritma kruskal adalah sebuah algoritma dalam teori graf yang mencari sebuah minimum spanning tree untuk sebuah graf berbobot yang terhubung. Ini berarti, jika grafik tidak terhubung, maka harus menemukan hutan rentang minimum atau pohon rentang minimum untuk setiap komponen yang terhubung di dalam graf terhubung. Algoritma Kruskal juga tergolong algoritma Greedy dalam teori graf yang digunakan untuk mencari minimum spanning tree. Algoritma ini pertama kali muncul pada tahun 1956 dalam sebuah tulisan yang ditulis oleh Joseph Kruskal. Algoritma Kruskal adalah contoh dari algoritma rakus . Algoritma ini pertama kali muncul dalam Prosiding American Mathematical Society , hal 1956.
      Dasar pembentukan algoritma Kruskal berasal dari analogi growing forest. Growing forest maksudnya adalah untuk membentuk pohon merentang minimum T dari graf G adalah dengan cara mengambil satu per satu sisi dari graf G dan memasukkannya ke dalam pohon yang telah terbentuk sebelumnya. Seiring dengan berjalannya jalur graf ke setiap sisi, maka forest akan memiliki pohon yang semakin sedikit. Analogi ini disebut dengan growing forest. Algoritma Kruskal akan terus menambahkan sisi-sisi ke dalam hutan yang sesuai, hingga akhirnya tidak ada lagi forest, melainkan hanya sebuah pohon merentang minimum.
      Graph adalah kumpulan dua himpunan, yaitu himpunan titik ( vertex, simpul atau node ) dan kumpulan dari garis ( edge ). Sedangkan pohon merupakan graph tak berarah yang terhubung dan tidak mengandung sirkuit. Sirkuit sendiri ialah simpul awal sama dengan simpul akhir.
- Kelebihan Algoritma Kruskal
      Kelebihan algoritma Kruskal dibanding algoritma prim adalah sebagai berikut :
Sangat cocok diterapkan saat graf memiliki sisi berjumlah sedikit namun memiliki sangat banyak simpul, karena orientasi kerja algoritma ini adalah berdasarkan pada urutan bobot sisi, tidak berdasarkan simpul.

Contoh pemecahan permasalahan

- Pencarian rumah makan dengan algoritma djikstra dan algoritma kruskal.
1. Peta tata letak antar rumah makan.

2. Graf rumah makan

Keterangan :

A : Warung Nasi Goreng Hj. Udin

B : Rumah Makan Padang Lubuak

C : Rumah Makan Masakan Banjar Mama Aswan

D : Rumah Makan Bubur Ayam Pak Suhendar

E : Nasi Kuning Jasmine

F : Warung Makan Nasi Rames Mesra Malang

G : Depot Mega

H : Warung Makan Umi

I : Rumah Makan Padang Telaga

J : Rumah Makan Bulan

3. Tabel matriks dari graf rumah makan

      Kesimpulan dari materi ini adalah algoritma dijkstra (pencarian jalur terpendek), merupakan suatu algoritma yang disebut juga sebagai single-source shortest path yang digunakan dalam menentukan jalur terpendek dari simpul sumber menuju simpul tujuan berdasarkan bobot pada sisi. Algoritma dijkstra bekerja dengan cara mengujungi semua semua simpul-simpul yang terdapat pada graf yang dimulai pada simpul sumber.

      Algoritma kruskal adalah sebuah algoritma dalam teori graf yang mencari sebuah minimum spanning tree untuk sebuah graf berbobot yang terhubung. Dasar pembentukan algoritma Kruskal berasal dari analogi growing forest. Graph adalah kumpulan dua himpunan, yaitu himpunan titik ( vertex/simpul/node ) dan kumpulan dari garis ( edge ). Tree merupakan graph tak berarah yang terhubung dan tidak mengandung sirkuit. Sirkuit sendiri ialah simpul awal = simpul akhir.

Referensi :

Laporan algoritma dan pemrograman 2 kelompok 4