Algoritma Kruskal

Algoritma Kruskal

Sebuah algoritma dalam teori graf yang mencari sebuah minimum spanning tree (MST) untuk sebuah graf berbobot yang terhubung. Inti dari tree adalah tidak boleh membentuk suatu cycle atau loop.

Langkah Algoritma Kruskal :

1. Lakukan pengurutan terhadap setiap sisi di graf mulai dari sisi yang memiliki bobot terkecil.
2. Pilih sisi yang mempunyai bobot minimum yang tidak membentuk sirkuit pada pohon, kemudian tambahkan sisi tersebut ke dalam pohon. 3. Ulangi langkah kedua sebanyak n – 1 kali (n adalah jumlah simpul graf).

Kelebihan  ✅

Sangat cocok digunakan saat graf memiliki sisi berjumlah sedikit namun memiliki sangat banyak simpul, karena orientasi kerja algoritma ini adalah berdasarkan urutan bobot sisi bukan simpul.

Kekurangan  ❌ 

Kurang cocok digunakan saat graf dimana setiap simpul terhubungkan dengan semua simpul yang lain. Karena algoritma ini menitik beratkan pada pencarian sisi yang diurutkan.

Soal 1

Soal 1

Soal 1

Dapat kita urutkan terlebih dahulu, dengan cara melihat bobot terkecil

(6,1) = 10
(4,3) = 12
(7,2) = 14
(2,3) = 16
(7,4) = 18
(5,4) = 22
(5,7) = 24
(6,5) = 25
(1,2) = 28

Step By Step

(6,1) = 10✅
(4,3) = 12✅
(7,2) = 14✅
(2,3) = 16✅
(7,4) = 18❌
(5,4) = 22✅
(5,7) = 24❌
(6,5) = 25✅
(1,2) = 28❌

Total = 10 + 12 + 14 + 16 + 22 + 25 = 99

                                                                                                 


Soal 2

Soal 2

Soal 2

Dapat kita urutkan terlebih dahulu, dengan cara melihat bobot terkecil

(A,B) = 1
(D,E) = 2
(B,C) = 3
(C,D) = 4
(A,E) = 5
(A,C) = 7
(A,D) = 10

Step By Step

(A,B) = 1✅
(D,E) = 2✅
(B,C) = 3✅
(C,D) = 4✅
(A,E) = 5❌
(A,C) = 7❌
(A,D) = 10❌

Total = 1 + 2 + 3 + 4 = 10

 

Leave a Comment

Your email address will not be published. Required fields are marked *

Skip to toolbar