PERBEDAAN AGORITMA PRIM DENGAN KRUSKAL

PERBEDAAN AGORITMA PRIM DENGAN KRUSKAL : 

1.      Materi Prim

Algoritma prim ditemukan oleh Vojtech Jarnik pada tahun 1957 ,Prim merupakan jenis logika yang digunakan untuk menyelesaikan suatu masalah dengan jalan yang sistematis dan terstruktur, mulai dari mengidentifikasi masalah, membuat jalan untuk menyelesaikan masalah sampai membuat tindakan tentang jalan penyelesaian masalah yang akan diselesaikan. Algoritma ini bekerja dalam teori graf untuk mencari pohon rentang minimum dari sebuah graf berbobot yang saling terhubung. Dalam hal ini menunjukan bahwa sebuah himpunan bagian dari edge yang membentuk suatu pohon yang menggandung node didalamnya, dimana bobot keseluruhan tersebut tidak terhubung antara satu dengan yang lain, maka graf tersebut hanya memiliki satu pohon yang memiliki nilai minimum pada komponen yang saling terhubung.

Langkah langkah dalam membuat algoritma tersebut yaitu :

1.      Kita terlebih dahulu harus membuat pohon atau tree yang terdiri dari 1 node.

2.      Kemudian membuat sebuah himpunan yang berisikan setiap cabang pada graf.

3.      Lakukan perulangan pada setiap cabang yang akan menghubungkan setiap node di pohon atau tree yang dibuat.

4.      Setelah itu hapus himpunan satu cabang yang memiliki bobot terkecil yang menghubungkan 1 node di dalam jangkauan pohon atau tree yang dibuat kemudian hubungkan node tersebut dengan node yang berada diluar dari pohon atau tree yang dibuat.

2.      Materi Kruskal

Kruskal merupakan algoritma untuk mencari nilai minimum dengan bentuk spanning tree. Algoritma ini pertama kali ditemukan oleh Joseph Kruskal pada tahun 1915.Algoritma kruskal berdasar pada analogi growing yaitu analogi yang membentuk pohon merentang minimum T dari G dengan cara mengambil satu persatu sisi dari himpunun titik G dan memasukan kedalam pohon yang telah terbentuk sebelumnya.Penulisan algoritma Kruskal sebagai berikut :

1.      Posisi titik T masih kosong.

2.      Memilih sisi (i,j) menggunakan bobot nilai terbesar.

3.      pilih sisi (i,j) dengan bobot nilai terbesar berikutnya yang tidak membentuk cycle di T, kemudian tambahkan (i,j) ke T.

4.      Ulangi proses ke 3 sampai sampai berapa kali banyak nya data

5.      Langkah terakhir yaitu membuat total nilai banyak nya data.

Setiap cara dalam proses penyelesaian masalah pasti memiliki kekurangan dan kelebihan dalam metode yang digunakan, dalam metode algoritma kruskal juga terdapat kelebihal dan kekurangan dalam metode nya. Kelebihan dan kekurangan nya yaitu:

1.      Kelebihan

Algoritma kruskal sangatlah cocok digunakan pada metode graf yang setiap sisinya memiliki jumlah yang sedikit namun memiliki banyak simpul didalamnya. Karena orientasi kerja algoritma ini bekerja berdasarkan pada urutan bobot sisi, dan tidak bekerja berdasarkan simpul yang digunakan.

2.      Kekurangan

Kekurangan dalam menggunakan metode ini yaitu digunakan saat graf lengkap atau yang mendekati lengkap, dimana setiap simpul ataupun setiap titik terhubung dengan simpul simpul yang lainnya. Dalam hal ini algoritma kruskan menitikberatkan pada pencarian sisi, dimana sisi-sisi tersebut harus diurutkan , sehingga proses pengurutan sisi-sisi tersebut memakan waktu yang terlalu lama.