Algoritma Prim: Perbedaan antara revisi

'''AlgoritmaAlgoritme Prim''' adalah sebuah algoritmaalgoritme dalam teori graf untuk mencari pohon rentang minimum untuk sebuah graf berbobot yang saling terhubung. Ini berarti bahwa sebuah himpunan bagian dari edge yang membentuk suatu pohon yang mengandung node, di mana bobot keseluruhan dari semua edge dalam pohon diminimalisasikan. Bila graf tersebut tidak terhubung, maka graf itu hanya memiliki satu pohon rentang minimum untuk satu dari komponen yang terhubung. AlgoritmaAlgoritme 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 [[Edsger Dijkstra|Dijkstra]] pada [[1959]]. Karena itu algoritmaalgoritme ini sering dinamai '''algoritmaalgoritme DJP''' atau '''algoritmaalgoritme Jarnik'''.

Dengan struktur data [[binary heap]] sederhana, algoritmaalgoritme Prim dapat ditunjukkan berjalan dalam waktu [[Big-O notation|O]](''E''log ''V''), di mana E adalah jumlah cabang dan V adalah jumlah node. Dengan [[Fibonacci heap]], hal ini dapat ditekan menjadi O(''E'' + ''V''log ''V''), yang jauh lebih cepat bila grafnya cukup padat sehingga ''E'' adalah <math>\Omega</math>(''V''log ''V'').

|AlgoritmaAlgoritme 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.

Misalkan ''P'' adalah sebuah graf terhubung berbobot. Pada setiap iterasi algoritmaalgoritme 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 algoritmaalgoritme 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

AlgoritmaAlgoritme-algoritmaalgoritme lain untuk masalah ini adalah [[AlgoritmaAlgoritme Kruskal]] dan [[AlgoritmaAlgoritme Borůvka]].

* R. C. Prim: ''Shortest connection networks and some generalisations''. In: ''Bell System Technical Journal'', 36 (1957), pp. &nbsp;1389–1401

* D. Cherition and [[Robert Tarjan|R. E. Tarjan]]: ''Finding minimum spanning trees''. In: ''SIAM Journal of Computing'', 5 (Dec. 1976), pp. &nbsp;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 0-262-03293-7. Section 23.2: The algorithms of Kruskal and Prim, pp.&nbsp;567–574.

* [http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Prim.shtml Minimum Spanning Tree Problem: Prim's Algorithm] {{Webarchive|url=https://web.archive.org/web/20070505070612/http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Prim.shtml |date=2007-05-05 }}

* [http://www.mincel.com/java/prim.html Prim's Algorithm (Java Applet)] {{Webarchive|url=https://web.archive.org/web/20060712152157/http://www.mincel.com/java/prim.html |date=2006-07-12 }}

[[Kategori:MatematikaTeori graf]]