32
2.5
Jaringan
2.5.1
Minimal Spanning Tree
Menurut
Taha
(2003,
p215),
minimal
spanning
tree
digunakan untuk
menghubungkan node
–
node
dalam
jaringan
secara
langsung
maupun
tidak
langsung
sehingga
menghasilkan panjang
terpendek
untuk
semua
cabangnya.
Algoritma
ini
biasanya
digunakan
dalam
konstruksi jalan
yang
menghubungkan
beberapa kota.
Langkah yang digunakan adalah sebagai berikut:
Step 0. Set C
0
=
?
dan c
0
=
N.
Step 1. Mulai dengan semua node,
i, dalam c
0
yang tidak terhubung dan jadikan
C1 = {i}, dimana c1 = N – {i}. Jadikan k = 2.
Step k.
Pilih sebuah
node, j*, dalam
himpunan c
k-1
yang
tidak
terhubung
memiliki
jarak
terpendek
pada
himpunan
C
k-1
dan
hapus
node
tersebut
dari C
k-1
.
Sehingga :
C
k
=
C
k-1
+ {j*}, c
k
=
c
k-1
–
{j*}
Jika
himpunan
node
yang
tidak
terhubung pada
c
k
kosong,
selesai.
Jika
tidak, jadikan k = k + 1 dan ulangi langkah tersebut.
Berikut
adalah
contoh
persoalan
dalam
permasalahan minimal
spanning
tree. Gambar di bawah ini menunjukkan
hubungan kabel dalam suatu
perusahaan.
 |