## Implementasi Pohon Merentang Minimum Dalam Menentukan Prioritas Pemeliharaan Jalur Jalan Kota Dengan Biaya Minimal
Imran Djafar (1) , Abdul Ibrahim (2)
STMIK Dipanegara Makassar Perintis Kemerdekaan Km. 9 Makassar, 0411-587194/ 081342460232 E-mail:just_imran77@yahoo.com

## Abstrak
Penelitian  ini  bertujuan  bagaimana  mengimplemtasikan  algoritma  pohon  merentang  minimum (Minimum  Spanning  Tree  disingkat    MST)      dalam  hal  ini  algoritma  prim,  kruskal  dan  brute  force kedalam  sebuah  program  aplikasi  dengan  bahasa  pemrograman  Visual  Basic.  Program  ini  berfungsi untuk  menentukan  solusi  terbaik  dengan  biaya  minimal  dalam    pencarian  jalur  prioritas  dalam pemeliharaan jalan-jalan utama kota. Peta jalan utama kota diabstraksikan kedalam graf bentuk matriks ketetanggaan, yang menggunakan teknik pembobotan jalan secara multi criteria  weight. Selain itu yang ingin  diukur  adalah  kompleksitas  waktu  algoritma  MST,  apakah  sudah  sesuai  dengan  dasar  teori  laju pertumbuhan notasi big O  atau tidak?. Penelitian ini kami lakukan di kota Makassar, dengan melakukan 2 tahapan; pengujian program algoritma MST yaitu validasi dan pengujian program,  validasi program adalah uji coba beberapa matriks graf terhubung lengkap Kemudian pengujian program  MST masalah perbaikan  jalan  dengan  memasukkan  graf  matriks  data  biaya  pemeliharan  jalan  dengan  keluaran berupa  pohon  merentang  minimum  matriks  data  pemeliharaan  jalan  kota,  dan  daftar  nama  jalan-jalan kota  MST.Hasil  penelitian  ini  menunjukkan  bahwa  pengujian  program  sudah  sesuai  dengan  algoritma MST,  selain  itu  terlihat  bahwa  algoritma  prim,  lebih  efisien  dibanding  kruskal,  sedangkan  brute  force tidak efisien dibandingkan dengan prim dan kruskal.
Kata  kunci :  Graf,  full  connected  graf,  minimum  spanning  tree,  matriks  ketetanggaan,  algoritma  prim, kruskal, dan brute force.

## Abstract
The  aim  of  the  study  was  implement  the  algorithm  of  minimum  spanning  tree  that  is  Prim algorithm,  Kruskal  algorithm  and  brute  force  to  a  visual  basic  language  program.  This  program functions to  determinine the best  solution  with minimum cost  for road maintenance. The road map  was abstracted to  a matrix graph in  the form of adjacency matrix using  multi criteria  weight by calculating several  values.  The  values  consisted  of  traffic  class,  road  condition,  and  condition  of  drainage  system. The complexity during minimum spanning tree algoritm was measured to find out the appropriateness of the growth rate of big O notation theory.The study was conducted in Makassar in two stages: the test of minimum spanning tree algorithmic program by validating was a trial of several matrices fully connected to  edge  random  value  and  similar  edge  vale,  and  incomplete  connected  graph  matrix.  The  minimum spanning  tree test  was conducted by including  matrix graph of road maintenance, and the list  of  street names  of  minimum  spanning  tree.The  result  of  study  indicate  that  the  program  testing  has  been compatible with the mimimum spanning tree algorithm is more efficient than kruscal, whereas Brute force is not efficient compared to Prim and Kruskal.
Keywords : Graf, full connected graf, minimum spanning tree, matriks adjacency, prim, kruskal, and brute force algorihtm.
1. Pendahuluan
Banyak permasalahan  yang dapat dimodelkan dengan  menggunakan graf, khususnya di  bidang teknologi informasi. Salah satunya adalah masalah dalam pencarian bobot terpendek, atau termurah guna meminimal biaya. Banyak aplikasi yang membutuhkan adanya pencarian jarak / jalur terpendek dari suatu graf.  Salah  satu  cabang  dari  teori  graf  yang  banyak  dikembangkan  saat  ini  adalah  penggunaan  teori pohon.  Konsep  pohon  dianggap  sebagai  salah  satu  konsep  yang  paling  populer  saat  ini  dan  banyak digunakan  untuk  menyelesaikan  beberapa  masalah  yang  ditemui  manusia  dalam  kehidupan  sehari-
133 harinya.  seperti ketika  hendak direntangkan  jaringan kabel  listrik  yang  menghubungkan  sejumlah  lokasi dengan panjang kabel yang digunakan sependek-pendeknya mungkin, melihat pengelompokan data yang tersebar  pada  suatu  ruang,  ataupun  pada  perencanaan  jaringan  transportasi/distribusi  barang  seperti membangun  jalur  kereta  api  yang  menghubungkan  sejumlah  kota  ataukah  seorang  salesman  yang mengadakan  kunjungan  sejumlah  kota  sebanyak  n  kota,  dimana  salesman  tersebut    harus  mengunjungi seluruh kota tersebut dengan meminimal jarak perjalanan.
Dari  fenomena  tersebut  maka  akan  dirancang  aplikasi  konsep  pohon  yaitu  pohon  merentang minimum  atau Minimum  Spanning  Tree disingkat  MST  untuk  menyelesaikan  permasalahan  jalur terpendek,    jalur  termurah,  jalur  tercepat    atau  jalur  yang  minimal  dengan  mengunjungi  seluruh  simpul atau node pada suatu graf pohon. Saat ini terdapat beberapa algoritma untuk penentuan pohon merentang minimum, namun pada penelitian   ini, kami hanya menggunakan tiga algoritma yang cukup mapan untuk menyelesaikan  permasalahan  ini  yaitu  algoritma  prim,  algoritma  kruskal  dan  brute-force.  Ketiga algoritma ini sama-sama menerapkan strategi greedy dalam pencarian solusi terbaik ( best solutions ), Salah  satu  permasalahan  yang  kami  angkat  adalah  bagaimana  cara  untuk  penentuan  jalur-jalur jalan  utama  dalam  area  kota,  yang  harus  mendapatkan  prioritas  pertama  dalam    pemeliharaan  jalan dikarenakan  dana  pemeliharaan  yang  terbatas,  sehingga  kesemua  jalan  utama  dalam  area  kota,  masih tetap terhubung satu sama lain, dengan kata lain, penentuan jalur yang menghubungkan beberapa simpul atau lokasi sehingga jalur tersebut merupakan jalur yang paling minimal.
Untuk  pencapaian  hasil,  maka  akan    digunakan  suatu  metode  untuk  menyelesaikan  masalah  Pohon Merentang Minimum ( Minimum Spanning  Tree) yaitu   Algoritma  Kruskal,  Algoritma Prim dan Brute- force.
2. Dasar Teori 2.1. Notasi “O”
Tugas yang dilakukan oleh komputer untuk menyelesaikan masalah biasanya berupa tugas yang serupa,  tetapi  dilakukan  berulang-ulang    (iterasi).  Banyakya  perulangan  yang  harus  dilakukan  oleh komputer  menentukan  lama  waktu  proses  (running  time).  Seringkali  jumlah  perulangan  yang  harus dilakukan dipengaruhi oleh jumlah data yang diproses.
Perbedaan  waktu  proses  sebagai  fungsi  jumlah  data  yang  di[roses  sangat  erat  hubungannya dengan laju pertumbuhan ( rate of growth ) algoritma yang bersangkutan. Laju pertumbuhan menunjukkan faktor  kelipatan  waktu  proses  seiring  dengan  kenaikan  jumlah  data.  Jika  jumlah  data  dilipat  duakan, berapa  faktor  perubahan  lama  waktu  proses  yang  dibutuhkan?  Dalam  computer,  laju  pertumbuhan dinyatakan  dengan  notasi-O    (dibaca  notasi  big-oh/  O-besar).  Notasi-O  memberikan  cara  untuk menyatakan  laju  pertumbuhan  algortima  secara  global/aproksimasi  dan  tidak  memperhatikan  perbedaan faktor konstanta serta perbedaan-perbedaan lain yang tidak begitu berpengaruh (Moh.Sjukani, 2009).

## 2.2.  Kompleksitas Algoritma
Kompleksitas  waktu, T ( n ),diukur  dari  jumlah  tahapan  komputasi  yang  dibutuhkan  u menjalankan  algoritma  sebagai  fungsi  dari  ukuran  masukan n .  Kompleksitas  ruang, S ( n ),  diukur  dari memori  yang digunakan oleh  struktur data yang terdapat di dalam algoritma sebagai  fungsi dari ukuran masukan n . Kompleksitas waktu dibedakan atas tiga macam [8]:
1. T max (n) : kompleksitas waktu untuk kasus terburuk (worst case),
 kebutuhan waktu maksimum.
2. T min (n) : kompleksitas waktu untuk kasus terbaik (best case),
 kebutuhan waktu minimum.
3. T avg (n) : kompleksitas waktu untuk kasus rata-rata (average case)  kebutuhan waktu secara rata-rata. 2.3. Graf
Awamnya,  diagram  yang  tersusun  atas titik dan garis yang  menghubungkan  dua  titik  .  Letak (posisi) titik, dan panjang dan bentuk lekukan garis tidak penting (Lawi, Armin.Dr.Eng, 2008).
Implementasi Pohon Merentang Minimum Dalam Menentukan Prioritas Pemeliharaan Jalur Jalan Kota Dengan Biaya Minimal – (Imran Djafar)
134
Graf G adalah pasangan terurut himpunan V dan E , <V , E >. Himpunan V disebut  himpunan  simpul  (titik)  dari  graf G ,  ditulis V ( G ).  Himpunan E disebut  himpunan rusuk  (sisi  atau  garis)  dari  graf G yang  menghubungkan  simpul  dalam V ,  ditulis E ( G ).  Graf  < V , E > dengan nama G selanjutnya ditulis G ( V , E ). Pada graf G contoh Gbr. 1.1 diperoleh: V ( G ) = { a 1 , a 2 , a 3 , a 4 , a 5 }  dan E ( G ) = { e 1 , e 2 , e 3 , e 4 , e 5 , e 6 , e 7 } Graf G ( V , E ) dimana V himpunan hingga  graf G disebut graf hingga. Graf G ( V , E ) dimana V himpunan tak-hingga  graf G disebut graf tak-hingga.

## 2.3. Definisi Graf Pohon
Graf  terhubung G yang  tidak  memuat  siklus  disebut  pohon.  Simpul  dengan  derajat  1  dalam pohon disebut daun (atau simpul ujung). Simpul yang berderajat 2 atau lebih disebut simpul cabang (atau simpul dalam atau simpul internal). Kumpulan beberapa pohon disebut hutan.
Gambar 2. Graf
Teorema; Pandang graf T dengan v buah simpul dan e buah rusuk. Pernyataan-pernyataan berikut adalah ekuivalen.
1. T adalah pohon. 2. T tidak memiliki siklus dan e = v – 1. 3. T terhubung dan e = v – 1. 4. T tidak memiliki siklus dan bagaimanapun caranya apabila 1 rusuk  ditambahkan, terdapat 1 siklus yang terjadi.
5. T terhubung dan setiap rusuk dari T adalah rusuk potong (jembatan) dari T . 6. Untuk setiap 2 simpul dalam T , hanya terdapat satu lintasan sederhana (Lawi, Armin.Dr.Eng, 2008).

## 2.4. Pohon Merentang Minimum
Jika G adalah graf berbobot, maka bobot pohon merentang T dari G didefinisikan sebagai jumlah bobot  semua  sisi  di  T.  Pohon  merentang  yang  berbeda  mempunyai  bobot  yang  berbeda  pula.  Di  antara semua  pohon  merentang  di  G,  pohon  merentang  yang  berbobot  minimum  dinamakan  pohon  merentang minimum ( minimum spanning tree ).
2.5. Algoritma Kruskal Teorema  2.5 Pandang  graf G ( V , E )  dengan n buah  simpul.  Berikut  ini  adalah  langkah algoritma Kruskal untuk mencari pohon merentang minimal dari G . Langkah-1 : Untuk i = 1, pilih rusuk e 1 dengan bobot minimal. Langkah-2 : Jika i = n – 1, selesai. Jika tidak, lanjutkan step-3. Langkah-3 : i buah rusuk yang dipilih menjadi unsur himpunan S . Kemudian, pilih e i +1 dari himpunan E – S. Di sini, e i +1 adalah rusuk dengan bobot minimal dari subgraf terinduksi rusuk ( S  { e i +1 }) G yang tidak memiliki siklus.
Pseudo-code untuk MST dengan algoritma Kruskal(G, ω ) 1. A ← Φ 2.  For each vertex  ν  V[G] 3.  Do MAKE-SET (ν)
4.  Sort the edges of E into nondecreasing order by weight ω
5.  For each edge (u,ν)  E, taken in nondecreasing order by weight 6.    Do if  FIND-SET ( u ) ≠ FIND-SET ( v ) 7.            then A ← A  {(u, v )} 8.                              UNION (u, v ) 9.    Return A
START jumNode = UBound(m) ReDim mst(jumNode, jumNode) weight = 0 pendek = 32767 STOP For brs = 1 To jumNode For klm = 1 To jumNode If m(brs, klm) < pendek And m(brs, klm) > 0 Then pendek = m(brs, klm) nodeAwal = brs nodeAkhir = klm T F T F X STOP T F X If Not siklus(m, nodeAwal, nodeAkhir) Then T F m(nodeAwal, nodeAkhir) = 32767 m(nodeAkhir, nodeAwal) = 32767 mst(nodeAwal, nodeAkhir) = m(nodeAwal, nodeAkhir) mst(nodeAkhir, nodeAwal) = m(nodeAwal, nodeAkhir) m(nodeAwal, nodeAkhir) = -1 m(nodeAkhir, nodeAwal) = -1 weight = weight + pendek For i = 1 To Jumnode -1 For i = 1 Klm 1 To Count Pendek = 32767 Pendek = 32767

## Gambar 3. Flowchart program algoritma Kruskal
2.6. Algoritma Prim Teorema 2.6 Pandang graf G ( V , E ) dengan n buah simpul, berikut ini  langkah-langkah dari algoritma prim :   *Langkah 1: ambil sisi graf G yang berbobot minimum, masukkan ke     dalam T. *Langkah 2: pilih sisi ( u,v ) yang mempunyai bobot minimum dan bersisian dengan simpul di T, tetapi ( u,v ) tidak membentuk sirkuit di T. Tambahkan ( u,v ) ke dalam T.
*Langkah 3: ulangi langkah 2 sebanyak n – 2 kali. *Setiap langkah seluruhnya di dalam algoritma Prim adalah 1 + ( n - 2 ) =  n – 1, yaitu sebanyak jumlah sisi di dalam pohon perentang dengan n buah simpul.
Pseudo-code untuk  MST dengan Algoritma Prim (G, ω,r ) 1. For each u  V [ G ] 2. do key [ u ] ← ∞ 3. л [ u ] ← NIL 4. Key [ r ] ← 0 5. Q ← V [ G ] 6. While Q ≠ Φ 7. Do u ← EXTRACT-MIN ( Q ) 8. for each v  Adj [ u ] 9. do if v  Q and ω ( u,v ) < key [ v ] 10. then л [ v ] ← u 11. key [ v ] ← ω(u,v) sumber: (Cormen, Leiserson, Rivest.,1990).
136 START jumNode =  UBound( m) ReDim mst( jumNode ,  jumNode) ReDim arrNode( jumNode) count = 1 weight = 0 arrNode( count ) =  nodeAwal For i  = 1  To jumNode -  1 pendek =  32767 For klm = 1  To count nodeAwal =  arrNode( klm) For brs = 1  To jumNode If m( brs ,  nodeAwal ) <  pendek And m( brs , nodeAwal )  > 0 Then pendek = m( brs ,  nodeAwal) prevNode =  nodeAwal nextNode = brs count =  count + 1 nodeAwal =  nextNode arrNode( count ) =  nodeAwal For a = 1  To count For b = 1  To count m( arrNode(a) ,  arrNode(b )) = 0 m( arrNode(b) ,  arrNode(a )) = 0 m( arrNode(a) ,  arrNode(b )) = 0 m( arrNode(b) ,  arrNode(a )) = 0 STOP T F For i = 1  Klm 1  To Jumnode For i = 1  Klm 1  To Jumnode For A = 1  To Count For A = 1  To Count For A = 1 To Count
Gambar  4. Flowchart program algoritma Prim
2.7. Algoritma Brute-force Teorema 2.7; Mencari semua kombinasi pohon merentang yang mungkin dibentuk dari graf lalu dipilih jumlah bobot pohon merentang yang minimum.
Algoritma Brute-force merupakan suatu metode pencarian hasil, dimana semua kemungkinan yang ada  akan  ditelusuri  sehingga  membutuhkan  waktu  yang  lama.  Algoritma  Brute-force  dapat  diterapkan untuk kasus MST, dimana proses perulangannya  menggunakan rumus kombinasi. Berikut adalah  rumus untuk mencari kombinasi :
C ( n, m ) =
)! ( ! ! m n m n 
Dimana : C ( n, m )= Kombinasi m objek diambil dari n buah objek. n= Jumlah semua lintasan yang memungkinkan. m=  Banyaknya  lintasan  yang  hanya  dapat  digunakan  sehingga  membentuk    suatu  pohon,  dimana  m = jumlah node – 1.
START weight = MAXLONG For i = 1 To pangkat (2, jumEdge(m)) frmMST.prgBar.Value = i DoEvents Call kombi(m, i) If cekKombi(m) = True Then m = mTmp If (hitungWeight(m) < weight) Then STOP T T F F mst = m weight = hitungWeight(m) For i = 1 To Jumnode -1

## Gambar 5. Flowchart program Brute force

## 2.8. Kompleksitas Algoritma Prim
Algoritma Prim mempunyai kompleksitas waktu asimptotik O (E+V log V). kompleksitas untuk asimptotik  algoritma  Prim  agak  sulit  dianalisis  karena  menggunakan  Fibonacci  heap  dalam mengimplementasikan  minimum  antrian  prioritas  (min-priority  queue)  Q,  dimana  Q  adalah  struktur  data antrian  dari  simpul-simpul  V  yang  diatur  sesuai  dengan  operasi  kamus  (dictionary  operations)  untuk mekasnisme FIFO. (Cormen, Leiserson, Rivest.,1990).
Simpul dan bobot pada graf direpresentasikan ke dalam matriks. Untuk mencari suatu sisi, maka algoritma  Prim  akan  mencari  kedua  arah  yaitu  baris  dan  kolom  graf  G  kemudian  akan  dilihat bobotnya.

## 2.9. Kompleksitas Algoritma Kruskal
Anggaplah E adalah  jumlah  sisi  pada  graf G dan V adalah  jumlah  simpul.  Algoritma kruskal  memiliki  kompleksitas  asimptotik O ( E log E ),  atau  ekuivalen  dengan O ( E log V ). Keduanya dinyatakan equivalen karena: - E paling banyak adalah V 2 dan log V 2 = 2 x log V atau O(log V ). -  Apabila kita mengabaikan simpul terpencil, V ≤2 E , jadi log V dapat disubstitusi dengan O (log E ) Kita dapat menerima batasan karena : Pertama urutkan sisi berdasarkan bobot menggunakan pengurutan perbandingan  ( comparison  sort )  dengan  waktu O ( E log E );  hal  ini  menyebabkan  langkah “menghilangkan sisi dengan bobot minimum dari S ” untuk dioperasikan pada waktu konstan. Kemudian kita gunakan sebuah struktur data himpunan disjoint untuk menjaga simpul mana yang terdapat pada suatu komponen.  Kita  membutuhkan  operasi  sebanyak O ( E ),  dua  buah  operasi  pencarian,  dan  mungkin  sebuah penggabungan  untuk  setiap  sisi.  Sebuah  struktur  data  himpunan  disjoint  sederhana  seperti  himpunan hutan disjoint dengan penggabungan berdasarkan  rangking dapat  menjalankan  operasi  O(E)  pada  waktu O(E  log  V).  Dengan  demikian  total  waktu  asimptotiknya  menjadi  O(E  log  E)  =  O(E  log  V).  (Cormen, Leiserson, Rivest.,1990).

## 2.10. Kompleksitas Algoritma Brute-force
Algoritma  brute  force  akan  menghitung sebanyak C ( n , 2) = n ( n – 1)/2  pasangan titik dan  memilih pasangan titik yang mempunyai jarak terkecil. Kompleksitas algoritma adalah O ( n 2 ).
138

## 2.11. Sistem Penilaian Jalan
Dengan  menjumlahkan  nilai  nilai  keseluruhan  keadaan  maka  didapatkan  nilai  kondisi  jalan. Urutan P rioritas dihitung. d enga n mema kai rumus   sebagai berikut :
Urutan Prioritas = 17 - (Kelas LHR + Nilai-Kondisi Jalan) Kelas LHR = Kelas.lalu-lintas untuk pekerjaan Pemeliharaan Nilai Kondisi Jalan = Nilai yang diberikan terhadap kondisi jalan
3. Desain Penelitian

## 4. Pengujian Algoritma Program Mst
Pengujian algoritma MST, dibagi atas dua bagian, yaitu pertama ; validasi program MST , dan kedua yaitu pengujian program MST pada masalah pemeliharan jalan.
Pengukuran  dilakukan  sebanyak  sepuluh  kali  percobaan  pada  setiap  satu  ukuran  matriks  yang berbeda (dapat dilihat pada lampiran 4), data matriks yang digunakan berukuran 3x3 hingga 66x66. Hasil pengukuran  kemudian  ditotal  kemudian  dirata-ratakan  lalu  dimasukkan  kedalam  tabel  hasil  komputasi waktu untuk melihat pertumbuhan kompleksitas waktunya.

## 4.1. Validasi Program MST
Uji  coba  beberapa  data  matriks  ketetanggaan  untuk  mendapatkan  sebuah  data  dan  grafik pertumbuhan kompleksitas waktu pada setiap algoritma MST untuk;
a. Graf terhubung lengkap ( full connected graph ) dengan nilai edge random Pada tabel 1 memperlihatkan hasil komputasi ketiga algoritma MST. Tampak hasil total waktu  yang ditunjukkan  oleh  algoritma  prim  masih  lebih  baik  (efisien)  dibandingkan  dengan  algoritma  kruskal, sedangkan  untuk  brute-force  terlihat  sangat  kurang  efisien  karena  waktu  yang  dibutuhkan  sangat  lama dibandingkan dengan prim dan kruskal.

## Peta Makassar Digital
Buat  penomoran,  pelabelan,  dan  tracking  untuk  setiap simpang  jalan  kota  Makassar  (perlimaan,  perempatan, pertigaan, perduaan jalan utama kota)
Buat Matriks ketetanggaannya kedalam Mic. Excell
Input Bobot berdasarkan Multi criteria weight diambil dari kalkulasi nilai kelas lalu lintas, nilai konsidi jalan, dan nilai kondisi sistem dranaise
Simpan  dengan  extensi  *.dat  yang  berisikan  adjacensy matriks  (file teks)
Jalankan  Program  Pohon  Merentang  Minimum,  dengan Algoritma Kruskal,  Prim  dan  Brute-force ,  dengan  inputan file teks
a
Peta jalan-jalan utama dalam bentuk Graf Matriks Data.
Hasil  berupa  Matriks  Data  Graf  Pohon  Merentang Minimum ( Minimum Spanning Tree ) dan Data Jalan MST.
Gambar 6. Desain penelitian
139
Tabel .1 Hasil Komputasi Waktu Matriks Full Connected Random
No Ukuran jumlah node jumlah edge T Rerata Lama Waktu Komputasi 10 x Percobaan (detik) Matriks Prim  Kruskal Brute Force 1 3x3 3 3 1.09 1.08 1.10 2 4x4 4 6 1.10 1.06 1.23 3 5x5 5 10 1.10 1.06 1.23 4 6x6 6 15 1.09 1.06 5.50 5 7x7 7 21 1.29 1.20 259.18 6 8x8 8 28 2.02 1.98 ~ 7 9x9 9 36 2.01 1.98 ~ 8 10x10 10 45 2.02 1.98 ~ 9 15x15 15 105 2.02 1.98 ~ 10 20x20 20 190 2.02 1.99 ~ 11 25X25 25 300 2.02 2.03 ~ 12 30X30 30 435 2.02 2.09 ~ 13 66X66 66 2145 2.05 4.19 ~ TOTAL  21.85 23.66 268.23
Terlihat pada gambar 7, terlihat bahwa hasil komputasi waktu Prim dan kruskal, prim jauh lebih efisien dibandingkan dengan kruskal.
Gambar 7. Grafik Hasil Komputasi Waktu Prim Dan Kruskal  Full C. Random
Terlihat pada gambar 8, terlihat bahwa  hasil komputasi waktu Brute-force  sangat kurang  efisien karena waktu yang dibutuhkan sangat  lama dibandingkan dengan prim dan kruskal.
Gambar 8. Grafik Hasil Komputasi Waktu Brute Force Full C. Random
0,00 2,00 4,00 6,00 1 3 5 7 9 11 13 Prim Kruskal 0,00 100,00 200,00 300,00 1 2 3 4 5 Brute Force Brute Force
140

## b. Not full connected graph  dengan nilai edge bernilai acak,
Pada tabel 2 memperlihatkan hasil komputasi ketiga algoritma MST. Tampak hasil total waktu yang ditunjukkan  oleh  algoritma  prim  masih  lebih  baik  (efisien)  dibandingkan  dengan  algoritma  kruskal, sedangkan  untuk  brute-force  terlihat  sangat  kurang  efisien  karena  waktu  yang  dibutuhkan  sangat  lama dibandingkan dengan prim dan kruskal.
Tabel 2. Hasil Komputasi Waktu Matriks Not Full Connected
No Ukuran jumlah node jumlah edge T Rerata Lama Waktu Komputasi 10 x Percobaan (detik) Matriks Prim  Kruskal Brute Force 1 3x3 3 3 1.13 1.27 1.76 2 4x4 4 6 1.15 1.32 1.57 3 5x5 5 9 1.01 1.36 1.57 4 6x6 6 10 1.13 1.27 1.79 5 7x7 7 12 1.17 1.32 2.50 6 8x8 8 14 1.24 1.41 4.32 7 9x9 9 17 1.13 1.29 18.52 8 10x10 10 23 1.02 1.45 2,283.95 9 15x15 15 31 1.64 1.67 ˜ 10 20x20 20 41 1.44 1.67 ˜ 11 25X25 25 53 1.32 1.69 ˜ 12 30X30 30 71 1.70 2.02 ˜ 13 66X66 66 132 1.72 2.03 ˜ TOTAL  16.80 19.78  2,315.99
Terlihat pada gambar  9, terlihat bahwa hasil komputasi waktu Prim dan kruskal, prim jauh lebih efisien dibandingkan dengan kruskal.
Gambar 9. Grafik Hasil Komputasi Waktu Prim Dan Kruskal Not Full Connected
Terlihat pada gambar 10, terlihat bahwa hasil komputasi waktu Brute-force sangat kurang efisien karena waktu yang dibutuhkan sangat  lama dibandingkan dengan prim dan kruskal.
0,00 0,50 1,00 1,50 2,00 2,50 1 3 5 7 9 11 13 Prim Kruskal
141
Gambar 10.  Grafik Hasil Komputasi Waktu Brute Force Not Full Connected
4.2. Hasil pengujian program MST pada masalah pemeliharan jalan.
a. Untuk matriks data pemeliharaan jalan
Pengujian program MST, data matriks pemeliharaan jalan, sebelum proses: Jumlah Node = 66, Jumlah Edge = 89 , Total Weight = 3117302100 , Setelah  proses  didapatkan  hasil  data,  untuk  Prim:  Jumlah  Node=  66,  Jumlah  Edge= 65 ,  Total  Weight MST= 1214028750 ,  Lama  Waktu= 2,09, Sedangkan  Kruskal:    Jumlah  Node=  66,  Jumlah  Edge= 65 , Total Weight MST= 1214028750, Lama Waktu= 2,11. Ini dapat dilihat pada lampiran III A. Sedangkan hasil data matriks oleh program MST dengan algoritma Brute Force setelah di run dengan ukuran data matriks 66x66,  hasilnya Data Type Over flow , ini disebabkan oleh tingginya kompleksitas waktu dan ruang  yang  dibutuhkan  untuk  proses  tidak  sebanding  dengan  spesfikasi  prosessor  dan  memori komputer.
Gambar  11. matriks data pemeliharaan jalan

## b. Untuk  data jalan pemeliharaan MST
Pengujian  program  MST,  untuk  data  jalan  pemeliharaan  MST,  sebelum  proses:  Jumlah  data  jalan pemeliharaan= 89  jalan, dengan Total Weight = 3117302100,
Setelah diproses oleh program MST, didapatkan hasil data jalan,  untuk Prim dan Kruskal: Jumlah data jalan pemeliharaan MST= 66 jalan, dengan Total Weight MST= 1214028750.
Terlihat  antara  kedua  algoritma,  prim  dan  kruskal,  ada  perbedaan  pemilihan  jalur  jalan  pemeliharaan, namun tetap sama nilai Total Weight  MST yang dihasilkan antara prim dan kruskal.
Gambar 12. tampilan data pemeliharaan jalan
0,00 500,00 1.000,00 1.500,00 2.000,00 2.500,00 1 2 3 4 5 6 7 8

## Brute Force
Brute Force
142
c. Untuk Visualisasi dengan peta kota oleh MapSource :
Hasil  graf  matriks  dari  proses  algoritma  MST,  yang  divisualisasikan  kedalam  graf    peta kotaMST dengan MapSource sudah sesuai dengan teori tentang pohon  merentang  minimum  ini terbukti dari  hasil  visualisasinya.  Dari  hasil  visualisasi  graf  MST  untuk  kedua  algoritma,  algoritma  prim  dan kruskal  didapatkan  hasil  graf  mst  yang  berbeda,  namun  kedua  algoritma,  prim  dan  kruskal  sama-sama menghasilkan  total  weight  cost  yang  sama  nilainya,  ini  berarti  bahwa  graf  MST  yang  dihasilkan  oleh kedua algoritma boleh berbeda, berbeda dalam pemilihan jalur edge (jalur jalan), namun keduanya sama- sama menghasikan total weight cost yang sama.

## Gambar 13. Visualisasi kedalam peta

## 5. Kesimpulan
Aplikasi  yang  dirancang  untuk  menyelesaikan  masalah  pemeliharaan  jalan  di  kota  Makassar diselesaikan  dengan  mencari  MST  dari  graf  peta  jalan  utama  kota  Makassar.  Graf  yang  digunakan diabstraksikan kedalam bentuk matriks adjecency atau matriks ketetanggaan, untuk kemudian digunakan kedalam  ketiga  Algoritma  MST.  Algoritma  Prim,  Kruskal,  dan  Brute-Force  merupakan  algoritma  yang digunakan untuk memecahkan permasalahan yang berhubungan dengan pencarian MST. Ada perbedaan yang  dimiliki  Antara  algoritma  Prim  dan  algoritma  Kruskal  yaitu,  langkah-langkah  yang  diambil  oleh masing-masing  algoritma,  jumlah  langkah,  dan  cara  penentuan    pohon  merentang  minimumnya. Algoritma  Prim  lebih  berorientasi  pada  pencarian  simpul-simpul  yang  dihubungkan  oleh  sisi  dengan bobot  minimum.  Sisi  graf  yang  dimasukkan  untuk  menjadi  kandidat  sisi  pohon  merentang  minimum adalah  sisi  yang  bersisian  dengan  simpul  sebelumnya  Sedangkan  pada  algoritma  Kruskal  lebih berorientasi pada pencarian sisi-sisi yang memiliki bobot minimum lalu mengurutkannya dari sisi dengan bobot  minimum  hingga  bobot  maksimum  kemudian  dilakukan  penyaringan  terhadap  sisi  yang membentuk  sirkuit.    Pada  algoritma  Kruskal,  proses  mengurutkan  inilah  yang  membuat  Kruskal  kalah efisien  dibandingkan  dengan  algoritma  Prim.  Hal  ini  terbukti  dari  hasil  percobaan  yang  diberikan  pada table-tabel. Algoritma Brute force merupakan suatu metode pencarian hasil, dimana semua kemungkinan yang ada akan ditelusuri  sehingga  membutuhkan  waktu yang sangat lama pada prosesnya dibandingkan dengan algoritma prim dan kruskal.  Algoritma Brute Force mencari  semua kombinasi pohon  merentang yang  mungkin  dibentuk  dari  graf  lalu  dipilih  jumlah  bobot  pohon  merentang  minimumnya,  ini  terbukti dari hasil percobaan.

## Daftar Pustaka
[1] Cormen,  Leiserson,  Rivest. Introduction  to  Algorithms. 1990.  The  MIT  Press.  Massachusetts Institute of Technology.
[2] Direktorat Jenderal Bina Marga Direktorat Pembinaan Jalan Kota, Tata Cara Penyusunan Program Pemeliharaan Jalan Kota, 1990, Jakarta.
[3] Goodaire,  Edgar  G  ;  Parmenter,  Michael  M. Discrete  Mathematics  with  Graph  Theory .  1998. Prentice Hall, Inc. New Jersey.
[4] Lawi,  Armin.  Dr.Eng,  2008.Materi  Ajar  Matakuliah  Matematika  Diskrit.  Universitas  Hasanuddin, Indonesia.
[5] Liu, C.L. Element of Discrete Mathematics 2 nd .1985. McGraw-Hill,Inc.
[6] Suarga, Ph.D., 2007 . Algoritma Pemrograman, Penerbit Andi, Yogyakarta.
[7] Moh.Sjukani.2009.    Struktur  Data  (Algoritma  &  Struktur  Data  2)  dengan  C,  C++    Edisi  3,  Mitra Wacana Media, Jakarta.
[8] Munir,Rinaldi. 2001. Matematika Diskrit . Cetakan Pertama. Informatika. Bandung.