Visualisasi Pohon Rentang Minimum Menggunakan Algoritma Kruskal dan Prim

Imam Husni Al-Amin; Rina Candra Noor Santi; Budi Hartono

doi:10.35315/dinamik.v21i1.6078

Imam Husni Al-Amin Universitas Stikubank
Rina Candra Noor Santi Universitas Stikubank
Budi Hartono Universitas Stikubank

DOI: https://doi.org/10.35315/dinamik.v21i1.6078

Abstract

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
in
i dapat digunakan sebagai modul ajar yang menarik, khususnya untuk pokok bahasan pohon rentang
minimum.

References

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