Algoritma Menentukan Minimum Spanning Tree (MST)

H. Algoritma Menentukan Minimum Spanning Tree (MST)

Dua algoritma populer untuk menentukan minimum spanning tree (MST) adalah Kruskal Algorithm dan Prim’s Algorithm.

1. Algoritma Kruskal

Algoritma ini lebih sederhana jika dilihat dari konsepnya namun lebih sulit dalam implementasinya. Idenya adalah mendapatkan satu demi satu sisi mulai dari yang berbobot terkecil untuk membentuk tree, suatu sisi walaupun berbobot kecil tidak akan diambil jika membentuk siklik dengan sisi yang sudah termasuk dalam tree. Yang menjadi masalah dalam implementasinya adalah keperluan adanya pemeriksaan kondisi siklik tersebut.Salah satu pemecahaannya adalah dengan subsetting yaitu pembentukan subset-subset yang disjoint dan secara bertahap dilakukan penggabungan atas tiap dua subset yang berhubungan dengan suatu sisi dengan bobot terpendek. Algoritma lengkapnya:

·         Tahap pertama, jika dalam V terdapat n verteks maka diinisialisasi n buah subset yang disjoint, masing-masing berisi satu verteks, sebagai subset-subset awal.

·         Tahap berikutnya, urutkan sisi-sisi dengan bobot yang terkecil hingga terbesar.

·         Mulai dari sisi dengan bobot terkecil hingga terbesar lakukan dalam iterasi: jika sisi tsb. menghubungkan dua vertex dalam satu subset (berarti membentuk siklik) maka skip sisi tersebut dan periksa sisi berikutnya jika tidak (berarti membentuk siklik) maka kedua subset dari verteks-verteks yang bersangkutan digabungkan menjadi satu subset yang lebih besar. Iterasi akan berlangsung hingga semua sisi terproses.

MST_KRUSKAL (G)

{ For setiap vertex v dalam V[G] Do

{ set S(v) ← {v} }

Inisialisasi priority queue Q yang berisi semua edge dari G,

gunakan bobot sebagai keys.

A ← { } // A berisi edge dari MST

While A lebih kecil dari pada n-1 edge Do

{ set S(v) berisi v dan S(u) berisi u }

IF S(v) != S(u) Then

{ Tambahkan edge (u, v) ke A

Merge S(v) dan S(u) menjadi satu set

}

Return A

}

2. Algoritma Prim

Algoritma dimulai dari suatu verteks awal tertentu dan bisa ditentukan oleh pemanggil atau dipilih sembarang oleh algoritma. Misalnya verteks awal tersebut adalah v. Pada setiap iterasi terdapat kondisi di mana himpunan vertex V terbagi dalam dua:

W yaitu himpunan verteks yang sudah dievaluasi sebagai node di dalam pohon, serta (V-W) yaitu himpunan verteks yang belum dievaluasi.

Di awal algoritma W diinisialisasi berisi verteks awal v. Selanjutnya, di dalam iterasinya:

Pada setiap adjacency dari tiap verteks dalam W dengan verteks dalam (V-W) dicari sisi dengan panjang minimal. setelah diperoleh, sisi tersebut ditandai sebagai sisi yang membentuk tree dan verteks adjacent sisi tersebut dalam (VW) dipindahkan ke W (menjadi anggota W).

Jika sisi tersebut tidak ada maka proses selesai.

Dari contoh di atas misalnya dilakukan pencarian mulai dari verteks A Maka algoritma ini menghasilkan tahapan-tahapan iterasi pencarian sbb.:

MST_PRIM (G, w, v)

{ Q ← V[G]

for setiap u dalam Q do key [u] ← ∞

key [r] ← 0

π[r] ← NIl

while queue tidak kosong do

{ u ← EXTRACT_MIN (Q)

for setiap vertex v dalam Adj[u] do

{ if v ada dalam Q dan w(u, v) < key [v] then

{ π[v] ← w(u, v)

key [v] ← w(u, v)

}

}

}