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

Lubis, Hendarman (2021) ALGORITMA PRIM DAN KRUSKAL DALAM MENCARI MINIMUM SPANNING TREE PADA BAHASA PEMROGRAMAN C. JSI (Jurnal sistem Informasi) Universitas Suryadarma, 08 (02). pp. 1-13. ISSN ISSN ONLINE = 2541-3228

[img] Text
Jurnal Suryadarma 1.pdf

Download (1MB)

Abstract

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.

Item Type: Article
Subjects: Teknologi dan Ilmu Terapan > Komputer > Pemrograman untuk Bahasa Pemrograman Tertentu
Divisions: Fakultas Ilmu Komputer
KODE PRODI: KODEPRODI55201#Teknik Informatika
Creators:
CreatorsNIM/NIDN
Lubis, Hendarman0013077002
Depositing User: Hendarman Lubis
Date Deposited: 16 Aug 2021 07:18
Last Modified: 16 Aug 2021 07:18
URI: http://repository.ubharajaya.ac.id/id/eprint/9965

Actions (login required)

View Item View Item