Struktur Data : Spanning Tree

📋 Daftar Isi

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

Pilih node awal. Dari semua edge yang terhubung ke node awal tersebut, pilih edge dengan bobot terkecil.
Tandai edge yang dipilih dengan warna hijau.
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)
Bandingkan semua edge yang terhubung ke node-node hijau. Pilih bobot terkecil. Tandai edge yang dipilih dengan warna hijau.
Ulangi sampai semua node telah dilewati jalur hijau, maka jalur hijau yang terbentuk adalah MST yang dicari.