Latihan 1: Minimum Spanning Tree (Kruskal & Prim) — Algoritma

Latihan 1 dari materi Minimum Spanning Tree (Kruskal & Prim) di Algoritma — praktek dengan editor kode interaktif, test case otomatis, dan hint terpandu. Langsung jalan di browser.

Lengkapi function kruskalMST(n, edges) supaya mengembalikan total bobot MST, sebuah angka.

n adalah banyaknya node, bernomor 0 sampai n - 1.
edges adalah array berisi [u, v, weight].

Langkahnya:

Urutkan salinan edges dari bobot terkecil.
Siapkan union-find: array parent dengan parent[i] = i, dan function find yang mencari ketua kelompok.
Untuk tiap edge: kalau ketua u dan ketua v beda, gabungkan dan tambahkan bobotnya ke total. Kalau sama, lewati (edge itu bikin siklus).
Berhenti setelah n - 1 edge, lalu return total.

Tiga console.log di bawahnya harus mencetak, berurutan:

4
30
16

Hint

Urutkan edge dari bobot terkecil, lalu ambil satu per satu. Edge yang kedua ujungnya sudah satu kelompok dilewati, karena bikin siklus.
Pakai union-find: parent[i] = i di awal, dan find(x) yang mengikuti parent sampai ketemu node yang menunjuk dirinya sendiri. Ambil edge kalau find(u) !== find(v).
for (const [u, v, weight] of terurut) { const ru = find(u); const rv = find(v); if (ru === rv) continue; parent[ru] = rv; total += weight; } return total;

</> { } .css => #id fn()

Versi baru

HyperSheets

bagian dari BelajarWeb.dev

Membuka gerbang…

Latihan 1: Minimum Spanning Tree (Kruskal & Prim) — Algoritma

Hint

Memperbarui Aplikasi