## Visualisasi  Pohon Rentang Minimum Menggunakan Algoritma  Kruskal dan Prim
Imam Husni Al Amin, Rina Candra Noor Santi dan Budi Hartono Program Studi Teknik Informatika,  Universitas Stikubank Semarang imam_husni@yahoo.co.id, fadhlfayza910@gmail.com, pakbudi@yahoo.com

## Abstrak
Graf  memuat  objek titik  dan objek garis yang menghubungkan  titik. Properti penting  yang dimiliki oleh graf adalah arah dan bobot pada garis. Graf berbobot adalah graf yang setiap garis atau sisinya diberi sebuah  harga  (bobot).  Bobot  ini  dapat  menyatakan  jarak  antara  dua  buah  kota,  biaya  perjalanan,  waktu tempuh yang dibutuhkan, dan sebagainya.
Penelitian  ini  melakukan  analisa  pada  salah  satu  bentuk  graf  yaitu  pohon,  khususnya  pada  proses penyusunan dan pembentukan pohon rentang minimum (minimum spanning tree) menggunakan algoritma Kruskal  dan  Prim.  Kedua  algoritma  ini  menghasilkan  struktur  pohon  rentang  minimum  yang  sama, meskipun proses penyusunannya  berbeda.
Proses penyusunan melalui dua buah contoh graf akan divisualisasikan  menggunakan perangkat lunak pengolah dokumen LaTeX. Graf  A disusun  oleh  7  buah  titik  dan  11  garis sedangkan  graf  B memiliki  7 buah titik dan 12 garis. Hasil visualisasi disimpan ke dalam berkas PDF (portable document format). Berkas ini  dapat  digunakan  sebagai  modul  ajar  yang  menarik,  khususnya  untuk  pokok  bahasan  pohon  rentang minimum.
Kata Kunci: Pohon rentang minimum, algoritma  Kruskal, algoritma Prim

## PENDAHULUAN
Graf  adalah  suatu  diagram  yang  dapat menggambarkan  berbagai  macam  struktur  yang bertujuan  untuk  memvisualisasi  objek-  objek agar lebih mudah dimengerti. Aplikasi graf dalam dunia  nyata  antara  lain  menggambarkan  atau merepresentasikan  struktur  hubungan  antar objek, struktur hirarki organisasi, urutan langkah kerja,  dan  lain  sebagainya.  Dari  sekian  banyak bentuk  representasi  graf,  bentuk  pohon  ( tree ) adalah  salah  satu  yang  memiliki  terapan  cukup banyak (Siang, 2009).
Diagram  graf  memuat  objek  titik  dan objek garis yang menghubungkan titik. Properti penting yang dimiliki oleh graf adalah arah dan bobot pada garis. Garis dapat berarah atau tidak berarah.  Garis  berarah  biasanya  digunakan untuk menyatakan hubungan antar objek dengan memperhatikan  urutan  antara  objek  –  objek tersebut.  Sebaliknya,  pada  garis  tidak  berarah digunakan  untuk  menyatakan  hubungan  antar objek  yang  tidak  memerlukan  adanya  urutan (Siang, 2009).
Graf  berbobot  adalah  graf  yang  setiap garis atau sisinya diberi sebuah harga atau bobot. Bobot  ini  dapat  menyatakan  jarak  antara  dua
buah kota, biaya perjalanan, waktu tempuh yang dibutuhkan,  dan lain sebagainya. Istilah lain dari graf berbobot adalah graf berlabel (Munir, 2010). Label  di  sini  dapat  berarti  memberi  nilai  pada garis juga memberi nama pada titik.
Penelitian ini akan  melakukan analisa pada salah  satu  bentuk  graf  yang  memiliki  banyak penerapan  di  dunia  nyata  yaitu  pohon  ( tree ), khususnya pada  proses  penyusunan atau pembentukan pohon rentang minimum
( minimum spanning tree ) menggunakan algoritma  Kruskal  dan  Prim.  Konsep  pohon rentang minimum secara lengkap dalam perspektif  matematika diskrit  dan  struktur  data pernah ditulis oleh Graham dan Hell pada tahun 1985, dan Jayawant dan Glavin tahun 2009.
Dua  buah  contoh  graf  akan  dicari  pohon rentang minimumnya. Proses penyusunan pohon dikerjakan  secara  manual  mengikuti  langkah- langkah  algoritma  Kruskal  dan Prim. Perangkat lunak  pengolah  dokumen  LaTeX  digunakan untuk  menggambarkan  atau  memvisualisasikan hasil  dari  setiap  langkah  pada  saat  proses penyusunan  pohon ini. Hasil  visualisasi disimpan  ke  dalam  berkas  PDF  ( portable document format ).

## METODE  PENELITIAN
Metode  penelitian  yang  digunakan  yaitu studi pustaka terutama untuk konsep graf, pohon, algoritma Kruskal dan Prim. Menyusun perintah- perintah ( source code ) yang dikenali oleh LaTeX untuk  menggambarkan  proses  pembentukan pohon rentang minimum.
Bahan  penelitian  menggunakan  dua  buah contoh  graf,  dimana  matriks  bobot  dan  bentuk kedua  graf ini dapat  dilihat  pada  Gambar  1 dan Gambar  2. Graf A memiliki  7 buah  titik dan 11 garis atau sisi, sedangkan graf B memiliki 7 buah titik  dan  12  garis.  Perangkat  lunak  yang digunakan  adalah  TexMaker  ( universal  LaTex editor )  versi  4.0.4,  Beamer  ( document  class ) versi 3.24 untuk menghasilkan berkas presentasi PDF, dan Tikz ( package library ) versi 2.10.
Gambar  1. Matriks bobot dan hubungan antar titik

## Gambar 2 Gambar graf A dan Graf B
1. Pohon Rentang Minimum
(minimum spanning tree)
Pohon adalah sebuah graf terhubung  yang tidak  mengandung  sirkuit.  Definisi  lain  pohon yaitu  graf  tidak  berarah  yang  bersifat  hanya terdapat sebuah lintasan unik antara setiap pasang simpul. Beberapa pohon dapat membentuk hutan ( forest ) yaitu kumpulan pohon yang saling lepas. Konsep pohon ini memiliki penerapan yang luas, baik  di  dalam  ilmu  komputer  maupun  di  luar bidang ilmu komputer (Sedgewick, 2011).
Pohon  membantu  untuk  mempelajari struktur  data.  Para  ahli  bahasa  menggunakan konsep  pohon  parsing  ( parse  tree )  untuk menguraikan  kalimat.  Dalam  kehidupan  sehari- hari kita telah menggunakan konsep pohon untuk menggambarkan diagram sistem gugur pertandingan olahraga, silsilah keluarga, struktur organisasi,  dan  lain-lain  (Munir,  2010).  Contoh aplikasi pohon rentang  yaitu pada pemeliharaan jalan  raya  dengan  dana  terbatas.  Alokasi  dana yang  terbatas  akan  menyebabkan  pertimbangan hanya  merawat  ruas  jalan  sesedikit  mungkin, namun  semua  daerah  masih  tetap  dapat terhubung satu sama lain.
Jika  G  adalah  graf  berbobot,  maka  bobot pohon  rentang  T  dari  G  didefinisikan  sebagai jumlah  bobot  sisi  di  T.  Pohon  rentang  yang berbeda mempunyai bobot  yang  berbeda pula.
Di  antara  semua  pohon  rentang  di  G, pohon rentang  yang berbobot  minimum  disebut pohon  rentang  minimum  ( minimum  spanning tree ) (Erickson, 2013). Algoritma pohon rentang minimum  secara  lengkap  pernah  ditulis  oleh Nesetril  dan  Nesetrilova  pada  tahun  2012. Sementara itu, Tapia dan Rojas pada tahun 2004 berhasil  menerapkan konstruksi  pohon  rentang minimum untuk mengenali tulisan tangan secara on-line .  Contoh  sederhana  pohon  rentang minimum dapat dilihat pada Gambar 3 (Erickson, 2013).
Gambar 3 Pohon rentang minimum
Disini  akan  digunakan dua buah  algoritma untuk men yusun  pohon  rentang minimum yaitu algoritma  Kruskal  dan  Prim.  Proses  atau langkah-langkah penyusunan pohon menggunakan  kedua  algoritma  ini  berbeda, namun  bentuk  akhir  pohon  yang  dihasilkan adalah sama.

## 2. Algoritma Kruskal
Langkah  awal  algoritma  Kruskal  adalah sisi-  sisi  di  dalam  graf  diurutkan  terlebih  dulu berdasarkan bobot dari yang kecil ke besar. Sisi- sisi  yang  sudah  urut  berdasarkan  bobot  akan membentuk hutan dengan masing-masing  pohon di hutan hanya berupa satu buah simpul, disebut dengan hutan rentang ( spanning forest ). Misalkan T adalah pohon rentang yang sisi- sisinya diambil dari  graf  G.  Sisi  yang  dimasukkan  ke  dalam himpunan  T  adalah  sisi  graf  G  sedemikian sehingga  T  adalah  pohon.  Sisi  dari  graf  G ditambahkan ke T jika ia tidak membentuk sirkuit atau siklus di T (Munir, 2010). Berikut ini adalah langkah-langkah algoritma  Kruskal yaitu:
1. Urutkan secara menaik berdasarkan
bobotnya untuk semua sisi-sisi graf. T masih kosong.
2. Pilih sisi e (u,v) dengan bobot minimum yang tidak  membentuk  sirkuit  di  T.  Masukkan  e (u,v) ke dalam T.
3. Ulangi  langkah  nomor  2 sebanyak  n-1  kali. Proses memperoleh pohon rentang
minimum  menggunakan  algoritma  Kruskal pada  graf  B  dapat  dilihat  pada  Gambar  4 (Erickson, 2013).
Gambar 4 Pohon rentang minimum  algoritma Kruskal

## 3. Algoritma Prim
Misalkan  T  adalah  pohon  rentang  yang sisi- sisinya diambil dari graf G. Algoritma Prim membentuk pohon rentang minimum langkah per langkah. Pada setiap langkah kita mengambil sisi e dari  graf  G  yang  mempunyai bobot  minimum dan bersisian dengan simpul- simpul di dalam T tetapi  e  tidak  membentuk  sirkuit  di  dalam  T (Munir,  2010).  Berikut  ini  adalah  langkah- langkah  algoritma  Prim yaitu:
1. Ambil  sisi  dari  graf  G  yang  berbobot minimum,  masukkan  ke dalam T.
2. Pilih  sisi  e  (u,v)  yang  mempunyai  bobot minimum  dan bersisian dengan simpul di T, tetapi e (u,v) tidak  membentuk  sirkuit  di T. Masukkan e (u,v) ke dalam T.
3. Ulangi langkah 2 sebanyak n-2 kali.
Proses memperoleh pohon rentang minimum  menggunakan  algoritma  Prim  pada graf  B  dapat  dilihat  pada  Gambar  5  (Erickson, 2013).
Gambar 5 Pohon rentang minimum  algoritma Prim

## HASIL  DAN PEMBAHASAN
Percobaan  dilakukan  menggunakan  dua buah graf yaitu graf A dan graf B. Struktur kedua graf ini dapat dilihat pada Gambar 1 dan Gambar 2.  Graf  A  memiliki  7  buah  titik  dan  11  garis sedangkan  graf B  disusun  oleh  7  buah  titik  dan 12  garis.  Secara  umum,  penulisan  perintah ( source  code )  agar  dimengerti  oleh  pustaka Beamer dan Tikz untuk proses visualisasi pohon rentang  minimum  mengikuti aturan  berikut  ini (perintah lengkap dapat dilihat pada Tabel 1):
1. Menentukan  posisi  relatif  antara  satu  titik dengan  titik  lainnya.  Format  penulisan perintah menggambar sebuah titik
adalah{(posisi_kolom,posisi_bars)/nama_tit ik}. Posisi kolom paling kiri diberi nilai 0 dan akan  bertambah  1  untuk  kolom  yang disebelah  kanannya.  Pada posisi baris, maka baris  tengah  bernilai  0,  akan  bertambah  1 untuk baris diatasnya  dan berkurang 1 untuk baris dibawahnya. Contoh penulisan perintah  ada  pada  kolom  ketiga  yang  diberi catatan A.
2. Menghubungkan  titik  dengan  garis  dan menuliskan  bobot  setiap  garis.  Format penulisan perintah menggambar sebuah garis atau sisi adalah {titik_pertama/titik_kedua/bobot}. Pada
graf  tidak  berarah  maka  penulisan  titik pertama  dan  titik  kedua  bisa  dipertukarkan. Contoh  penulisan  perintah  ada  pada  kolom ketiga yang diberi catatan B.
3. Menggambar  urutan  titik  yang  membentuk pohon  rentang minimum. Format penulisan perintahnya
adalah {nama_titik/nomor_slide}. Contoh penulisan perintah  ada  pada  kolom  ketiga  yang  diberi catatan C.
4. Menggambar urutan  garis  yang  membentuk pohon  rentang minimum. Format penulisan perintahnya adalah {titik_pertama/titik_kedua}. Contoh penulisan  perintah  ada  pada  kolom  ketiga yang diberi catatan D.
5. Menentukan  garis  yang  boleh  dihilangkan karena  akan  membentuk  sirkuit.  Format penulisan
perintahnya adalah
{titik_pertama/titik_kedua/nom or_slide}.
Contoh  penulisan  perintah  ada  pada  kolom ketiga yang diberi catatan E.
Pada Gambar 6 dapat dilihat tampilan antar muka  TexMaker  yang digunakan  untuk  menulis kode  sumber,  yang  memiliki  fasilitas  untuk melihat hasilnya ( output ) dari proses quick build dan view  PDF .  TexMaker  dapat  memberitahu terjadi  kesalahan  ( error atau warning )  apabila penulisan perintah masih belum benar.
Gambar 6. Tampilan  antarmuka TexMaker Hasil penelitian dapat dilihat pada Gambar 7, Gambar  8, Gambar  9,  dan  Gambar  10. Pada graf A dan  graf B masing-masing membutuhkan 7  tahap  untuk  menghasilkan  pohon  rentang minimum.  Disini  dapat  dilihat  melalui  proses penyusunan  yang berbeda  namun  menghasilkan struktur pohon rentang yang sama.
Tabel 1. Perintah visualisasi  penyusunan  pohon rentang minimum
Gambar 7. Pohon rentang minimum  algoritme Kruskal01
Gambar 8. Pohon rentang minimum  algoritme Prim01
Gambar 9. Pohon rentang minimum  algoritme
Kruskal02
Gambar 10. Pohon rentang minimum  algoritme Prim02

## KESIMPULAN
Melalui penelitian ini dapat disimpulkan:
1. Algoritma  Kruskal  dan  algoritma  Prim menghasilkan struktur pohon rentang
minimum  yang  sama,  meskipun  melalui proses penyusunan yang berbeda.
2. Proses  visualisasi  pohon  rentang  minimum dapat  disusun menggunakan perangkat lunak pengolah dokumen LaTex.
3. Berkas hasil visualisasi disimpan
menggunakan  format  PDF  yang  dapat digunakan sebagai modul ajar yang menarik, khususnya  untuk  pokok  bahasan  pohon rentang minimum.

## SARAN
Untuk melengkapi apa  yang  telah diperoleh  dari  penelitian  ini  maka  dapat ditambahkan algoritma lain yang bisa digunakan untuk  menyusun  pohon  rentang  minimum. Selanjutnya proses algoritma ini akan dibandingkan  dengan  algoritma  Kruskal  dan algoritma
Prim. Perlu dipertimbangkan pemilihan  perangkat  lunak  yang mampu membuat  visualisasi  sekaligus  dapat  menerima masukan dari pemakai agar lebih interaktif.

## DAFTAR PUSTAKA
van  Dongen, M.R.C., 2012,  Latex  and  Friends,
Springer-Verlag  Berlin Heidelberg.
Erickson,  J.,  2013,  Algorithms,  Department  of
Computer  Science  University  of  Illinois Urbana- Champaign,  USA.
Goossens, M., dkk.,  2008,  The  Latex Graphics Companion  2nd  edition,  Adisson-Wesley,
USA.  [4]  Graham,  R.L.,  dan  Hell,  P, 1985,  On  the  History  of  the  Minimum Spanning  Tree  Problem,  Annals  of  the
History  of  Computing, Volume 7,
Number 1, 43-57, January 1985.
Jayawant,  P.,  dan  Glavin,  K.,  2009,  Minimum spanning  trees,  Involve  a  journal  of mathematics,  Vol.2  No.4  pp.437-448, mathematical sciences publishers.
Munir, R., 2010, Matematika Diskrit edisi ketiga revisi keempat,  Informatika,  Bandung.
Nesetril,  J.,  dan  Nesetrilova,  H,  2012,  The
Origins  of  Minimal Spanning  Tree
Algorithms - Boruvka  and  Jarnik,
Documenta  Mathematica  Extra  Volume ISMP (2012) 127–141.
Oetiker,  T.,  dkk.,  2011,  The  Not  So  Short Introduction  to  LATEX2,  Version  5.01, April 06, 2011.
Sedgewick, R., and Wayne, K., 2011, Algorithms 4th edition, Adisson-Wesley  USA.
Siang,  J.J.,  2009,  Matematika  Diskrit  dan Aplikasin ya  pada  Ilmu  Komputer  edisi keempat, Penerbit Andi, Yogyakarta.
Tapia,  E.,  dan  Rojas,  R.,  2004,  Recognition of
On-line Handwritten Mathematical Expressions  Using  a  Minimum  Spanning Tree Construction and Symbol Dominance,  GREC  2003  LNCS  3088, pp.329-340, Springer-Verlag Berlin Heidelberg.