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

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}

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

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

Const jumlahGaris As Integer = 8

Langkah-langkah penggunaan algoritma ini adalah

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

Dim gmb As New Gambar(jumlahTitik, jumlahGaris, dataGaris)

* 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:

Public Class Gambar
    Private jumlahTitik As Integer
    Private jumlahGaris As Integer
    Private daftarGarisPadaTitik As ArrayList

    Public Sub New(ByVal jumlahTitik As Integer, ByVal jumlahGaris As Integer, dataGaris()() As Integer)
        Me.jumlahTitik = jumlahTitik
        Me.jumlahGaris = jumlahGaris

        daftarGarisPadaTitik = New ArrayList
        For i As Integer = 0 To Me.jumlahTitik - 1
            daftarGarisPadaTitik.Add(New List(Of Garis)())
        Next

        Dim grs As Garis
        For i As Integer = 0 To dataGaris.Count - 1
            grs = New Garis(dataGaris(i)(0), dataGaris(i)(1), dataGaris(i)(2))
            tambahGaris(grs)
        Next
    End Sub

    Public Sub tambahGaris(ByVal grs As Garis)
        Dim idxTitikUjung1 As Integer = grs.titikUjung1
        Dim idxTitikUjung2 As Integer = grs.titikUjung2

        If idxTitikUjung1 < 0 OrElse idxTitikUjung1 >= Me.jumlahTitik Then
            Throw New IndexOutOfRangeException("Titik " & idxTitikUjung2 & " tidak berada diantara 0 dan " & (Me.jumlahTitik - 1))
        End If
        If idxTitikUjung2 < 0 OrElse idxTitikUjung2 >= Me.jumlahTitik Then
            Throw New IndexOutOfRangeException("Titik " & idxTitikUjung2 & " tidak berada diantara 0 dan " & (Me.jumlahTitik - 1))
        End If

        daftarGarisPadaTitik(idxTitikUjung1).Add(grs)
        daftarGarisPadaTitik(idxTitikUjung2).Add(grs)
    End Sub
	
	. . .
End Class

Public Class Garis
    Private m_titikUjung1 As Integer
    Private m_titikUjung2 As Integer
    Private m_biaya As Double

    Public ReadOnly Property titikUjung1() As Double
        Get
            Return m_titikUjung1
        End Get
    End Property

    Public ReadOnly Property titikUjung2() As Double
        Get
            Return m_titikUjung2
        End Get
    End Property

    Public ReadOnly Property biaya() As Double
        Get
            Return m_biaya
        End Get
    End Property

    Public Sub New(ByVal titikUjung1 As Integer, ByVal titikUjung2 As Integer, ByVal biaya As Double)
        If titikUjung1 < 0 Then
            Throw New IndexOutOfRangeException("Titik harus bernilai angka bulat positif")
        End If
        If titikUjung2 < 0 Then
            Throw New IndexOutOfRangeException("Titik harus bernilai angka bulat positif")
        End If
        If Double.IsNaN(biaya) Then
            Throw New ArgumentException("Biaya harus bernilai angka")
        End If

        m_titikUjung1 = titikUjung1
        m_titikUjung2 = titikUjung2
        m_biaya = biaya
    End Sub
	
	. . .
End Class

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

mst.ProsesPerhitungan(gmb, jumlahTitik)

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

Dim GarisTerdekat(jumlahTitik - 1) As Garis
For Each grs As Garis In G.daftarGaris
. . .

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

Dim titikUjung1 As Integer = grs.titikUjung1
Dim titikUjung2 As Integer = grs.titikUjung2
Dim i As Integer = pohon.CariIndukTitik(titikUjung1)
Dim j As Integer = pohon.CariIndukTitik(titikUjung2)

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

Public Function CariIndukTitik(ByVal p As Integer) As Integer
	If p < 0 OrElse p >= indukTitik.Length Then
		Throw New IndexOutOfRangeException()
	End If

	Do While p <> indukTitik(p)
		indukTitik(p) = indukTitik(indukTitik(p))
		p = indukTitik(p)
	Loop
	Return p
End Function

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

If i = j Then Continue For

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

If GarisTerdekat(i) Is Nothing OrElse grs.biaya < GarisTerdekat(i).biaya Then GarisTerdekat(i) = grs
If GarisTerdekat(j) Is Nothing OrElse grs.biaya < GarisTerdekat(j).biaya Then GarisTerdekat(j) = grs

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

If (Not pohon.isTerhubung(titikUjung1, titikUjung2)) Then
	jalur.Add(grs)
	m_biaya += grs.biaya
	pohon.union(titikUjung1, titikUjung2)
End If

* 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

Public Function isTerhubung(ByVal p As Integer, ByVal q As Integer) As Boolean
	Return CariIndukTitik(p) = CariIndukTitik(q)
End Function

* 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

Public Sub union(ByVal p As Integer, ByVal q As Integer)
	Dim i As Integer = CariIndukTitik(p)
	Dim j As Integer = CariIndukTitik(q)
	If i = j Then Return

	'arahkan akar induk yang peringkatnya lebih rendah menuju akar induk yang peringkatnya lebih tinggi
	If peringkat(i) < peringkat(j) Then
		indukTitik(i) = j
	ElseIf peringkat(i) > peringkat(j) Then
		indukTitik(j) = i
	Else
		indukTitik(j) = i
		peringkat(i) += 1
	End If
	m_jumlahTitik -= 1
End Sub

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

Dim totalBiaya As Double = 0.0
For Each grs As Garis In jalur
	totalBiaya += grs.biaya
Next grs

Const EPSILON As Double = 0.000000000001
If Math.Abs(totalBiaya - m_biaya) > EPSILON Then
	Console.WriteLine("jumlah biaya yang baru dihitung " & totalBiaya & " tidak sama dengan biaya yang sudah dihitung  " & m_biaya)
	Return False
End If

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

pohon = New PohonGabungan(jumlahTitik)
For Each grs As Garis In jalur
	Dim titikUjung1 As Integer = grs.titikUjung1
	Dim titikUjung2 As Integer = grs.titikUjung2

	If pohon.isTerhubung(titikUjung1, titikUjung2) Then
		Console.WriteLine("hasil jawaban bukan merupakan pohon")
		Return False
	End If
	pohon.union(titikUjung1, titikUjung2)
Next grs

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

For Each grs As Garis In G.daftarGaris
	Dim titikUjung1 As Integer = grs.titikUjung1
	Dim titikUjung2 As Integer = grs.titikUjung2

	If (Not pohon.isTerhubung(titikUjung1, titikUjung2)) Then
		Console.WriteLine("Terdapat garis yang terputus pada hasil jawaban")
		Return False
	End If
Next grs

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

2d1. Hubungkan semua garis pada pohon selain garis grs

For Each grslain As Garis In jalur
	Dim titikUjungLain1 As Integer = grslain.titikUjung1
	Dim titikUjungLain2 As Integer = grslain.titikUjung2

	If grslain IsNot grs Then
		pohon.union(titikUjungLain1, titikUjungLain2)
	End If
Next grslain

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

For Each grslain As Garis In G.daftarGaris
	Dim titikUjungLain1 As Integer = grslain.titikUjung1
	Dim titikUjungLain2 As Integer = grslain.titikUjung2

	If (Not pohon.isTerhubung(titikUjungLain1, titikUjungLain2)) Then
		If grslain.biaya < grs.biaya Then
			Console.WriteLine("Garis " & grslain.ToString & " mengembalikan biaya yang lebih rendah daripada garis " & grs.ToString)
			Return False
		End If
	End If
Next grslain

* 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:

Public Class PohonGabungan
    Private indukTitik() As Integer     ' indukTitik[i] = induk dari titik ke i
    Private peringkat() As SByte        ' peringkat[i] = peringkat dari sub pohon yang memiliki akar titik i (sByte tidak bisa lebih dari 31)
    Private m_jumlahTitik As Integer

    Public Sub New(ByVal jumlahTitik As Integer)
        If jumlahTitik < 0 Then Throw New ArgumentException()
        m_jumlahTitik = jumlahTitik

        indukTitik = New Integer(jumlahTitik - 1) {}
        peringkat = New SByte(jumlahTitik - 1) {}
        For i As Integer = 0 To jumlahTitik - 1
            indukTitik(i) = i
            peringkat(i) = 0
        Next i
    End Sub
	
	. . .
End Class

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

For i As Integer = 0 To mst.hasil.Count - 1
	Console.WriteLine("Jalur " & i + 1 & " adalah dari titik " & Chr(mst.hasil(i).titikUjung1 + 65) & " ke titik " & Chr(mst.hasil(i).titikUjung2 + 65) & " dengan biaya " & mst.hasil(i).biaya)
Next
Console.WriteLine("Total biaya = " & mst.biaya)

Hasil akhir adalah: (klik untuk perbesar gambar)

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

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.