Analisi Perbandingan Algoritma Kruskal dan Boruvka dalam Menyelesaikan Minumun Spanning Tree pada Complate Graph

Abstract

The problem that is often encountered in daily life is how to connect all points in one work domain with a low optimization value, for example what is the lowest cost required to connect a water pipe to each house in an area. To solve this problem, a system that is able to find a path that connects all points in one work domain with the lowest optimization is needed. In this study, the system was built using two algorithms namely, Kruskal and Boruvka algorithms and complete graph is used as a modeling of the problem. By using these two algorithms, the system will find the optimum path that connects all points in the complete graph, then the system also displays a comparison between the two algorithms in finding the optimum path. The data used is dynamic, meaning the user can enter and change the value of the side of the complete graph as needed. The value of the complexity of the Kruskal and Boruvka algorithms obtained are respectively worth Θ( n3 ) and Θ( n4 ). From the 10 tests that have been done, it is found that the Kruskal algorithm is more effective than the Boruvka algorithm to complete the minimum spanning tree in a complete graph with a number of points and sides of 15 points and 105 sides respectively.

Permasalahan yang sering dijumpai dikehidupan sehari-hari ialah bagaimana menghubungkan semua titik pada satu domain kerja dengan nilai optimasi yang rendah, misalnya berapa biaya terendah yang diperlukan untuk menghubungkan pipa air pada setiap rumah dalam satu wilayah. Untuk menyelesaikan masalah tersebut diperlukan sistem yang mampu mencari jalur yang menghubungkan semua titik pada satu domain kerja dengan optimasi yang paling rendah. Pada penelitian ini, sistem dibangun menggunakan dua algoritma yaitu, algoritma Kruskal dan Boruvka serta digunakan complete graph sebagai pemodelan terhadap masalah. Dengan menggunakan kedua algoritma tersebut, sistem akan menemukan jalur optimum yang menghubungkan semua titik pada complete graph, kemudian sistem juga menampilkan perbandingan antara kedua algoritma dalam mencari jalur optimum. Data yang digunakan bersifat dinamis artinya user dapat memasukkan dan mengubah nilai dari sisi pada complete graph sesuai kebutuhan. Nilai kompleksitas algoritma Kruskal dan Boruvka yang didapatkan adalah masing-masing bernilai Θ( n3 ) dan Θ( n4 ). Dari 10 pengujian yang sudah dilakukan didapatkan algoritma Kruskal lebih efektif dibandingkan algoritma Boruvka untuk menyelesaikan minimum spanning tree pada complete graph dengan jumlah titik dan sisi masing-masing 15 titik dan 105 sisi.