Wikipedia

Algoritma Prim: Perbedaan antara revisi

Jelajahi riwayat secara interaktif
← Revisi sebelumnya
Konten dihapus Konten ditambahkan
VisualTeks wiki
YonaBot (bicara | kontrib)
3.226 suntingan
Hadithfajri (bicara | kontrib)
952 suntingan
Tidak ada ringkasan suntingan
 
(23 revisi perantara oleh 18 pengguna tidak ditampilkan)
Baris 1:
'''AlgoritmaAlgoritme Prim''' adalah sebuah algoritmaalgoritme dalam [[graphteori theory]]graf untuk mencari [[pohon rentang minimum]] untuk sebuah graf berbobot yang saling terhubung. berbobot, denganIni kataberarti lainbahwa sebuah himpunan bagian dari cabang-cabangedge yang membentuk suatu pohon yang terdiri dari semuamengandung node, di mana bobot keseluruhan dari semua cabangedge dalam pohon adalah paling kecildiminimalisasikan. 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'''.
 
Langkah-langkahnya adalah sebagai berikut:
Baris 8:
** hubungkan cabang tersebut ke pohon
 
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'').
 
== Contoh ==
{| border=1 cellspacing=0 cellpadding=5
|[[ImageBerkas:Prim Algorithm 0Prim_Algorithm_0.svg|200px]]
|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.
|-
|[[ImageBerkas:Prim Algorithm 1.svg|200px]]
|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'''.
|-
|[[ImageBerkas:Prim Algorithm 2.svg|200px]]
|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'''.
|-
|[[ImageBerkas:Prim Algorithm 3.svg|200px]]
|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.
|-
|[[ImageBerkas:Prim Algorithm 4.svg|200px]]
|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.
|-
|[[ImageBerkas:Prim Algorithm 5.svg|200px]]
|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.
|-
|[[ImageBerkas:Prim Algorithm 6.svg|200px]]
|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.
|}
 
== Bukti ==
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<sub>1</sub>'' adalah pohon rentang minimum dari P. Bila ''Y<sub>1</sub>''=''Y'' maka ''Y'' adalah pohon rentang minimum. Kalau tidak, misalkan ''e'' cabang pertama yang ditambahkan dalam konstruksi ''Y'' yang tidak berada di ''Y<sub>1</sub>'', 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<sub>1</sub>'' adalah pohon rentang dari ''P'', ada jalur dalam ''Y<sub>1</sub>'' 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'').
Baris 41:
Misalkan ''Y<sub>2</sub>'' adalah graf yang diperoleh dengan menghapus ''f'' dan menambahkan ''e'' dari ''Y<sub>1</sub>''. Dapat ditunjukkan bahwa ''Y<sub>2</sub>'' terhubung, memiliki jumlah cabang yang sama dengan ''Y<sub>1</sub>'', dan bobotnya tidak lebih besar daripada ''Y<sub>1</sub>'', 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.
 
AlgoritmaAlgoritme-algoritmaalgoritme lain untuk masalah ini adalah [[AlgoritmaAlgoritme Kruskal]] dan [[AlgoritmaAlgoritme Borůvka]].
 
== Rujukan ==
* 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 02620329370-262-03293-7. Section 23.2: The algorithms of Kruskal and Prim, pp.567&ndashnbsp;574567–574.
 
== Pranala luar ==
{{commons|Category:Prim's Algorithm|Prim's Algorithm}}
* [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.cut-the-knot.org/Curriculum/Games/Mazes.shtml Create and Solve Mazes by Kruskal's and Prim's algorithms] at [[cut-the-knot]]
* [http://students.ceid.upatras.gr/~papagel/project/prim.htm Animated example of Prim's algorithm]
* [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 }}
* [http://www.algorithm-code.com/wiki/Prim%27s_algorithm Prim's algorithm code]
 
{{Authority control}}
[[kategori:matematika]]
[[Kategori:Teori graf]]
 
[[de:Algorithmus von Prim]]
[[en:Prim's algorithm]]
[[es:Algoritmo de Prim]]
[[fr:Algorithme de Prim]]
[[he:האלגוריתם של פרים]]
[[it:Algoritmo di Prim]]
[[ko:프림 알고리즘]]
[[nl:Algoritme van Prim]]
[[no:Prims algoritme]]
[[pl:Algorytm Prima]]
[[pt:Algoritmo de Prim]]
[[ru:Алгоритм Прима]]
[[sl:Primov algoritem]]
[[sr:Примов алгоритам]]
[[sv:Prims algoritm]]
[[tr:Prim algoritması]]
[[zh:Prim演算法]]
Diperoleh dari "https://wiki-indonesia.club/wiki/Algoritma_Prim"