MST Prim dengan Timbunan
Kembangkan pepohon dari satu bucu.
MST Prim dengan Timbunan ialah pelajaran Persediaan Temu Duga Pengaturcaraan percuma di CoddyKit. Ini ialah pelajaran 4 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Persediaan Temu Duga Pengaturcaraan, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Laluan Berbeza kepada MST
Algoritma Prim juga mencari pepohon rentangan minimum, tetapi algoritma ini mengembangkan satu kelompok bersambung ke arah luar, bukannya menyusun semua sisi terlebih dahulu. 🌱
Berkembang dari Satu Bucu
Pilih mana-mana bucu permulaan dan tandakannya sebagai telah dilawati. Pepohon bermula sebagai satu nod tunggal dan berkembang satu sisi pada satu masa.
visited = [False] * nIdea Sempadan
Pada setiap langkah, lihat semua sisi yang merentasi dari pepohon ke bahagian luar. Prim sentiasa mengambil sisi sempadan yang paling murah.
Timbunan Memilih Nilai Minimum
Timbunan minimum mempercepat pencarian sisi sempadan paling murah. Masukkan sisi calon dan keluarkan pemberat terkecil pada setiap pusingan.
import heapq
heap = [(0, start)]Keluarkan Sisi Paling Murah
Keluarkan entri terkecil daripada timbunan. Entri itu memberikan pemberat dan bucu seterusnya yang paling murah untuk disambungkan kepada pepohon yang sedang berkembang.
w, u = heapq.heappop(heap)Langkau Entri Lapuk
Sesuatu bucu mungkin muncul dalam timbunan lebih daripada sekali. Jika anda mengeluarkan bucu yang sudah dilawati, abaikannya dan keluarkan entri seterusnya.
if visited[u]:
continueTambah dan Kembangkan
Tandakan bucu yang dikeluarkan sebagai telah dilawati dan tambahkan pemberatnya kepada jumlah. Kemudian masukkan setiap sisi keluarnya ke dalam timbunan untuk langkah seterusnya.
visited[u] = True
total += w
for wt, v in adj[u]:
heapq.heappush(heap, (wt, v))Ulang sehingga Lengkap
Teruskan mengeluarkan entri dan mengembangkan pepohon sehingga setiap bucu telah dilawati. Pada ketika itu, jumlah terkumpul ialah pemberat pepohon rentangan minimum.
Masa Pelaksanaan
Setiap sisi boleh dimasukkan sekali dan dikeluarkan sekali, jadi Prim berasaskan timbunan berjalan dalam O(E log V), setanding dengan Kruskal.
Prim berbanding Kruskal
Gunakan Prim pada graf padat dengan senarai kejiranan, dan Kruskal apabila anda sudah mempunyai senarai sisi biasa. Kedua-duanya menghasilkan pemberat MST yang sama.
Kelihatan Seperti Dijkstra
Gelung timbunan menyerupai Dijkstra, tetapi anda membandingkan pemberat sisi mentah, bukan jarak laluan. Mengenali corak ini menjimatkan masa pengekodan anda. ⚡
Semakan Pantas
Ingat cara Prim memilih sisi seterusnya pada setiap pusingan.
Imbas Kembali
Anda membina MST dengan Prim: bermula dari mana-mana bucu, gunakan timbunan minimum untuk menambah sisi sempadan paling murah, dan langkau lawatan yang lapuk. Syabas! 🎉
Pelajari Persediaan Temu Duga Pengaturcaraan dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 90
- Pelajaran
- 360
Soalan Lazim
Adakah pelajaran “MST Prim dengan Timbunan” percuma?
Ya — teks penuh “MST Prim dengan Timbunan” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Persediaan Temu Duga Pengaturcaraan, tingkat taraf kepada CoddyKit PRO. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “MST Prim dengan Timbunan”?
Kembangkan pepohon dari satu bucu. Anda berlatih Persediaan Temu Duga Pengaturcaraan menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan Persediaan Temu Duga Pengaturcaraan?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Persediaan Temu Duga Pengaturcaraan di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 4 daripada 4.
Berapa lamakah pelajaran “MST Prim dengan Timbunan” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran Persediaan Temu Duga Pengaturcaraan ini?
Ya. Setiap pelajaran Persediaan Temu Duga Pengaturcaraan menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- DSU dengan Pemampatan Laluan
- Gabungan Mengikut Kedudukan dan Komponen
- Pepohon Rentangan Minimum Kruskal
- MST Prim dengan Timbunan