MINIMAL SPANNING TREE

oleh : Dicky Rahardiantoro


Pohon rentang minimum (minimal spanning tree) adalah teknik mencari jalan penghubung yang dapat menghubungkan semua titik dalam jaringan secara bersamaan sampai diperoleh jarak minimum.

Masalah pohon rentang minimum serupa dengan masalah rute terpendek (shortest route), kecuali bahwa tujuannya adalah untuk menghubungkan seluruh simpul dalam jaringan sehingga total panjang cabang tersebut diminimisasi. Jaringan yang dihasilkan merentangkan (menghubungkan) semua titikdalam jaringan tersebut pada total jarak (panjang) minimum.

Langkah-langkah dari pohon rentang minimum adalah :

  1. pilih secara arbitrer sebuah node dalam jaringan
  2. hubungkan node tersebut dengan node terdekat yang dapat meminimalkan total jarak
  3. perhatikan semua node apakah terdapat node yang belum terhubung, temukan dan hubungkan node terdekat yang belum terhubung
  4. ulangi langkah ketiga sampai seluruh node dapat terhubung
Sebagai contoh, gedung Istec Corporation yang baru memiliki beberapa ruangan dan tiap ruangan membutuhkan 1 lubang aliran listrik (atau biasa disebut sebagai steker). Teknisi listrik akan menyalurkan listrik dari ruang bagian depan sampai keseluruh ruangan dengan total panjang kabel yang seefisien mungkin. Adapun jarak antar ruangan dapat digambarkan dalam gambar jaringan berikut ini, sedangkan ruang bagian depan digambarkan sebagai node-1.



Karena node-1 adalah ruangan terdepan yang menjadi sumber aliran listrik utama, maka node-1 akan dijadikan sebagai patokan dalam jaringan. Node yang paling dekat dengan node-1 adalah node dengan jarak 2 meter, sehingga kita hubungkan node 1 dengan node-3.


Kemudian kita lihat node-node terdekat yang belum terhubung dengan node 1 dan 3, yaitu node 7, 6 dan 2. Yang terdekat dengan node 3 adalah node 7 dengan jarak 3 meter. Kemudian node 3 dan node 7 dapat dihubungkan.


Node yang belum terhubung terdekat dengan node 1, 3 dan 7 adalah node 6 dengan panjang 2 meter.


Node yang belum terhubung dan dekat dengan node 1,3,7 dan 6 adalah 5 dan 2. Node 5 dapat terhubung dengan node 6 dengan jarak 3 meter, sedangkan node 3 dapat dihubungkan dengan node-1 dengan jarak 3 meter.


Sisa node yang belum terhubung adalah node 8, 4 dan 9. Node 4 dapat dihubungkan dengan node 5 dengan jarak 3 meter, dan untuk mencapai node 9 total jarak terdekat lebih pendek jika ditempuh dari node 8 ke 9 dari pada melalui node 4.



Karena seluruh node telah terhubung atau telah terkait dalam satu jaringan, maka solusi di atas telah optimum. Jadi teknisi listrik dapat memulai merentangkan kabelnya dengan menghubungkan node 1 – 2, 1 – 3, 3 – 7, 6 – 7, 5 – 6, 4 – 5, 6 – 8, 8 – 9

Panjang kabel yang dibutuhkan adalah : 21 meter





5 komentar:

kiki said...

salam sukses bisa nggak buat codingannya dalam C++

kiki said...

salam sukses tolong bisa nggak buat program dalam C++

Dicky Rahardi said...

Bahasan artikel saya masih dalam ruang lingkup untuk membangun pemahaman proses. Untuk programming dengan C++ (Visual C++) mungkin coding berikut bisa membantu http://ds4beginners.wordpress.com/2006/10/05/prims-algorithm-for-minimum-spanning-tree/

Jika ada yang kurang dari keterangan saya, mohon ditambahkan

Salam

Kit said...

bisa ga kalau MST dengan algoritma prim di buat coding vb ato di flash?

asdita rizki lubis said...

bisa buat menentukan minimum spanning tree menggunakan algoritma kruskal dalam bahasa c? buat program nya

Post a Comment

Tanggapan, pesan atau pertanyaan hendaknya disertai dengan identitas (minimal mengisi NAMA dgn men-select bagian Comment as dengan "Name/URL"). Terima kasih

(c) DickyRahardi.Com™, 2006