My first Magazine pemrograman-kompetitif-dasar | Page 139

11.2 Minimum Spanning Tree
3
3
2
2
5
1
5
4
1
4
(a)
3
(b)
3
2
2
5
1
5
4
1
4
(c)
(d)
Gambar 11.10: Diberikan suatu graf seperti pada gambar (a). Gambar (b) merupakan salah satu
spanning tree dari (a), namun (c) dan (d) bukanlah spanning tree dari (a).
Perhatikan contoh pada Gambar 11.10. Kita diberikan sebuah graf seperti pada gambar
(a). Untuk membentuk spanning tree , kita akan memilih beberapa edge dari graf asli sedemikian
sehingga edge yang diambil membentuk tree yang menghubungkan semua node . Gambar (b)
merupakan contoh spanning tree yang didapat dengan mengambil edge [h1, 4i, h2, 4i, h3, 4i, h4, 5i].
Sementara itu, gambar (c) bukanlah merupakan spanning tree dari (a) karena subgraf yang
dihasilkan tidak membentuk tree . Gambar (d) juga bukanlah spanning tree dari (a) karena ada
salah satu node yang tidak terhubung, yaitu node 1.
3
6
1
1
2
5
2
5
4
4
(a)
3
3
2
6
1
1
2
5
2
5
4
4
(b)
3
3
2
6
1
1
2
5
2
3
5
4
4
2
(c)
Gambar 11.11: Diberikan suatu graf berbobot seperti pada gambar (a). Gambar (b) merupakan
contoh MST dari (a), namun (b) bukanlah MST dari (a).
Minimum Spanning Tree (MST) adalah spanning tree pada graf berbobot yang mana total
bobot dari seluruh edge pada spanning tree tersebut minimum. Perhatikan ilustrasi pada Gambar
11.11. Misalkan diberikan graf berbobot seperti pada gambar (a). Gambar (b) dan (c) merupakan
spanning tree dari (a), namun total bobot dari spanning tree (b) merupakan yang minimum dari
seluruh kemungkinan spanning tree . Maka (b) adalah MST dari (a).
Kita akan mempelajari 2 algoritma untuk mencari MST pada suatu graf berbobot, yaitu
algoritma Prim dan algoritma Kruskal. Kedua algoritma ini bekerja dengan memanfaatkan konsep
greedy .
11.2.1
Prim
Cara kerja Prim serupa dengan cara kerja Dijkstra. Mula-mula, kita asumsikan seluruh node
tidak terhubung satu sama lain. Setelah itu, kita akan memilih sembarang node sebagai node
pertama pada tree yang akan kita bentuk. Kemudian, kita akan melakukan ekspansi pada tree
129