Kalkulator Pohon Rentang Minimum

Selamat datang di Kalkulator Pohon Rentang Minimum, alat interaktif untuk menghitung MST dari graf berbobot menggunakan algoritma Kruskal atau Prim. Baik Anda sedang mempelajari teori graf, merancang infrastruktur jaringan, atau mengoptimalkan alokasi sumber daya, kalkulator ini menyediakan eksplorasi visual langkah demi langkah dari dua algoritma dasar dalam optimasi kombinatorial.

Apa itu Minimum Spanning Tree (MST)?

Minimum Spanning Tree (Pohon Rentang Minimum) dari sebuah graf berbobot, tidak berarah, dan terhubung adalah subset tepi yang:

• Menghubungkan semua simpul bersama-sama (spanning/merentang)
• Tidak mengandung siklus (pohon)
• Memiliki total bobot tepi seminimal mungkin

Untuk graf dengan V simpul, MST selalu memiliki tepat V - 1 tepi. Jika graf tidak terhubung, hasilnya adalah Minimum Spanning Forest — kumpulan MST untuk setiap komponen yang terhubung.

Algoritma Kruskal

Algoritma Kruskal adalah algoritma rakus (greedy) berbasis tepi yang membangun MST dengan memproses tepi berdasarkan urutan bobot yang meningkat. Algoritma ini menggunakan struktur data Union-Find (Disjoint Set Union) untuk mendeteksi siklus secara efisien.

Pseudocode Kruskal

Algoritma Prim

Algoritma Prim adalah algoritma rakus berbasis simpul yang menumbuhkan MST dari simpul awal. Pada setiap langkah, algoritma ini menambahkan tepi termurah yang menghubungkan simpul di dalam pohon ke simpul di luar pohon.

Pseudocode Prim

Kruskal vs Prim: Kapan Menggunakan yang Mana?

Cara Menggunakan Kalkulator Ini

1. Tentukan tepi graf Anda: Masukkan tepi dalam format simpul1, simpul2, bobot, satu per baris. MST beroperasi pada graf tidak berarah, jadi setiap tepi berfungsi di kedua arah.
2. Pilih algoritma: Pilih Kruskal untuk graf jarang atau Prim untuk graf padat. Keduanya menghasilkan MST yang optimal.
3. Atur simpul awal (hanya Prim): Secara opsional tentukan dari mana algoritma Prim dimulai. Ini mempengaruhi urutan pemilihan tepi tetapi tidak mempengaruhi total bobot MST.
4. Hitung MST: Klik "Temukan MST" untuk menjalankan algoritma. Jelajahi visualisasi interaktif, tabel tepi, dan pelacakan langkah demi langkah.
5. Telusuri langkah-langkah: Gunakan tombol Selanjutnya/Sebelumnya untuk melihat algoritma dieksekusi langkah demi langkah, dengan penyorotan canvas waktu nyata.

Memahami Hasil

Tabel Tepi MST

Menampilkan setiap tepi yang dipilih untuk MST, sesuai urutan penambahannya, bersama dengan bobot masing-masing dan total bobot MST.

Visualisasi Graf

Canvas interaktif menampilkan graf Anda dengan elemen berkode warna:

• Simpul dan tepi hijau = Bagian dari MST
• Sorotan oranye = Sedang diperiksa
• Elemen abu-abu = Belum menjadi bagian dari MST

Pelacakan Langkah demi Langkah

Menampilkan setiap keputusan algoritma: tepi mana yang diperiksa, apakah diterima atau ditolak (dan alasannya), dan status konstruksi MST saat ini.

Aplikasi Dunia Nyata dari MST

Desain Jaringan

Aplikasi yang paling klasik. Saat menghubungkan simpul (kota, server, perangkat listrik) dengan total kabel, serat, atau panjang pipa minimum, MST memberikan solusi optimal. Perusahaan telekomunikasi menggunakan algoritma berbasis MST untuk meminimalkan biaya infrastruktur.

Analisis Klaster

Dalam pembelajaran mesin dan ilmu data, pengelompokan berbasis MST (seperti single-linkage clustering) mengelompokkan titik data dengan menghapus tepi terpanjang dari MST. Ini menghasilkan klaster alami tanpa perlu menentukan jumlah grup sebelumnya.

Segmentasi Gambar

Algoritma visi komputer menggunakan MST untuk membagi gambar menjadi wilayah yang bermakna. Piksel adalah simpul, bobot tepi mewakili perbedaan warna/intensitas, dan memotong tepi MST memisahkan objek yang berbeda.

Algoritma Aproksimasi

MST memberikan pendekatan 2-aproksimasi untuk Traveling Salesman Problem (TSP) metrik. Bobot MST adalah batas bawah pada tur TSP optimal, dan menggandakan tepi MST memberikan tur dalam rentang 2x dari optimal.

Desain Sirkuit

Desain chip VLSI menggunakan MST (melalui varian pohon Steiner) untuk meminimalkan total panjang kawat yang menghubungkan komponen pada papan sirkuit, mengurangi penundaan sinyal dan biaya manufaktur.

Properti Utama MST

• Cut Property: Untuk setiap potongan (cut) graf, tepi dengan bobot minimum yang melintasi potongan tersebut berada dalam MST.
• Cycle Property: Untuk setiap siklus dalam graf, tepi dengan bobot maksimum dalam siklus tersebut TIDAK berada dalam MST (dengan asumsi bobot unik).
• Keunikan: Jika semua bobot tepi berbeda, maka MST bersifat unik. Dengan bobot duplikat, mungkin ada beberapa MST valid dengan total bobot yang sama.
• Subgraf: MST adalah subgraf dengan V-1 tepi dan tanpa siklus.

Pertanyaan yang Sering Diajukan

Apa itu Minimum Spanning Tree (MST)?

Minimum Spanning Tree adalah subset tepi dari graf berbobot, tidak berarah, dan terhubung yang menghubungkan semua simpul bersama-sama dengan total bobot tepi seminimal mungkin, tanpa membentuk siklus. MST memiliki tepat V-1 tepi untuk graf dengan V simpul.

Apa perbedaan antara algoritma Kruskal dan Prim?

Algoritma Kruskal berbasis tepi: algoritma ini mengurutkan semua tepi berdasarkan bobot dan secara rakus menambahkan tepi yang tidak membuat siklus, menggunakan struktur data Union-Find. Algoritma Prim berbasis simpul: algoritma ini menumbuhkan MST dari simpul awal dengan selalu menambahkan tepi termurah yang menghubungkan pohon ke simpul baru, menggunakan antrean prioritas. Keduanya menghasilkan MST optimal tetapi mungkin berbeda dalam urutan pemilihan tepi.

Kapan saya harus menggunakan algoritma Kruskal vs Prim?

Kruskal umumnya lebih baik untuk graf jarang (sedikit tepi relatif terhadap simpul) dengan kompleksitas waktu O(E log E). Prim lebih baik untuk graf padat dengan kompleksitas waktu O(E log V) menggunakan heap biner. Untuk graf sangat padat, Prim dengan Fibonacci heap mencapai O(E + V log V).

Bisakah sebuah graf memiliki beberapa MST yang valid?

Ya, sebuah graf dapat memiliki beberapa MST yang valid jika ada tepi dengan bobot yang sama. MST yang berbeda akan memiliki total bobot yang sama tetapi mungkin menyertakan tepi yang berbeda. Kruskal dan Prim mungkin menghasilkan MST yang berbeda untuk graf yang sama, tetapi keduanya akan memiliki total bobot minimum yang sama.

Apa saja aplikasi dunia nyata dari MST?

MST digunakan dalam desain jaringan (meminimalkan panjang kabel/serat optik), tata letak papan sirkuit, analisis klaster, segmentasi gambar, konstruksi taksonomi, mendekati masalah NP-hard seperti Traveling Salesman Problem (TSP), dan membangun jaringan jalan/pipa/listrik dengan biaya minimum.

Apakah MST berfungsi pada graf yang tidak terhubung?

MST sejati membutuhkan graf yang terhubung. Jika graf tidak terhubung, algoritma akan menghasilkan Minimum Spanning Forest — kumpulan MST, satu untuk setiap komponen yang terhubung. Kalkulator ini akan menunjukkan kapan graf tidak terhubung sepenuhnya.

Sumber Daya Tambahan

• Pohon Rentang Minimum - Wikipedia
• Algoritma Kruskal - Wikipedia
• Algoritma Prim - Wikipedia