Analisis Algoritma Kruskal Gready dan Fase Pemilihan Busur dalam Menentukan Pohon Rentangan Minimum

Addy Roflin

Abstract


Algoritma Kruskal Gready merupakan salah satu algoritma untuk mendapatkan bobot pohon rentangan minimal yang dibentuk dari suatu graf terhubung terboboti. Algoritma ini mempunyai kompleksitas Θ(nlog n), dengan n adalah jumlah item yang diproses. Sebagai alternatif, algoritma Fase Pemilihan Busur memiliki kompleksitas Θ(mlog n) dengan m adalah jumlah busur dan n adalah jumlah simpul pada graf. Untuk n<m2, Θ(mlog n) = Θ(nlog n). Dengan kata lain, pada kasus terburuk, kedua algoritma tersebut sama cepatnya.


Full Text:

PDF

Refbacks

  • There are currently no refbacks.


  

 

Creative Commons License

Jurnal Penelitian Sains (JPS) Published by UP2M, Faculty of Mathematic and Natural Science Sriwijaya University is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

 

View My Stats