Algoritma Boruvka


Algoritma Boruvka adalah salah satu algoritma yang digunakan untuk pencarian jalur. Contoh yang dibahas kali ini adalah mengenai menghubungkan semua titik dengan biaya terendah.
Sama seperti Algoritma Kruskal yang sudah pernah dibahas sebelumnya, algoritma ini hanya bertujuan untuk menghubungkan semua titik, bukan untuk mencari jalur yang tersambung dari awal sampai akhir. Contoh kasus nyata yang dapat digunakan adalah menghubungkan semua komputer dalam 1 jaringan pada sebuah warnet. Jika terdapat pemasangan komputer baru, tentu saja cukup dihubungkan dengan komputer terdekat, tidak perlu langsung dihubungkan dengan komputer induk, kecuali jika komputer induk memang merupakan komputer terdekat.



Diasumsikan ada 5 titik yang harus dihubungkan semuanya, yaitu titik A,B,C,D,E
semua titik tidak terhubung secara langsung dengan titik-titik lainnya, melainkan hanya melalui jalur tertentu saja
setiap jalur juga memiliki biaya sendiri-sendiri
Tentukan jalur yang harus diambil untuk menghubungkan semua titik dengan biaya terendah
Diasumsikan data jalur yang tersedia adalah sebagai berikut

Titik awal Titik Tujuan Biaya
Titik A Titik B 6
Titik A Titik E 7
Titik B Titik C 5
Titik B Titik D 4
Titik B Titik E 8
Titik C Titik D 7
Titik C Titik E 3
Titik D Titik E 9

Contoh data titik adalah sebagai berikut:

Jika diilustrasikan dalam gambar, maka model data awal adalah sebagai berikut
kruskal awal



Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
* Tentukan jumlah titik yang harus dihubungkan
Diasumsikan dalam kasus ini, jumlah titik ada 5 buah

* Tentukan jumlah garis penghubung antar titik yang telah diketahui
Diasumsikan dalam kasus ini, jumlah garis ada 8 buah


Langkah-langkah penggunaan algoritma ini adalah

* Masukkan data titik dan garis kedalam masing-masing variabel yang tersedia

* Agar dapat menjalankan skrip diatas, maka diperlukan 2 buah Class, yaitu Class Gambar untuk menampung data jumlah titik, jumlah garis, dan daftar garis pada masing-masing titik, dan Class Garis untuk menampung data titik-titik ujung dan biaya garis tersebut. Deklarasi kedua class tersebut adalah sebagai berikut:

* Lakukan proses perhitungan dengan metode Boruvka
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 1 – 2)

1. Lakukan perhitungan sampai sebanyak jumlah titik atau hasil jawaban garis sudah sama dengan jumlah titik (poin 1a dan 1b)

1a. Lakukan perhitungan pada masing-masing garis yang diketahui
cari garis yang terdekat pada masing-masing titik

1a1. tentukan titik-titik ujung yang membentuk garis
Kemudian cari induk untuk masing-masing titik ujung tersebut
Penjelasan tentang fungsi mencari induk titik akan dijelaskan pada perhitungan dibawah ini

* Gunakan fungsi ini untuk mencari induk dari sebuah titik
Penjelasan mengenai langkah-langkah perhitungan dapat dilihat pada keterangan skrip dibawah ini

1a2. Apabila induk titik ujung pertama dan induk titik ujung kedua berada pada pohon yang sama,
maka lanjutkan perhitungan untuk garis berikutnya

1a3. Garis terdekat adalah garis dengan biaya paling rendah pada masing-masing titik

1b. Lakukan perulangan pada semua titik
Tambahkan semua garis yang sudah ditemukan

1b1. Jika garis ini sebelumnya sudah pernah menghubungkan titik, maka tidak perlu menambah garis lagi
Jika tidak, maka simpan garis tersebut, kemudian lakukan penggabungan pohon antara induk titik ujung 1 dan 2
Penjelasan tentang fungsi menggabungkan pohon akan dijelaskan pada perhitungan dibawah ini

* Gunakan fungsi ini untuk mengetahui apakah antara 2 titik saling berhubungan atau tidak
Cara perhitungan adalah dengan mencari induk antara 2 titik tersebut
Fungsi mencari induk titik sudah dibahas pada perhitungan sebelumnya

* Gunakan fungsi ini untuk melakukan penggabungan pohon antara 2 titik
Penggabungan pohon digunakan untuk menggabungkan 2 pohon yang baru saja dihubungkan oleh garis
Penjelasan mengenai langkah-langkah perhitungan dapat dilihat pada keterangan skrip dibawah ini

2. Lakukan pengecekan apakah jawaban pohon sudah memenuhi kriteria

2a. Lakukan pengecekan total biaya
Apabila jumlah biaya yang dihitung tidak sama dengan perhitungan biaya sebelumnya, maka hasil jawabannya salah

2b. Lakukan pengecekan apakah jawaban garis yang ditemukan dapat menghubungkan sebuah titik sampai kembali ke titik itu sendiri
Jika demikian, maka hasil jawaban nya salah

2c. Lakukan pengecekan apakah jawaban garis yang ditemukan semuanya saling menghubungkan titik secara berkesinambungan
Jika tidak demikian, maka hasil jawaban nya salah

2d. Lakukan pengecekan apakah hasil jawaban sudah betul (biaya minimal) (poin 2d1 dan 2d2)

2d1. Hubungkan semua garis pada pohon selain garis grs

2d2. Lakukan pengecekan pada semua garis lainnya
Apabila ada garis yang belum terhubung, dan biayanya kurang dari biaya garis grs, maka hasil jawaban adalah salah

* Agar dapat menjalankan skrip diatas, maka diperlukan sebuah Class PohonGabungan untuk menampung data induk titik, peringkat, dan jumlah titik yang ada. Deklarasi Class PohonGabungan adalah sebagai berikut:

3. Catat hasil akhir untuk masing-masing jawaban garis yang ditemukan
Kemudian catat total biaya garis tersebut


Hasil akhir adalah: (klik untuk perbesar gambar)

cmd65

Jika diilustrasikan dalam gambar, maka model hasil akhirnya adalah sebagai berikut
kruskal akhir


Contoh modul / source code dalam bahasa VB (Visual Basic) dapat didownload disini:



Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.

Tinggalkan sebuah komentar

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *