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

Addy Roflin (Jurusan Matematika, Universitas Sriwijaya)

Jurnal Penelitian Sains
No 11 (2002)

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.