Algoritma Prim

Algoritma ini dimulai dari simpul yang berubah-ubah di setiap tingkatnya, diperbolehkan menambah cabang baru untuk membuat susunan pohon baru. Algoritma ini akan tertahan ketika simpul yang sedang dieksplorasi pada graf sudah sampai pada simpul yang dituju. Strategi yang digunakan adalah strategi Greedy dengan menganggap bahwa pada setiap langkah dari pohon merentangnya adalah augmented dan dipilih simpul yang nilainya paling kecil dari semua simpul yang ada.

Metode Greedy merupakan salah satu metode untuk merancang dan mendesain suatu algoritma. Metoda Greedy membangun suatu pohon merentang minimum dengan memeriksa garis demi garis untuk memilih garis dengan bobot kecil dan membuang garis dengan bobot besar, sehingga terbentuk suatu pohon merentang minimum. Metode ini digunakan untuk mendapatkan solusi yang optimal dari suatu permasalahan.

Beberapa peneliti yang menggunakan metode Greedy diantaranya adalah, yang pertama Borůvka tahun 1926, selanjutnya dengan metoda yang sama, penelitiannya ditinjau ulang oleh Choquet tahun 1938, Lukasziewicz, Florek, Perkal, Steinhaus dan Zubrzycki tahun 1951. Algoritma Borůvka dimulai dari n titik terasing dari graf (graf semula tanpa garis), kemudian dari masing-masing titik dipilih garis dengan bobot terkecil yang berhubungan dengan titik tersebut. Karena setiap garis mempunyai dua titik, maka dimungkinkan ada garis yang diperiksa dua kali.

Peneliti selanjutnya adalah Kruskal tahun 1956, yang menyusun garis-garis dalam urutan tidak menurun (non decreasing) dari bobotnya. Langkah awal adalah memilih garis dengan bobot terkecil diantara semua garis. Selanjutnya memilih garis dengan bobot terkecil berikutnya diantara sisa garis, dengan garis tersebut menghubungkan titik di dalam pohon bagian yang sudah dipilih dengan titik diluar pohon bagian.

Matematikawan Vojtěch Jarník tahun 1930 mengenalkan suatu metoda penentuan pohon merentang, yang selanjutnya diteliti kembali oleh Robert C. Prim tahun 1957 dan Dijkstra tahun 1959 sehingga menghasilkan suatu algoritma yang dikenal dengan nama algoritma Prim.

Algoritma Prim menitikberatkan pada pemilihan bobot minimum berdasarkan simpul yang diambil. Dan karena tidak perlu mengurutkan terlebih dahulu, algoritma Prim cocok untuk pohon dengan jumlah simpul banyak. Algoritma Prim akan selalu berhasil menemukan pohon merentang minimum tetapi pohon merentang yang dihasilkan tidak selalu unik.

Langkah-langkah dalam algoritma Prim adalah sebagai berikut:

·         Buat sebuah pohon yang terdiri dari satu simpul (node), dipilih secara acak dari graf.

·         Buat sebuah himpunan yang berisi semua cabang di graf.

·         Ulangi sampai semua cabang di dalam himpunan menghubungkan dua simpul di pohon

o    Hapus dari himpunan satu cabang dengan bobot terkecil yang menghubungkan satu simpul di pohon dengan satu simpul di luar pohon.

o    Hubungkan cabang tersebut ke pohon.

Algoritma Prim dalam pseudocode yaitu:

Procedure Prim(input G:graf, output T:pohon)

{    Membentuk pohon merentang minimum T dari graf terhubung G.

Masukan: graf-berbobot terhubung G = (V, E), yang mana |V| = n

Keluaran: pohon merentang minimum T = (V, E’)

}

Deklarasi

i, p, q, u, v : integer

Algoritma

Cari sisi (p,q) dari E yang berbobot terkecil

T ← {(p,q)}

for i ← 1 to n-1 do

Pilih sisi (u,v) dari E yang bobotnya terkecil namun bersisian dengan suatu simpul didalam T

T ← T U {(u,v)}

Endfor

 Keterangan :

G       =   graf.

T       =   pohon.

V       =   himpunan simpul-simpul.

E       =   himpunan sisi-sisi yang menghubungkan simpul di graf.

E’      =   himpunan sisi-sisi yang menghubungkan simpul-simpul yang ada di pohon.

(p,q)  =   pasangan simpul-simpul yang ada di graf yang membentuk sisi.

(u,v)  =    pasangan simpul-simpul yang ada di pohon yang membentuk sisi dengan bobot terkecil.

DAFTAR PUSTAKA / REFERENSI

Gloor, P. A., Johnson, D. B., Makedon, F., Metaxas, P., (1993), A Visualization System for Correctness Proofs of Graph Algorithms, http://www.wellesley.edu/CS/pmetaxas/visual_proofs.pdf, Computer Science Education, [19 Maret 2010].

Greenberg, H. J., (1998), Greedy Algorithm for Minimum Spanning Tree, http://glossary.computing.society.informs.org/notes/spanningtree.pdf, University of Colorado, Denver, [19 Maret 2010].

Kristanto, A., (2008), Perancangan Sistem Informasi dan Aplikasinya, Gava Media, Yogyakarta.

Mehta, D. P., Sahni, S., (2005), Handbook of Data Structures and Applications, Chapman & Hall/CRC Computer and Information Science Series, United States of America.

Munir, R., (2009), Matematika Diskrit, Edisi 3, Informatika, Bandung.

Oetomo, B. S., (2002), Perencanaan dan Pembangunan Sistem Informasi, Andi, Yogyakarta.

Purbasari, I. Y., (2007), Desain Dan Analisis Algoritma, Edisi 1, Graha Ilmu, Yogyakarta.

Purwanto, E. B., (2008), Perancangan Dan Analisis Algoritma, Edisi 1, Graha Ilmu, Yogyakarta.

Zakaria, T. M., Prijono, A., (2006), Konsep Dan Implementasi Struktur Data, Informatika, Bandung.