Penyelesaian masalah

Tahapan pada kruskal:

1. Melakukan sorting pada tiap edge mulai dari berat terendah sampai yang terberat.

2. Membangun sebuah spanning tree dengan menggabungkan semua node menggunakan berat edge yang terendah yang didapatkan dari tahap pertama. Sebuah edge dapat digunakan jika edge tersebut belum pernah digunakan dan tidak menyebabkan cycle pada spanning tree yang akan dibentuk.h awal Contoh penyelesaian kruskal:yContoh 1: akan diproses dengan algoritma kruskalasddddd

a) Graph awal yang akan diproses

b) Menghubungkan node dengan melihat bobot yang paling kecil terlebih dahulu

c) Menghubungkan node dengan melihat bobot yang paling kecil terlebih dahulu

d) Menghubungkan node dengan melihat bobot yang paling kecil terlebih dahulu

e) sehingga semua node terhubung seperti diatas. Contoh 2:

Urutkan terlebih dahulu jarak yang terpendek panjang:A-B = 50

B-E = 70

A-D = 100

D-B = 100

D-E = 110C-E = 120A-C = 210

Langkah 1:

Langkah 2:

Langkah 3:

Langkah 4:

Jadi, panjang kabel minimal yang dibutuhkan agar ke-5 kota tersebut terhubung adalah

50 + 70 + 100 + 120 = 340 kmLatar belakangMinimum Spanning tree juga dapat disebut sebagai biaya graf minimum. Sebagai contoh, apabila kita akan menuju suatu tempat dengan banyak jalur yang ada, kita akan membutuhkan biaya yang mahal untuk mencapai suatu tempat tersebut dengan jalur yang tidak optimal. Dengan adanya minimum spanning tree ini, kita dapat mengetahui jalur mana yang harus dilewati sehingga hanya memerlukan biaya yang murah, dan waktu yang lebih cepat.

Pada minimum spanning tree terdapat 2 metode, yaitu kruskal dan prim.

Kruskal yaitu salah satu algoritma yang digunakan untuk mendapatkan minimum spanning tree dengan weight terkecil,

Sedangka Prim algoritma yang digunakan untuk mendapatkan minimum spanning tree dengan dengan graph berbobot yang connect.

Pada ulasan ini kami akan menjelaskan bagaimana mendapatkan minimum spanning tree dengan algoritma Kruskal.Rumusan Masalah

Contoh:

1) Bagaimana cara menggunakan metode kruskal pada graf dibawah ini?

2) Salah satu perusahaan komunikasi akan memasang kabel fiber optik untuk menghubungkan beberapa kota. Berikut adalah estimasi panjang kabel yang diperlukan untuk menghubungkan antar kota(dalam km).

Kota:

A-D=100;B-E=70;

C-A=210;

D-B=100;

E-D=110;

C-E=120;

A-B=50;

Berapa panjang kabel minimal yang dibutuhkan agar ke lima kota tersebut terhubung?KesimpulanDengan metode kruskal ini kita dapat menyimpulkan,

Spanning tree dengan algoritma kruskal menggunakan 2 tahap yaitu, melakukan sorting pada tiap edge mulai dari berat terendah sampai yang terberat, dan membangun sebuah spanning tree dengan menggabungkan semua node menggunakan berat edge yang terendah yang didapatkan dari tahap pertama.

Dengan syarat yaitu sebuah edge dapat digunakan jika edge tersebut belum pernah digunakan dan tidak menyebabkan cycle pada spanning tree yang akan dibentuk.Analisa algoritma II

Minimum spanning tree

kruskalDisusun oleh:

Muh. Nur ramadhan (115100041)Aftur hidayat

(115100058)

Arif gunawan

(115100055)