fbpx

Struktur Data : Spanning Tree

Spanning Tree adalah sebuah Tree yang dibuat dari sebuah Graph dengan menghilangkan beberapa edge-nya. Tree ini harus mengandung semua node yang dimiliki Graph. Pada prinsipnya adalah menghilangkan jalur edge yang membentuk jalur putaran dari 1 node kembali ke node semula.


Minimum Spanning Tree

Jika Weighted Graph diubah menjadi Spanning Tree, tiap kombinasi Tree yang dapat dibuat
memiliki total weight yang berbeda-beda. Problem Minimum Spanning Tree (MST) berusaha mencari Tree seperti apa yang bisa dibuat dari sebuah Weighted Graph dengan total weight seminimal mungkin.

Contoh Aplikasi:

  • Membangun rel kereta api yang bisa menghubungkan beberapa kota
  • Mendesain jaringan telekomunikasi (fiber-optic networks, computer networks, leased-line telephone networks, cable television networks, etc.)
  • Mendesain jaringan pipa untuk menghubungkan sejumlah lokasi

Minimum Spanning Tree dengan Algoritma Dijkstra

Algoritma ini dicetuskan oleh Edsger Dijkstra di tahun 1959.

Pada algoritma ini, kita akan menandai node yang memiliki lintasan terpendek/minimum, dengan syarat setiap node yang terhubung tidak boleh membentuk siklus/circle. Algoritma akan berhenti jika semua node telah terhubung/terkunjungi oleh lintasan.


Langkah – langkah

  1. Pilih node awal. Dari semua edge yang terhubung ke node awal tersebut, pilih edge dengan bobot terkecil.
  2. Tandai edge yang dipilih dengan warna hijau.
  3. Apabila ada edge yang kedua node-nya sudah terkena jalur hijau, tandai edge tersebut dengan warna merah (karena jika dipilih akan membentuk jalur cycle ๐Ÿกช melanggar syarat tree)
  4. Bandingkan semua edge yang terhubung ke node-node hijau. Pilih bobot terkecil. Tandai edge yang dipilih dengan warna hijau.
  5. Ulangi sampai semua node telah dilewati jalur hijau, maka jalur hijau yang terbentuk adalah MST yang dicari.

Contoh Algoritma Dijkstra

Berikut ini contoh algoritma dijkstra beserta langkah-langkahnya


Materi Lengkap

Silakan baca juga beberapa artikel menarik kami tentang Graph, daftar lengkapnya adalah sebagai berikut.


Tonton juga video pilihan dari kami berikut ini

Bagikan ke teman-teman Anda

Contact Us

How to whitelist website on AdBlocker?

How to whitelist website on AdBlocker?

  1. 1 Click on the AdBlock Plus icon on the top right corner of your browser
  2. 2 Click on "Enabled on this site" from the AdBlock Plus option
  3. 3 Refresh the page and start browsing the site
error: Content is protected !!
Up