<![CDATA[Minimum spanning tree (MST) pada graf berbobot adalah graf terhubung yang memuat semua titik pada graf tanpa sirkuit dan memiliki jumlah bobot paling minimum dari semua sisi. Untuk menentukan MST dari suatu graf terhubung berbobot, terdapat beberapa algoritma yang dapat digunakan, salah satunya adalah algoritma Kruskal. Dengan menggunakan algoritma Kruskal, diketahui hanya mampu menghasilkan satu MST sedangkan terdapat graf terhubung berbobot yang memungkinkan memiliki MST yang tidak tunggal. Oleh karena itu, algoritma Kruskal dimodifikasi menjadi algoritma All MST yang dapat digunakan untuk menentukan semua MST. Pada artikel ini dibahas tentang penentuan semua MST pada graf berbobot dengan menggunakan algoritma All MST. Artikel ini dimulai dengan menentukan MST awal menggunakan algoritma Kruskal, dengan bobot MST totalnya dinotasikan sebagai . MST awal inilah yang akan menghasilkan kemungkinan-kemungkinan MST lainnya pada setiap submasalah. Kemudian, dengan menggunakan algoritma Depth First Search (DFS), semua submasalah ini akan dibentuk menjadi pohon berakar. Berdasarkan hasilnya, menunjukkan bahwa algoritma All MST dapat digunakan untuk mendapatkan semua MST. Selain itu, diperoleh bahwa semua submasalah dapat dibentuk menjadi pohon berakar dengan pola kunjungan setiap submasalah yaitu DFS. Selanjutnya, untuk semua MST yang terbentuk dari algoritma All MST menghasilkan masing-masing MST yang berbeda. Kata Kunci : algoritma Kruskal, pohon berakar, algoritma Depth First Search]]>
Copyrights © 2022
