ALGORITMA PRIM DAN KRUSKAL DALAM MENCARI MINIMUM SPANNING TREE PADA BAHASA PEMROGRAMAN C

Hendarman Lubis, Dwi Budi Srisulistiowati

Sari


Abstrak

Algoritma prim dan kruskal merupakan kedua jenis algoritma yang dapat digunakan untuk mencari minimum spanning tree (MST) pada sebuah graf. Dalam pencarian MST di sebuah graf, algoritma prim berorientasi pada titik atau vertex graf, sedangkan algoritma kruskal berorientasi pada bobot (weight) sisi graf. Walaupun perbedaan orientasi namun kedua algoritma tersebut mampu memberikan solusi yang sama. Algoritma prim mempunyai kompleksitas waktu (worst case) O(E Log V), sedangkan algoritma kruskal O( E Log E) dan O(E Log V). Kompleksitas waktu tersebut sangat berpengaruh pada kecepatan waktu eksekusi atau running time dalam menjalankan algoritma proses pencarian MST, dimana algoritma prim akan mempunyai running time tercepat ketika kompleksitas graf rumit sedangkan algoritma kruskal akan lebih cepat jika kompleksitas graf sederhana. Hal tersebut juga sudah terbukti ketika diimplementasikan menggunakan bahasa pemrograman C, sehingga keefisienan waktu masing-masing algoritma dapat ditentukan berdasarkan tingkat kompleksitas graf yang diberikan.

Kata Kunci: Algoritma Kruskal, Algoritma Prim, Graf, Minimum Spanning Tree, Running Time.


Teks Lengkap:

PDF

Referensi


F. Daniel and P. N. L. Taneo, Teori Graf. Yogyakarta, Indonesia: Deepublish, 2019.

M. K. Siregar, Matematika Diskrit. Lampung, Indonesia: Perahu Litera, 2018.

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction To Algorithms, 3rd ed. London, England: Eastern Economy, 2010.

Marsudi, Teori Graf. Malang, Indonesia: Universitas Brawijaya Press, 2016.

H. M. Pandey, Design Analysis and Algorithm. New Delhi, India: Firewall Media, 2008.

S. S. Skiena, The Algorithm Design Manual, 2nd ed. New York, USA: Springer Science & Business Media, 2020.

Carlson, S. C. Graph theory. Retrieved from https://www.britannica.com/topic/graph-theory, 2017.

P. Simanjuntak, E. Elisa, H. Pangaribuan, Pengantar Konsep Struktur Data, Pustaka Galeri Mandiri, 2020.

F. Daniel, Prida N. L. Taneo, Teori Graf, Deepublish, 2019.

Majidah Khairani Siregar, Matematika Diskrit, Perahu Litera, 2018.

Nugraha, D.W, Aplikasi Algoritma Prim Untuk Menentukan Minimum Spanning Tree Suatu Graf Berbobot dengan Menggunakan Pemrograman Berorientasi Objek. Jurnal Ilmiah Foristek. Volume 1, Nomor 2, September, 2011.

S. Rizki, Penerapan Teori Graf untuk Menyelesaikan Masalah Minimum Spanning Tree (MST) Menggunakan Algoritma Kruskal, Jurnal Aksioma , Volume 1, Nomor 2, 2012.

Rusdiana, L., & Marfuah, M. The Application of Determining Students' Graduation Status of STMIK Palangkaraya Using K-Nearest Neighbors Method. International Conference on Environment and Technology (IC-Tech). Pekanbaru, Indonesia: IOP Conf. Series: Earth and Environmental Science, 2017.

Schach, S. R. Object-Oriented and Classical Software Engineering. New York: McGraw-Hill. Widya, M. A., Agustiawan, Y., Fibrian, I. D., & Muttaqin, Z. 2011.

Hameed, A, Software Development Lifecycle for Extreme Programming. International Journal of Information Technology and Electrical Engineering, 2016.




DOI: https://doi.org/10.35968/jsi.v8i2.711

Refbacks

  • Saat ini tidak ada refbacks.


Indexed by: