- Saat ini
- Di dalam pohon
- Di sebelah pohon
- Sisi terbaik sejauh ini
- Akan membentuk siklus
Pohon merentang minimum
Anda ingin menghubungkan setiap kota dengan kabel, setiap rumah dengan pipa air, atau setiap komputer dalam jaringan, dengan bahan sesedikit mungkin. Jawabannya adalah pohon merentang minimum: himpunan sisi yang menghubungkan setiap simpul dengan total panjang terkecil. Pilih algoritma Kruskal atau Prim dan jalankan langkah demi langkah untuk melihat pohon tumbuh, satu sisi terpendek yang diperbolehkan setiap kali. Tekan Putar untuk melihat pohon tumbuh, atau Langkah dan Mundur untuk maju satu langkah demi satu langkah. Geser penggeser langkah untuk melompat ke mana saja. Pilih algoritmanya: Kruskal mencoba sisi dari yang terpendek ke yang terpanjang, Prim menumbuhkan satu pohon dari awal; klik simpul untuk menjadikannya awal Prim. Angka di tiap sisi adalah panjangnya. Di bawah graf ada daftar sisi yang masih akan dicoba, atau simpul yang menunggu bergabung beserta panjang sisi terbaiknya ke pohon. Graf baru membuat graf lain; pilih berapa simpul dan sisinya. Saat papan dipilih, tombol panah melangkah, spasi memutar dan menjeda, serta Home dan End melompat ke awal dan akhir.
Cara kerjanya
- Pilih algoritma Kruskal atau Prim. Untuk Prim, klik simpul untuk menjadikannya awal.
- Tekan Putar, atau pakai Langkah dan Mundur untuk bergerak satu langkah demi satu langkah. Geser penggeser langkah untuk melompat ke mana saja.
- Perhatikan sisi bergabung ke pohon dan total panjang bertambah. Graf baru membuat graf lain untuk dicoba.
Algoritma Kruskal
Urutkan semua sisi dari terpendek ke terpanjang dan coba sesuai urutan itu. Jika sebuah sisi menghubungkan dua bagian yang belum terhubung, sisi itu masuk ke pohon. Jika kedua ujungnya sudah terhubung lewat pohon, sisi itu akan membentuk siklus, jadi dilewati. Berhenti saat jumlah sisi pohon satu lebih sedikit dari jumlah simpul. Untuk cepat mengetahui apakah dua simpul sudah terhubung, algoritma Kruskal menyimpan bagian-bagiannya dalam struktur union-find.
Algoritma Prim
Mulai dengan pohon berisi satu simpul. Setiap simpul di luar pohon mengingat sisi terpendeknya ke pohon. Berulang kali tambahkan simpul yang sisinya paling pendek, bersama sisi itu, lalu periksa sisi-sisinya: salah satunya mungkin memberi tetangga jalan masuk yang lebih pendek ke pohon. Algoritma Prim mirip algoritma Dijkstra, tetapi yang dibandingkan adalah sisi tunggal, bukan seluruh jarak dari awal. Kedua algoritma selalu berakhir dengan total panjang yang sama.
Pertanyaan yang sering diajukan
Apa itu pohon merentang minimum?
Untuk graf terhubung yang sisinya memiliki panjang, pohon merentang adalah himpunan sisi yang menghubungkan semua simpul tanpa siklus; dengan n simpul, jumlah sisinya selalu n − 1. Pohon merentang minimum adalah pohon merentang yang total panjangnya sekecil mungkin.
Apa perbedaan algoritma Kruskal dan Prim?
Algoritma Kruskal melihat sisi seluruh graf dari terpendek ke terpanjang dan menggabungkan bagian-bagian yang terpisah menjadi satu pohon. Algoritma Prim menumbuhkan satu pohon dari awal, selalu menambahkan sisi terpendek yang keluar darinya. Keduanya greedy dan menemukan pohon dengan total panjang yang sama; Kruskal cocok untuk graf jarang, Prim untuk graf padat.
Apakah pohon merentang minimum unik?
Jika semua panjang sisi berbeda, ya. Jika ada panjang yang sama, bisa ada beberapa pohon dengan total terkecil yang sama, dan algoritma bisa memilih pohon yang berbeda tergantung cara memecah seri.
Apakah pohon merentang minimum sama dengan jalur terpendek?
Tidak. Pohon merentang minimum menjaga total panjang semua sisi tetap kecil, tetapi jalur antara dua simpul di pohon bisa jauh lebih panjang daripada jalur terpendeknya. Untuk jalur terpendek, gunakan algoritma Dijkstra.
Apakah graf saya dikirim ke mana pun?
Tidak. Graf dibuat dan pohon dibangun di browser Anda, dan pengaturan terakhir Anda disimpan di penyimpanan lokal browser ini.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Ke Editor