Implementasi algoritma pohon merentang merentang minimum (MST) pada permainan

Abstract

Permainan pohon merentang minimum adalah permainan berkonsep matematika. Konsepnya diambil dari salah satu matakuliah matematika S1. Permainannya cukup simpel. Yaitu pemain dihadapkan pada beberapa titik secara acak dimana masing-masing titik mempunyai bobot antar titik yang berbeda. Pemain harus menghubungkan semua titik dengan sisi dengan syarat sisi tidak boleh membentuk lintasan tertutup (sikel) dan semua titik terhubung. Jawaban pemain selanjutnya akan dibandingkan dengan dua algoritma. Yaitu algoritma Kruskal dan algoritma Prim.

Algoritma Kruskal maupun algoritma Prim adalah algoritma pada pohon merentang minimum. Kedua algoritma ini sebenarnya mempunyai tujuan yang sama, yaitu mencari bobot total minimum dari suatu pohon. Pohon adalah graf terhubung yang tidak memuat sikel. Perbedaan algoritma ini hanya pada proses pencarian. Algoritma Prim dimulai dari sebarang titik. Kemudian mencari titik lain yang belum terpilih dan terhubung dengan titik terpilih yang memiliki bobot paling kecil. Sedangkan algoritma Kruskal mengurutkan sisi yang terpendek terlebih dahulu. Kemudian mengambil urut dari sisi yang terpendek dengan syarat sisi tidak boleh membentuk sikel.

Dari proses uji coba dan analisis data, algoritma Prim dan algoritma Kruskal sudah menjadi suatu teorema, oleh karena itu kedua algoritma ini menghasilkan jawaban seminimum mungkin. Input permainan ini adalah titik-titik dan sisi. Selama proses bermain, sisi yang dipilih pemain tidak boleh membentuk sikel dan memuat semua titik. Output permainan berupa minimum spanning tree.