Contoh Soal Algoritma Kruskal

Contoh [Minimum Spanning Tree]

Soal 1

screenshot_1

Dapat kita urutkan terlebih dahulu, dengan cara melihat bobot terkecil

(D,F) = 3
(D,E) = 4
(A,B) = 4
(C,F) = 5
(F,A) = 5
(A,E) = 6
(B,C) = 6
(C,D) = 7

Step By Step

(D,F) = 3 ✅
(D,E) = 4 ✅
(A,B) = 4 ✅
(C,F) = 5 ✅
(F,A) = 5 ✅
(A,E) = 6 ❌
(B,C) = 6 ❌
(C,D) = 7 ❌

Total = 3 + 4 + 4 + 5 + 5 = 21

screenshot_2 screenshot_3 screenshot_4 screenshot_5 screenshot_6

Soal 2

screenshot_7

Dapat kita urutkan terlebih dahulu, dengan cara melihat bobot terkecil

(D,F) = 5
(A,B) = 6
(E,G) = 6
(C,E) = 7
(A,D) = 7
(B,C) = 8
(B,E) = 8
(F,G) = 8
(F,E) = 9
(D,B) = 9
(D,E) = 15

Step By Step

(D,F) = 5 ✅
(A,B) = 6 ✅
(E,G) = 6 ✅
(C,E) = 7 ✅
(A,D) = 7 ✅
(B,C) = 8 ❌
(B,E) = 8 ❌
(F,G) = 8 ✅
(F,E) = 9 ❌
(D,B) = 9 ❌
(D,E) = 15 ❌

Total = 5 + 6 + 6 + 7 + 7 + 8 = 39