Pohon merentang minimum
Pada 1926, Otakar Borůvka diminta merencanakan jaringan listrik Moravia selatan semurah mungkin. Pertanyaannya, bagaimana menghubungkan setiap tempat dengan total panjang kabel paling sedikit, adalah masalah pohon merentang minimum, dan masalah ini punya beberapa jawaban paling sederhana dan elegan di seluruh ilmu komputer.
Masalahnya
Ambil graf terhubung yang sisinya memiliki panjang, atau biaya. Pohon merentang adalah himpunan sisi yang menghubungkan semua simpul dan tidak memuat siklus; dengan n simpul, jumlah sisinya selalu tepat n − 1, karena setiap sisi menghubungkan satu simpul lagi. Di antara semua pohon merentang, pohon merentang minimum memiliki total panjang terkecil. Sebuah graf bisa memiliki pohon merentang dalam jumlah sangat besar, tetapi tidak perlu mencoba semuanya.
Mengapa greedy berhasil
Bagi simpul menjadi dua kelompok dengan cara apa pun. Sisi terpendek yang melintas di antara kedua kelompok selalu termasuk dalam suatu pohon merentang minimum: jika sebuah pohon justru memakai sisi lintas yang lebih panjang, menukarnya dengan yang lebih pendek akan menghubungkan simpul yang sama dengan biaya lebih kecil. Inilah sifat potong. Sisi lain dari koin ini adalah sifat siklus: sisi terpanjang pada siklus mana pun tidak pernah diperlukan. Kedua algoritma di bawah hanya terus menerapkan aturan-aturan ini.
Sebuah contoh
Ambil sisi A–B dengan panjang 1, B–C 2, A–C 3, C–D 4, dan B–D 5. Algoritma Kruskal mengambil A–B, lalu B–C, lalu melewati A–C karena A dan C sudah terhubung dan sisi itu akan membentuk siklus, lalu mengambil C–D. Pohon memiliki tiga sisi untuk empat simpul, jadi selesai, dengan total panjang 7, dan B–D bahkan tidak pernah dilihat. Algoritma Prim dari A pertama-tama menambahkan B lewat A–B; sisi milik B, B–C (2), mengalahkan A–C (3) sebagai jalan ke C, jadi C bergabung lewat B–C; sisi milik C, C–D (4), mengalahkan B–D (5), jadi D bergabung lewat C–D. Pohon yang sama, 7 yang sama.
Kruskal, Prim, dan Borůvka
Algoritma Kruskal, diterbitkan oleh Joseph Kruskal pada 1956, mengurutkan sisi dan memakai struktur union-find untuk melewati sisi di dalam satu bagian, sehingga kerjanya tumbuh sebanding E log E. Algoritma Prim pertama kali dijelaskan oleh Vojtěch Jarník pada 1930 dan ditemukan kembali oleh Robert Prim pada 1957 dan Edsger Dijkstra pada 1959; dengan binary heap kerjanya tumbuh sebanding E log V, dan dengan array sederhana sebanding V², yang bagus untuk graf padat. Algoritma Borůvka dari 1926 membuat setiap bagian mengambil sisi keluar terpendeknya pada saat yang sama, sehingga cocok untuk komputer paralel.
Kegunaan
Pohon merentang minimum dipakai untuk merancang jaringan kabel, pipa, dan jalan yang murah. Pohon ini mengelompokkan data menjadi klaster: hapus sisi-sisi terpanjang dari pohon, dan bagian-bagian yang tersisa adalah klasternya. Pohon ini memberi rute cepat untuk masalah penjual keliling yang paling panjang dua kali rute terbaik bila jarak mematuhi ketaksamaan segitiga. Dan algoritma Kruskal atau Prim pada kisi dengan panjang sisi acak adalah cara klasik untuk membuat labirin.
Jelajahi
Buka aplikasinya, pilih Kruskal atau Prim, lalu tekan Langkah. Dengan Kruskal, sisi yang masih akan dicoba tercantum di bawah graf dari terpendek ke terpanjang; sisi yang akan membentuk siklus digambar putus-putus merah. Dengan Prim, simpul yang menunggu bergabung tercantum beserta panjang sisi terbaiknya, yang digambar putus-putus. Jalankan keduanya pada graf yang sama dan bandingkan: urutannya berbeda, tetapi total panjangnya selalu sama.
Pertanyaan yang sering diajukan
Berapa banyak sisi pada pohon merentang?
Tepat satu lebih sedikit dari jumlah simpul. Sisi yang lebih sedikit tidak bisa menghubungkan setiap simpul, dan satu sisi lagi selalu akan membentuk siklus.
Mana yang lebih cepat, Kruskal atau Prim?
Algoritma Kruskal, yang mengurutkan sisi, biasanya lebih sederhana dan cepat pada graf jarang dengan sedikit sisi. Algoritma Prim dengan heap bekerja baik pada graf padat, dan dengan array biasa butuh sekitar V² langkah berapa pun jumlah sisinya.
Apa itu union-find?
Struktur data yang mencatat simpul mana yang berada di bagian yang sama. Struktur ini menjawab “apakah keduanya terhubung?” dan menggabungkan dua bagian hampir seketika, persis yang dibutuhkan algoritma Kruskal untuk setiap sisi.
Apakah pohon merentang minimum berlaku untuk graf berarah?
Tidak secara langsung. Untuk graf dengan sisi satu arah, masalah padanannya adalah arborescence merentang minimum, yang diselesaikan dengan algoritma Chu–Liu/Edmonds.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Bangun pohon merentang minimum