0Pricing
Coding Interview Prep · Pelajaran

MST Prim dengan Heap

Menumbuhkan tree dari satu vertex

MST Prim dengan Heap adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 4 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.

Jalur Berbeda Menuju MST

Algoritma Prim juga menemukan pohon merentang minimum, tetapi algoritma ini menumbuhkan satu bagian terhubung ke arah luar, bukan mengurutkan semua sisi terlebih dahulu. 🌱

Mulai dari Satu Simpul

Pilih simpul awal mana pun dan tandai sebagai telah dikunjungi. Pohon dimulai sebagai satu simpul dan meluas satu sisi demi satu sisi.

visited = [False] * n

Gagasan Batas Depan

Pada setiap langkah, lihat semua sisi yang melintasi dari pohon ke bagian luar. Algoritma Prim selalu mengambil sisi termurah dari sisi-sisi batas tersebut.

Heap Memilih Nilai Minimum

Heap minimum mempercepat pencarian sisi batas yang termurah. Masukkan sisi-sisi kandidat, lalu keluarkan bobot terkecil pada setiap putaran.

import heapq
heap = [(0, start)]

Keluarkan Sisi Termurah

Keluarkan entri terkecil dari heap. Entri tersebut memberikan bobot dan simpul berikutnya yang paling murah untuk ditambahkan ke pohon yang sedang tumbuh.

w, u = heapq.heappop(heap)

Lewati Entri Lama

Sebuah simpul dapat berada di heap lebih dari sekali. Jika Anda mengeluarkan simpul yang sudah dikunjungi, abaikan saja lalu keluarkan entri berikutnya.

if visited[u]:
    continue

Tambahkan dan Perluas

Tandai simpul yang dikeluarkan sebagai telah dikunjungi dan tambahkan bobotnya ke total. Kemudian, masukkan setiap sisi keluarnya ke heap untuk langkah-langkah berikutnya.

visited[u] = True
total += w
for wt, v in adj[u]:
    heapq.heappush(heap, (wt, v))

Ulangi hingga Lengkap

Terus keluarkan entri dan perluas pohon hingga setiap simpul telah dikunjungi. Pada saat itu, total yang terkumpul adalah bobot pohon merentang minimum.

Waktu Berjalan

Setiap sisi dapat dimasukkan sekali dan dikeluarkan sekali, sehingga algoritma Prim berbasis heap berjalan dalam O(E log V), sebanding dengan Kruskal.

Prim dibandingkan dengan Kruskal

Gunakan Prim pada graf padat dengan daftar ketetanggaan, dan gunakan Kruskal ketika Anda sudah memiliki daftar sisi biasa. Keduanya menghasilkan bobot MST yang sama.

Tampilannya Seperti Dijkstra

Perulangan heap menyerupai Dijkstra, tetapi yang dibandingkan adalah bobot sisi langsung, bukan jarak jalur. Mengenali pola ini menghemat waktu Anda saat menulis kode. ⚡

Pemeriksaan Singkat

Ingat kembali cara Prim memilih sisi berikutnya pada setiap putaran.

Rangkuman

Anda menumbuhkan MST dengan Prim: mulai dari mana saja, gunakan heap minimum untuk menambahkan sisi batas termurah, dan lewati kunjungan lama. Kerja bagus! 🎉

Pertanyaan yang Sering Diajukan

Apakah pelajaran “MST Prim dengan Heap” gratis?

Ya — teks lengkap “MST Prim dengan Heap” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “MST Prim dengan Heap”?

Menumbuhkan tree dari satu vertex Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?

Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 4 dari 4.

Berapa lama pelajaran “MST Prim dengan Heap” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?

Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

  1. DSU dengan Kompresi Jalur
  2. Union berdasarkan Rank dan Komponen
  3. Minimum Spanning Tree Kruskal
  4. MST Prim dengan Heap
← Kembali ke Coding Interview Prep