Minimum Spanning Tree Kruskal
Menambahkan sisi termurah tanpa membentuk siklus
Minimum Spanning Tree Kruskal adalah pelajaran Competitive Programming Academy gratis di CoddyKit. Ini adalah pelajaran 3 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 Competitive Programming Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Apa Itu MST
Pohon merentang minimum menghubungkan setiap simpul dengan menggunakan total bobot sisi yang paling rendah, tanpa siklus. Bayangkan memasang jaringan kabel di sebuah kota dengan biaya serendah mungkin. 🌲
Gagasan Utama Kruskal
Algoritma Kruskal sepenuhnya bersifat rakus: terus tambahkan sisi termurah yang tidak membentuk siklus hingga seluruh graf terhubung.
Langkah Pertama: Urutkan Sisi
Pertama, sort setiap sisi berdasarkan bobot, mulai dari yang terkecil. Memilih sisi murah secara rakus adalah alasan total akhirnya menjadi minimum.
edges.sort() # (weight, u, v)Mengapa DSU Sangat Cocok
Penambahan sisi hanya membentuk siklus jika kedua ujungnya sudah terhubung. DSU menjawab pengujian keterhubungan itu dalam waktu yang hampir konstan. 🤝
Telusuri Sisi yang Telah Diurutkan
Telusuri sisi dari yang termurah hingga yang termahal. Untuk setiap sisi, periksa apakah kedua ujungnya sudah memiliki akar yang sama dalam DSU.
for w, u, v in edges:
ru, rv = find(u), find(v)Terima atau Tolak
Jika akarnya berbeda, sisi tersebut menghubungkan dua bagian terpisah, jadi terima sisi itu dan gabungkan keduanya. Jika akarnya sama, lewati sisi tersebut untuk menghindari siklus.
if ru != rv:
union(u, v)
total += wKetahui Kapan Harus Berhenti
Pohon merentang dengan n simpul memiliki tepat n dikurangi 1 sisi. Setelah Anda menerima sebanyak itu, Anda dapat berhenti lebih awal.
Mendeteksi Keterpisahan
Jika semua sisi telah selesai ditelusuri tetapi sisi yang diterima kurang dari n dikurangi 1, graf tersebut tidak terhubung dan tidak ada pohon merentang yang dapat dibentuk.
Biaya Waktu
Pengurutan menjadi operasi yang paling dominan, sehingga algoritma Kruskal berjalan dalam O(E log E). Operasi DSU sangat murah sehingga hampir tidak menambah total tersebut.
Mengapa Pendekatan Rakus Benar
Sifat potongan menjamin bahwa sisi paling ringan yang melintasi pemisahan mana pun aman untuk ditambahkan. Itulah alasan memilih dari yang termurah tidak pernah keliru.
Kapan Memilih Kruskal
Kruskal sangat unggul pada graf jarang yang diberikan sebagai daftar sisi, format yang biasanya langsung disediakan oleh soal-soal pemrograman kompetitif. ⚡
Pemeriksaan Singkat
Tentukan hal yang membuat Kruskal menolak sebuah sisi.
Rangkuman
Anda membangun MST Kruskal: urutkan sisi, tambahkan sisi termurah yang menghubungkan dua komponen melalui DSU, lalu berhenti setelah n dikurangi 1 sisi. 🎉
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Minimum Spanning Tree Kruskal” gratis?
Ya — teks lengkap “Minimum Spanning Tree Kruskal” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Competitive Programming Academy, upgrade ke CoddyKit PRO. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Minimum Spanning Tree Kruskal”?
Menambahkan sisi termurah tanpa membentuk siklus Kamu berlatih Competitive Programming Academy 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 Competitive Programming Academy?
Tidak diperlukan pengalaman sebelumnya. Competitive Programming Academy 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 3 dari 4.
Berapa lama pelajaran “Minimum Spanning Tree Kruskal” 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 Competitive Programming Academy ini?
Ya. Setiap pelajaran Competitive Programming Academy 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
- DSU dengan Kompresi Jalur
- Union berdasarkan Rank dan Komponen
- Minimum Spanning Tree Kruskal
- MST Prim dengan Heap