Minimum Spanning Tree

13 Aug 2020 | Siti Muslimah Kusuma Haqqu N.

Minimum Spanning Tree

 

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 :

  1. Setiap pasang nodes dalam G terhubung dengan path tunggal
  2. G terhubung, tidak memiliki sirkuit, dan mempunyai n-1 edges
  3. G tidak memiliki sirkuit, penambahan 1 edge dapat membentuk 1 sirkuit
  4. 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.

Gambar 3. Minimum spanning tree berbobot 20

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.

  1. 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:

  1. https://www.spoj.com/problems/MST/
  2. https://www.spoj.com/problems/CSTREET/
  3. https://www.spoj.com/problems/ULM09/

Sumber :

  1. Bahan kuliah IF2091 Struktur Diskrit Program Studi Teknik Informatika ITB oleh Rinaldi
  2. org
  3. Laaksonen, Antti. (2017) Undergraduate Topics in Computer Science: Guide to Competitive Programming. Helsinki: Springer