Mungkin beberapa dari kalian masih ada yang duduk di bangku kuliah, masih ingatkah kalian dengan materi Minimum Spanning Tree? Sebenarnya apa sih Minimum Spanning Tree itu? Namun, sebelum mengetahui Minimum Spanning Tree, kita perlu mengetahui definisi dari graf, tree, dan spanning tree terlebih dahulu.
1. Definisi Graf
Graf adalah himpunan yang terdiri dari nodes dan edges. Graf G = (N, E), di mana N merupakan himpunan tidak kosong dari nodes dan E merupakan himpunan edges yang menghubungkan sepasang nodes.
2. Definisi Tree
Tree adalah graf terhubung yang tidak memiliki arah dan tidak mengandung sirkuit. Tree adalah graf tanpa arah G dan memiliki n nodes yang harus memenuhi :
Setiap pasang nodes dalam G terhubung dengan path tunggal
G terhubung, tidak memiliki sirkuit, dan mempunyai n-1 edges
G tidak memiliki sirkuit, penambahan 1 edge dapat membentuk 1 sirkuit
G terhubung, akan menjadi tidak terhubung jika salah satu edges dihilangkan
3. Definisi spanning tree
Spanning tree terdiri dari semua nodes dalam graf dan beberapa edges sehingga semua nodes saling terhubung. Spanning Tree merupakan graf tehubung yang diperoleh dari meutus sirkuit dalam graf. Bobot spanning tree adalah jumlahan dari bobot edges.
Gambar 1. Graf
Gambar 2. Spanning Tree berbobot 22
Dengan demikian, Minimum Spanning Tree adalah graf terhubung yang diperoleh dari memutus sirkuit dalam graf, tidak memiliki arah, dan memiliki bobot paling minimal.
Ada beberapa algoritma untuk memperoleh Minimum Spanning Tree, yaitu :
1. Prim’s
Langkah-langkah :
Ambil edge (T) dengan bobot terkecil pada tree.
Ambil edge yang bersisian dengan node di T dengan bobot minimum yang menambah node baru (tidak membentuk sirkuit) pada Tree.
Ulangi langkah 2 sebanyak n-2 kali.
2. Kruskal
Langkah-langkah :
Graf pada awalnya hanya terdiri dari nodes saja.
Tambahkan edges berdasarkan bobot yang paling kecil dan edges yang ditambahkan tidak membentuk sirkuit.
Ulangi langkah 2 sebanyak n-1 kali.
Mempelajari algoritma tentu tidak lengkap tanpa adanya latihan, berikut beberapa latihan yang dapat digunakan untuk mengimplementasikannya:
Sumber :
Bahan kuliah IF2091 Struktur Diskrit Program Studi Teknik Informatika ITB oleh Rinaldi
Laaksonen, Antti. (2017). Undergraduate Topics in Computer Science: Guide to Competitive Programming. Helsinki: Springer
