ALGORITMA MINIMUM SPANNING TREE

MINIMUM SPANNING TREE (MST)
By: Firqin Setara(409312419800)

Definition:
Let T be a spanning tree of mimimum total weight in a connected weighted graph G. Then T is minimumspanning tree or
a minimum connector in G. (Joan and Robin 2004:183)

Minimum Spanning Tree
• Graph bagian G( graph berbobot, terhubung, tidak berarah)
• Tidak berupa cycle
• Memuat semua titik
• Graph berbobot dengan bobot minimum

Contoh Penerapan
1. Pemodelan jaringan listrik dengan bobot (panjang kabel) minimum.
2. Pemodelan jaringan pipa PDAM(Perusahaan daerah air minum)
3. Pemodelan gardu sinyal (Tower) pada perusahaan telekomunikasi
4. Pemodelan pembangunan jalan raya, digunakan untuk memilih jalur
dengan bobot terkecil., untuk meminimalkan biaya pembangunan jalan.

Algoritma Spanning Tree:
1. Algoritma Boruvka (Otakar Borůvka 1926)
2. Algoritma Prim Vojtěch Jarník 1930)
3 Algoritma Kruskal (Joseph Kruskal 1956)
4. Algoritma Sollin
5. Algoritma Edge Ecchange
6. Algoritma TCRNN(Tree Construction with Reciprocal Nearest Neighbour)
7. Algoritma Bernard Chazel Baru Bernard Chazell
8. Algoritma Waktu Linear
9. Algoritma Reverse-Delete
10.Algoritma Semut (Marco Dorigo 1996)
11. Algoritma Genetika
12 Algoritma Parallel
13. Algoritma Penyimpanan Eksternal

1. Algoritma Boruvka
Algorima pertama untuk mencari pohon merentang minimum dari sutau graf
ditemukan oleh Otakar Borůvka pada tahun 1926. Untuk menentukan pohon merentang minimum dari sebuah graf dengan
menggunakan Algoritma Boruvka maka diperlukan langkah-langkah sebagai berikut:
Untuk mencari pohon merentang minimum pada graf G
Langkah-langkah Algoritma Boruvka:
Langkah 1: Salin titik dari G ke graf baru T yang kosong.
Langkah 2: Sedangkan L tidak terhubung (artinya hutan lebih dari satu pohon)
Langkah 3: Untuk setiap pohon di L, hubungkan sebuah titik ke titik yang lain pada pohon yang lain di L dengan
menambahkan sisi yang berbobot minimum
(Chartrand dan Ortrud, 1993:67).

2.Algoritma Prim
Algoritma Prim membentuk pohon merentang minimum langkah per langkah.
Pada setiap langkah diambil sisi dari graf G yang mempunyai bobot minimum
namun terhubung dengan pohon merentang minimum T yang telah terbentuk.
Langkah-langkah Algoritma Prim:
Langkah 1: Ambil sisi dari graf G yang berbobot minimum, masukkan ke dalam T
Langkah 2: Pilih sisi (u, v) yang mempunyai bobot minimum dan bersisian dengan simpul di T,
tetapi (u,v) tidak membentuk sirkuit di T. Tambahkan (u, v) ke dalamT.
Langkah 3: Ulangi langkah 2 sebanyak n - 2 kali hingga terbentuk pohon merentang minimum.

3.Algoritma Kruskal
Algoritma Kruskal adalah suatu Algoritma di dalam teori graf yang digunakan
untuk mengkonstruksi pohon merentang minimum di dalam graf berbobot terhubung
secara berurutan dari sisi yang berbobot kecil sampai berbobot besar hingga tidak
terbentuk sikel. Algoritma Kruskal dapat diasumsikan dengan memilih sisi dari Graf
secara berurutan berdasarkan bobotnya dari bobot kecil ke bobot besar.
Langkah-langkah Algoritma Kruskal: Langkah 1: Urutkan sisi-sisi graf dari kecil ke besar. T merupakan himpunan kosong.
Langkah 2: Pilih sisi e dengan bobot minimum yang tidak membentuk sirkuit di T,
tambahkan e ke dalam T
Langkah 3: Ulangi langkah 2 sebanyak n - 1 kali hingga terbentuk pohon merentang minimum.

4.Algoritma Sollin
Algoritma Sollin adalah suatu Algoritma di dalam teori graf yang digunakan untuk
menentukan pohon merentang minimum di dalam graf berbobot terhubung dengan cara
melakukan penghapusan sisi-sisi yang tidak menyebabkan graf menjadi tidak berhubung
atau membentuk sirkuit. Penghapusan tersebut dimulai dari sisi atau busur yang memiliki bobot terbesar hingga
terkecil.
Langkah-langkah Algoritma Sollin:
Langkah 1: Urutkan sisi-sisi pada graf berdasarkan bobotnya dari besar ke kecil
Langkah 2: Lakukan penghapusan setiap sisi yang tidak menyebabkan graf menjadi
tidak terhubung
Langkah 3 :Ulangi langkah 2 hingga diperoleh pohon merentang minimum.