VISUALISASI POHON RENTANG MINIMUM MENGGUNAKAN ALGORITMA KRUSKAL DAN PRIM

Abstract

Graf memuat obyek titik dan obyek 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