perbandingan kompleksitas algoritma prim, algoritma kruskal, dan algoritma sollin untuk menyelesaikan masalah minimum spanning tree

Abstract

Pada penelitian ini didiskusikan tentang kempleksitas algoritma dari tiga algoritma yaitu Algoritma Prim, Algoritma Kruskal, dan Algoritma Sollin. Graf yang digunakan untuk implementasi adalah graf lengkap dengan jumlah vertex 10 sampai dengan 100 dengan increment 10 dan data yang digunakan dibangkitkan secara random dengan bobot nilai antara 1 sampai dengan 1000. Untuk implementasi data dikembangkan source code dengan menggunakan Bahasa Pemrograman C++ dan dari hasil implementasi didapat hasil dan dapat dibuktikan bahwa ketiga algoritma tersebut mempunyai kompleksitas O(n²).

 

Kata kunci: Algoritma, Kompleksitas Algoritma, Algoritma Kruskal, Algoritma Prim, Algoritma Sollin.