Algoritma Prim

Dari Wikipedia Indonesia, ensiklopedia bebas berbahasa Indonesia.

Algoritma Prim adalah sebuah algoritma dalam graph theory untuk mencari pohon rentang minimum untuk sebuah graf terhubung berbobot, dengan kata lain sebuah himpunan bagian dari cabang-cabang yang membentuk suatu pohon yang terdiri dari semua node, di mana bobot keseluruhan semua cabang dalam pohon adalah paling kecil. Bila graf tersebut tidak terhubung, maka graf itu hanya memiliki satu pohon rentang minimum untuk satu dari komponen yang terhubung. Algoritma ini ditemukan pada 1930 oleh matematikawan Vojtěch Jarník dan kemudian secara terpisah oleh computer scientist Robert C. Prim pada 1957 dan ditemukan kembali oleh Dijkstra pada 1959. Karena itu algoritma ini sering dinamai algoritma DJP atau algoritma Jarnik.

Langkah-langkahnya adalah sebagai berikut:

buat sebuah pohon yang terdiri dari satu node, dipilih secara acak dari graf
buat sebuah himpunan yang berisi semua cabang di graf
loop sampai semua cabang di dalam himpunan menghubungkan dua node di pohon
- hapus dari himpunan satu cabang dengan bobot terkecil yang menghubungkan satu node di pohon dengan satu node di luar pohon
- hubungkan cabang tersebut ke pohon

Dengan struktur data binary heap sederhana, algoritma Prim dapat ditunjukkan berjalan dalam waktu O(Elog V), di mana E adalah jumlah cabang dan V adalah jumlah node. Dengan Fibonacci heap, hal ini dapat ditekan menjadi O(E + Vlog V), yang jauh lebih cepat bila grafnya cukup padat sehingga E adalah $Ω$ (Vlog V).

[sunting] Contoh

	Ini adalah graf berbobot awal. Graf ini bukan pohon karena ada circuit. Nama yang lebih tepat untuk diagram ini adalah graf atau jaringan. Angka-angka dekat garis penghubung adalah bobotnya. Belum ada garis yang ditandai, dan node D dipilih secara sembarang sebagai titik awal.
	Node kedua yang dipilih adalah yang terdekat ke D: A jauhnya 5, B 9, E 15, dan F 6. Dari keempatnya, 5 adalah yang terkecil, jadi kita tandai node A dan cabang DA.
	Node berikutnya yang dipilih adalah yang terdekat dari D atau A. B jauhnya 9 dari D dan 7 dari A, E jauhnya 15, dan F 6. 6 adalah yang terkecil, jadi kita tandai node F dan cabang DF.
	Algoritma ini berlanjut seperti di atas. Node B, yang jauhnya 7 dari A, ditandai. Di sini, cabang DB ditandai merah, karena baik node B dan node D telah ditandai hijau, sehingga DB tidak dapat digunakan.
	Dalam hal ini, kita dapat memilih antara C, E, dan G. C jauhnya 8 dari B, E 7 dari B, dan G 11 dari F. E yang terdekat, jadi kita tandai node E dan cabang EB. Dua cabang lain ditandai merah, karena kedua node yang terhubung telah digunakan.
	Di sini, node yang tersedia adalah C dan G. C jauhnya 5 dari E, dan G 9 dari E. C dipilih, jadi ditandai bersama dengan cabang EC. Cabang BC juga ditandai merah.
	Node G adalah satu-satunya yang tersisa. Jauhnya 11 dari F, dan 9 dari E. E lebih dekat, jadi kita tandai cabang EG. Sekarang semua node telah terhubung, dan pohon rentang minimum ditunjukkan dengan warna hijau, bobotnya 39.

[sunting] Bukti

Misalkan P adalah sebuah graf terhubung berbobot. Pada setiap iterasi algoritma Prim, suatu cabang harus ditemukan yang menghubungkan sebuah node di graf bagian ke sebuah node di luar graf bagian. Karena P terhubung, maka selalu ada jalur ke setiap node. Keluaran Y dari algoritma Prim adalah sebuah pohon, karena semua cabang dan node yang ditambahkan pada Y terhubung. Misalkan Y₁ adalah pohon rentang minimum dari P. Bila Y₁=Y maka Y adalah pohon rentang minimum. Kalau tidak, misalkan e cabang pertama yang ditambahkan dalam konstruksi Y yang tidak berada di Y₁, dan V himpunan semua node yang terhubung oleh cabang-cabang yang ditambahkan sebelum e. Maka salah satu ujung dari e ada di dalam V dan ujung yang lain tidak. Karena Y₁ adalah pohon rentang dari P, ada jalur dalam Y₁ yang menghubungkan kedua ujung itu. Bila jalur ini ditelusuri, kita akan menemukan sebuah cabang f yang menghubungkan sebuah node di V ke satu node yang tidak di V. Pada iterasi ketika e ditambahkan ke Y, f dapat juga ditambahkan dan akan ditambahkan alih-alih e bila bobotnya lebih kecil daripada e. Karena f tidak ditambahkan, maka kesimpulannya

w(f) ≥ w(e).

Misalkan Y₂ adalah graf yang diperoleh dengan menghapus f dan menambahkan e dari Y₁. Dapat ditunjukkan bahwa Y₂ terhubung, memiliki jumlah cabang yang sama dengan Y₁, dan bobotnya tidak lebih besar daripada Y₁, karena itu ia adalah pohon rentang minimum dari P dan ia mengandung e dan semua cabang-cabang yang ditambahkan sebelumnya selama konstruksi V. Ulangi langkah-langkah di atas dan kita akan mendapatkan sebuah pohon rentang minimum dari P yang identis dengan Y. Hal ini menunjukkan bahwa Y adalah pohon rentang minimum.

Algoritma-algoritma lain untuk masalah ini adalah Algoritma Kruskal dan Algoritma Borůvka.

[sunting] Rujukan

R. C. Prim: Shortest connection networks and some generalisations. In: Bell System Technical Journal, 36 (1957), pp. 1389–1401
D. Cherition and R. E. Tarjan: Finding minimum spanning trees. In: SIAM Journal of Computing, 5 (Dec. 1976), pp. 724–741
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 23.2: The algorithms of Kruskal and Prim, pp.567–574.