Minimum spanning tree (MST) adalah kumpulan edge yang menyambungkan semua node di sebuah graph, tanpa siklus, dengan total bobot paling kecil. Ingat lagi: graph terdiri dari node (titik) dan edge (garis penghubung), bobot adalah biaya sebuah edge, dan siklus adalah jalan yang muter balik ke titik awal. Bayangkan PLN mau menyambungkan listrik ke semua desa dengan total kabel sependek mungkin: jaringan kabel itulah MST-nya.
🧪 Tebakan cepat: sebuah graph punya 5 node. MST-nya selalu punya berapa edge? Tebak dulu, jawabannya ada di bagian "Kruskal: termurah dulu, tolak yang bikin siklus".
Kruskal: termurah dulu, tolak yang bikin siklus
Kruskal mengurutkan semua edge dari bobot terkecil, lalu mengambilnya satu per satu. Edge yang kedua ujungnya sudah tersambung ditolak, karena dia akan bikin siklus. Graph-nya: A-B 4, A-C 2, B-C 1, B-D 5, C-D 8, C-E 10, D-E 2.
| Langkah | Edge (bobot) | Keputusan | Kelompok sesudahnya |
|---|---|---|---|
| 1 | B-C (1) | ambil | {B, C}, {A}, {D}, {E} |
| 2 | A-C (2) | ambil | {A, B, C}, {D}, {E} |
| 3 | D-E (2) | ambil | {A, B, C}, {D, E} |
| 4 | A-B (4) | tolak: A dan B sudah satu kelompok | sama |
| 5 | B-D (5) | ambil | {A, B, C, D, E} |
Totalnya 1 + 2 + 2 + 5 = 10, dengan 4 edge. Semua node sudah satu kelompok, jadi C-D dan C-E gak perlu dicek lagi. Itu jawaban tebakan: graph dengan V node selalu punya MST dengan tepat V - 1 edge. Kurang dari itu, ada node yang belum tersambung. Lebih dari itu, pasti ada siklus.
const edges = [
["A", "B", 4],
["A", "C", 2],
["B", "C", 1],
["B", "D", 5],
["C", "D", 8],
["C", "E", 10],
["D", "E", 2],
];
function kruskal(nodes, edges) {
const parent = {};
for (const n of nodes) {
parent[n] = n;
}
function find(x) {
while (parent[x] !== x) {
x = parent[x];
}
return x;
}
const terurut = [...edges].sort((a, b) => a[2] - b[2]);
let total = 0;
let dipakai = 0;
for (const [a, b, w] of terurut) {
const ra = find(a);
const rb = find(b);
if (ra === rb) continue; // sudah satu kelompok: siklus
parent[ra] = rb; // gabungkan dua kelompok
total += w;
dipakai++;
if (dipakai === nodes.length - 1) break;
}
return total;
}
console.log(kruskal(["A", "B", "C", "D", "E"], edges)); // 10
- Tiap edge ditulis
[node, node, bobot].[...edges].sort((a, b) => a[2] - b[2])bikin salinan yang urut dari bobot terkecil (a[2]adalah bobotnya). parentmencatat kelompok tiap node. Cara ini namanya union-find. Awalnya tiap node jadi kelompoknya sendiri:parent.Aberisi"A".find(x)mengikutiparentsampai ketemu node yang menunjuk dirinya sendiri. Itu ketua kelompoknya.- Kalau ketua
adan ketuabsama, keduanya sudah tersambung: edge ini dilewati dengancontinue. - Kalau beda,
parent[ra] = rbmenggabungkan dua kelompok (ketua yang digabung, bukan node-nya), lalu bobotnya masuktotal. - Loop berhenti setelah
nodes.length - 1edge.
Di langkah 4, find("A") jalan A ke C, dan find("B") jalan B ke C. Ketuanya sama-sama C, jadi A-B ditolak.
Kalau node-nya angka
Node juga bisa ditulis sebagai angka 0 sampai n - 1, dengan edge [u, v, weight]. Maka parent cukup berupa array: for (let i = 0; i < n; i++) parent[i] = i;. Sisanya sama persis, dan batasnya n - 1 edge.
Dua kasus kecil ikut beres sendiri. Edge kembar yang menghubungkan pasangan node yang sama ditolak, karena pasangan itu sudah satu kelompok. Graph dengan satu node gak butuh edge apa pun, jadi totalnya 0.
Prim: tumbuh dari satu node
Prim memakai cara lain. Dia mulai dari satu node, misalnya A, lalu tiap langkah mengambil edge termurah yang menyambung pohonnya ke node di luar pohon: A-C 2, lalu C-B 1, lalu B-D 5, lalu D-E 2. Totalnya juga 10. Supaya cepat menemukan edge termurah, Prim biasanya memakai min-heap, struktur yang selalu memberi isi terkecil.
Jadi bedanya: Kruskal mengurutkan semua edge dan memakai union-find, Prim tumbuh dari satu node dengan min-heap. Keduanya greedy (selalu ambil yang termurah saat itu), dan di MST cara greedy ini terbukti selalu benar.
⚠️ Jebakan yang sering ketemu
- MST bukan jalur terpendek. MST meminimalkan total bobot untuk menyambung semua node. Jalur dari A ke E di dalam MST belum tentu jalur terpendek dari A ke E. Itu tugas Dijkstra.
- Edge diambil tanpa cek kelompok. Hasilnya ada siklus, dan totalnya kebesaran.
parent[a] = b. Yang digabung harus ketuanya,parent[ra] = rb. Kalau node-nya langsung, anggota lain di kelompok lama tertinggal.- Bobot yang sama. MST bisa lebih dari satu kalau ada bobot kembar, tapi totalnya selalu sama.
TL;DR: MST menyambung semua V node tanpa siklus dengan total bobot terkecil, dan selalu punya V - 1 edge. Kruskal: urutkan edge dari bobot terkecil (sort((a, b) => a[2] - b[2])), ambil satu per satu, tolak edge yang kedua ujungnya punya ketua find yang sama, gabungkan dengan parent[ra] = rb, berhenti di V - 1 edge. Prim tumbuh dari satu node dengan min-heap. Hasil totalnya sama.
