Hidup Untuk Berbagi

Algoritma Kruskal and Algoritma Prim. 

Kedua algoritma ini berbeda dalam metodologinya, tetapi keduanya mempunyai tujuan menemukan minimum spanning

algorithm Kruskal menggunakan edge, dan algorithm Prim menggunakan vertex yang terhubung.

Perbedaan prinsip antara algoritma prim dan kruskal adalah,

jika pada algoritma prim sisi yang dimasukkan ke dalam T harus bersisian dengan sebuah simpul di T, maka pada algoritma kruskal sisi yang dipilih tidak perlu bersisian dengan sebuah simpul di T. asalkan penambahan sisi tersebut tidak membentuk cycle.
Pada algoritma kruskal, sisi (edge) dari Graph diurut terlebih dahulu berdasarkan bobotnya dari kecil ke besar.

Sisi yang dimasukkan ke dalam himpunan T adalah sisi graph G yang sedemikian sehingga T adalah Tree (pohon). Sisi dari Graph G ditambahkan ke T jika ia tidak membentuk cycle.

T masih kosong
pilih sisi (i,j) dengan bobot minimum
pilih sisi (i,j) dengan bobot minimum berikutnya yang tidak membentuk cycle di T, tambahkan (i,j) ke T
Ulangi langkah 3 sebanyak (n-2) kali.
Total langkah (n-1) kali

One response

  1. nelma

    tx wt infox.. tapi kalau bsa ditambahkan dengan contoh donk…

    26 Mei 2013 pukul 2:27 pm

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s