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:

Dim dataGaris(jumlahGaris - 1)() As Integer dataGaris(0) = New Integer(2) {0, 1, 6} dataGaris(1) = New Integer(2) {0, 4, 7} dataGaris(2) = New Integer(2) {1, 2, 5} dataGaris(3) = New Integer(2) {1, 3, 4} dataGaris(4) = New Integer(2) {1, 4, 8} dataGaris(5) = New Integer(2) {2, 3, 7} dataGaris(6) = New Integer(2) {2, 4, 3} dataGaris(7) = New Integer(2) {3, 4, 9}

1 2 3 4 5 6 7 8 9

Dim dataGaris(jumlahGaris - 1)() As Integer dataGaris(0) = New Integer(2) {0, 1, 6} dataGaris(1) = New Integer(2) {0, 4, 7} dataGaris(2) = New Integer(2) {1, 2, 5} dataGaris(3) = New Integer(2) {1, 3, 4} dataGaris(4) = New Integer(2) {1, 4, 8} dataGaris(5) = New Integer(2) {2, 3, 7} dataGaris(6) = New Integer(2) {2, 4, 3} dataGaris(7) = New Integer(2) {3, 4, 9}

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



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

Const jumlahTitik As Integer = 5

1	Const jumlahTitik As Integer = 5

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

Const jumlahGaris As Integer = 8

1	Const jumlahGaris As Integer = 8