Algoritma Kruskall

Algoritma Kruskal adalah algoritma dalam teori graph yang menemukan suatu pohon rentang minimum untuk terhubung dalam graf berbobot . Ini berarti menemukan subset dari tepi yang membentuk sebuah pohon yang mencakup setiap titik , di mana berat total dari semua tepi di atas pohon diminimalkan.. Jika grafik tidak terhubung, maka menemukan hutan rentang minimum (pohon rentang minimum untuk setiap komponen terhubung ) . Algoritma Kruskal adalah contoh dari algoritma rakus . Algoritma ini pertama kali muncul dalam Prosiding American Mathematical Society , hal 1956. Algoritma lain untuk masalah ini termasuk Algoritma Prim , Reverse-Hapus algoritma , dan algoritma Borůvka's

Dasar pembentukan algoritma Kruskal berasal dari analogi growing forest. Growing forest maksudnya adalah untuk membentuk pohon merentang minimum T dari grafG adalah dengan cara mengambil satu per satu sisi dari graf G dan memasukkannya ke dalam pohon yang telah terbentuk sebelumnya. Seiring dengan berjalannya iterasi untuk setiap sisi, maka forest akan memiliki pohon yang semakin sedikit. Oleh sebab itu, maka analogi ini disebut dengan growing forest. Algoritma Kruskal akan terus menambahkan sisi – sisi ke dalam hutan yang sesuai hingga akhirnya tidak akan ada lagi forest dengan, melainkan hanyalah sebuah pohon yang merentang minimum.

Graph : kumpulan dua himpunan yaitu himpunan titik ( vertex / simpul / node ) dan kumpulan dari garis ( edge )
Tree : graph tak berarah yang terhubung dan tidak mengandung sirkuit. Sirkuit : simpul awal = simpul akhir

PR

Soal : Buatlah Minimum Spanning Tree + Total Cost !!

Jawab :

Gunakan Algoritma Kruskall

--------------Edge-----Cost----

1. ----- (C,D )----- 2
2. ------( A,F )----- 4
3. ------( C,E )----- 4
4. ------( B,C )----- 5
5. ------( A,C )----- 6

Maka Spanning Tree-nya adalah:

Sehingga total costnya adalah : 21

Sumber : pertama