Menemukan Pohon Minimum dengan Algoritma Kruskal

Strategi greedy yang digunakan:

Pada setiap langkah, pilih sisi e dari graf G yang mempunyai bobot minimum tetapi e tidak membentuk sirkuit di T.

Kompleksitas algoritma: O(|E| log |E|)

—  Pada algoritma kruskal, sisi (edge) dari Graph diurut terlebih dahulu berdasarkan bobotnya dari kecil ke besar.

—  Sisi yang dimasukkan ke dalam himpunan T adalah sisi graph G yang sedemikian sehingga T adalah Tree (pohon). Sisi dari Graph G ditambahkan ke T jika ia tidak membentuk cycle.

1.       T masih kosong

2.       pilih sisi (i,j) dengan bobot minimum

3.       pilih sisi (i,j) dengan bobot minimum berikutnya yang tidak membentuk cycle di T, tambahkan (i,j) ke T

4.       Ulangi langkah 3 sebanyak (n-2) kali.

5.       Total langkah (n-1) kali

1         (Sort the edges in an increasing order)

2         A:={}

3         while E is not empty do {

3     take an edge (u, v) that is shortest in E

              and delete it from E

4         if  u and v are in different components
then                 
                add (u, v) to A

Note: each time a shortest edge in E is considered.

Contoh Soal :

Jawaban :

Soal 2 :

Jawab :