Minimum Spanning Tree (MST) adalah sub-graph tree (tanpa siklus, terhubung) yang mencakup semua node dengan total bobot edge minimum.

Analogi: Kamu mau membangun jaringan listrik yang menghubungkan semua kota, dengan total panjang kabel paling pendek. Solusinya adalah MST.

Ciri MST

Untuk graph dengan V node, MST punya:

• Tepat V - 1 edge
• Tidak ada siklus
• Terhubung (dari setiap node bisa sampai ke semua node lain)
• Total bobot minimum di antara semua spanning tree yang mungkin

Ada dua algoritma klasik: Kruskal dan Prim. Keduanya greedy, hasilnya sama (MST valid), tapi pendekatannya berbeda.

Kruskal — Sort Edges + Union-Find

Ide: Urutkan semua edge dari bobot terkecil. Tambahkan satu per satu, skip edge yang akan membuat siklus.

Struktur kunci: Union-Find (Disjoint Set Union) untuk cek siklus dengan cepat.

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
  }
  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // path compression
    }
    return this.parent[x];
  }
  union(a, b) {
    const ra = this.find(a), rb = this.find(b);
    if (ra === rb) return false; // sudah satu komponen → siklus
    if (this.rank[ra] < this.rank[rb]) this.parent[ra] = rb;
    else if (this.rank[ra] > this.rank[rb]) this.parent[rb] = ra;
    else { this.parent[rb] = ra; this.rank[ra]++; }
    return true;
  }
}

function kruskal(n, edges) {
  // edges: [[u, v, w], ...]
  edges.sort((a, b) => a[2] - b[2]);

  const uf = new UnionFind(n);
  const mst = [];
  let totalWeight = 0;

  for (const [u, v, w] of edges) {
    if (uf.union(u, v)) {
      mst.push([u, v, w]);
      totalWeight += w;
      if (mst.length === n - 1) break; // MST lengkap
    }
  }
  return { mst, totalWeight };
}

// 4 node, edges: [u, v, weight]
const edges = [
  [0, 1, 10],
  [0, 2, 6],
  [0, 3, 5],
  [1, 3, 15],
  [2, 3, 4],
];
kruskal(4, edges);
// mst: [[2,3,4], [0,3,5], [0,1,10]], totalWeight: 19

Kompleksitas: O(E log E) untuk sort + O(E α(V)) untuk union-find ≈ O(E log E).

Prim — Grow from Vertex

Ide: Mulai dari satu node. Di setiap langkah, tambahkan edge dengan bobot terkecil yang menghubungkan node di dalam MST dengan node di luar MST.

Struktur kunci: Min-heap (priority queue).

function prim(adj, start = 0) {
  // adj[node] = [[neighbor, weight], ...]
  const inMST = new Set([start]);
  const edges = []; // min-heap: [weight, u, v]

  for (const [v, w] of adj[start]) edges.push([w, start, v]);

  const mst = [];
  let totalWeight = 0;

  while (edges.length > 0 && mst.length < Object.keys(adj).length - 1) {
    edges.sort((a, b) => a[0] - b[0]); // min-heap simulasi
    const [w, u, v] = edges.shift();

    if (inMST.has(v)) continue; // sudah di MST, skip

    inMST.add(v);
    mst.push([u, v, w]);
    totalWeight += w;

    for (const [next, nw] of adj[v]) {
      if (!inMST.has(next)) edges.push([nw, v, next]);
    }
  }
  return { mst, totalWeight };
}

Kompleksitas: O(E log V) dengan min-heap.

Kruskal vs Prim

Kegunaan Nyata

• Network design — kabel telekomunikasi, jaringan listrik, pipa
• Clustering — MST lalu hapus edge terbesar = kluster
• Approximation — TSP approximation dengan MST
• Image segmentation — graph-based segmentation

Fun fact: Kruskal dipublikasikan tahun 1956 (oleh Joseph Kruskal), Prim tahun 1957 (oleh Robert Prim — tapi sebenarnya Vojtěch Jarník sudah menemukan tahun 1930!). Algoritma klasik ini masih dipakai di sistem modern setelah 70+ tahun.

🎭 Analogi sehari-hari: PT PLN mau pasang kabel listrik ke semua kampung. Tujuannya: semua kampung dapet listrik dengan kabel paling sedikit. Solusi = MST. Tidak ada kampung yang skip, tidak ada loop kabel berlebih. Ini contoh klasik MST di dunia nyata.

💡 Kruskal vs Prim mental model:

• Kruskal: "Saya punya semua jalan kabel, urutkan dari termurah, ambil satu per satu kalau gak bikin loop." (greedy by edge)
• Prim: "Saya mulai dari satu kota, perluas ke kota tetangga termurah, ulangi sampai semua kota terhubung." (greedy by vertex)

Hasil sama. Kruskal cocok untuk sparse, Prim untuk dense.

⚠️ Jebakan umum:

• Multiple MST possible kalau ada edge dengan weight sama — algoritma pilih salah satu, semua valid
• Lupa Union-Find optimization di Kruskal = O(VE) bukan O(E log E)
• Gunakan untuk graph disconnected = Kruskal tetap jalan (build forest), Prim macet (perlu start ulang per component)
• Salah konsep MST — bukan shortest path antar 2 node, tapi shortest total edge yang menghubungkan semua node

🎯 MST kapan?

• Network design (kabel telekomunikasi, listrik, pipa air)
• Approximation TSP (Traveling Salesman Problem)
• Clustering (hapus k-1 edge terbesar dari MST = k clusters)
• Image segmentation
• Cycle detection saat building (sambil union, kalau cycle = skip)

🧪 Tebakan cepat: 6 kota, 9 edges. MST punya berapa edges? n-1 = 5. Selalu V-1 untuk MST.

TL;DR: MST = pohon yang sambung semua node dengan total weight minimum. Selalu V-1 edges. Kruskal (sort + UF, bagus sparse), Prim (grow + heap, bagus dense). Greedy works (greedy-choice property).