Minimum Spanning Tree

Bayangkan sebuah perusahaan telekomunikasi ingin menghubungkan n kota dengan kabel fiber optic sehingga setiap kota terjangkau — namun biaya kabel sangat mahal. Mereka tidak perlu memasang kabel antara setiap pasangan kota; cukup satu set kabel minimum yang menjamin semua kota terhubung. Inilah inti persoalan Minimum Spanning Tree (MST): diberikan graph terhubung berbobot, cari subgraph berbentuk pohon (tree) yang mencakup semua node dengan total bobot minimum. Pada Chapter ini kita akan memahami definisi formal MST, dua properti fundamental (cut dan cycle) yang menjadi dasar algoritma-algoritma MST, lalu melihat ikhtisar algoritma klasik yang akan dibahas detail pada bab-bab berikutnya.

Aturan: Spanning Tree dengan Bobot Minimum #

Diberikan graph tak berarah terhubung berbobot G = (V, E, w), sebuah spanning tree adalah subgraph T = (V, E_T) dengan |E_T| = V - 1 edge dan T terhubung tanpa siklus (yaitu, T adalah pohon yang mencakup semua node). Minimum Spanning Tree adalah spanning tree dengan total bobot minimum di antara semua spanning tree yang mungkin.

Properti penting:

Spanning tree selalu punya V - 1 edge (karena pohon).
Bila graph terputus, tidak ada spanning tree tunggal — hanya spanning forest (satu tree per komponen).
MST tidak unik bila ada edge dengan bobot sama; namun total bobotnya selalu sama.
MST berbobot total minimum — tetapi tidak menjamin diameter minimum atau derajat maksimum minimum (persoalan berbeda).

Mekanisme: Cut Property dan Cycle Property #

Dua properti berikut menjadi dasar semua algoritma MST klasik:

Cut Property #

Sebuah cut adalah partisi V = S ∪ (V - S) dengan S nonempty proper subset. Edge yang menghubungkan S dan V - S disebut crossing edge.

Cut Property: Untuk setiap cut, edge crossing dengan bobot minimum termasuk dalam suatu MST.

Konsekuensi: bila kita memilih cut yang partisinya adalah “node sudah di tree” vs “node belum di tree”, edge berbobot minimum yang menghubungkan kedua himpunan dapat ditambahkan ke MST dengan aman. Inilah inti algoritma Prim.

Cycle Property #

Untuk setiap siklus pada graph, edge dengan bobot maksimum pada siklus tersebut tidak termasuk MST (asumsi bobot edge berbeda-beda; bila ada tie, hanya satu di antaranya yang tidak masuk).

Konsekuensi: algoritma Kruskal mengurutkan semua edge ascending, lalu menambahkan edge satu per satu bila tidak membentuk siklus. Edge-edge berbobot tinggi pada siklus akan di-skip otomatis.

flowchart TD A["Graph G berbobot"] --> B["Spanning Tree T"] B --> C{"T minimum?"} C -- Ya --> D["MST"] C -- Tidak --> E["Suboptimal"] D --> F["|E_T| = V - 1<br/>Total bobot minimum"] F --> G["Tidak unik bila bobot tie"]

Ilustrasi Cut dan Cycle #

Misal graph segi empat 0-1-2-3-0 dengan diagonal:

0-1 bobot 1, 1-2 bobot 2, 2-3 bobot 3, 3-0 bobot 4 (siklus luar).
0-2 bobot 5 (diagonal), 1-3 bobot 6 (diagonal lain).

MST yang benar: {0-1, 1-2, 2-3} total bobot 1+2+3 = 6.

Cut {0} vs {1,2,3}: edge crossing = 0-1 (1), 0-3 (4), 0-2 (5). Minimum = 0-1. Sesuai cut property → 0-1 di MST. ✓
Cycle 0-1-2-3-0: bobot edge pada siklus = 1, 2, 3, 4. Maksimum = 3-0 (4). Sesuai cycle property → 3-0 tidak di MST. ✓

Implementasi: Demo MST Sederhana #

Sebagai pengantar, kita akan membuat demo MST dengan strategi Kruskal yang sederhana. Implementasi penuh dengan DSU akan dibahas detail pada Chapter Kruskal.

cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

// DSU (Disjoint Set Union) sederhana
struct DSU {
    std::vector<int> parent, rank_;
    DSU(int n) : parent(n), rank_(n, 0) {
        std::iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]]; // path compression
            x = parent[x];
        }
        return x;
    }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (rank_[a] < rank_[b]) std::swap(a, b);
        parent[b] = a;
        if (rank_[a] == rank_[b]) rank_[a]++;
        return true;
    }
};

int main() {
    // Graph (undirected, weighted):
    //   0 -- 1
    //   |\  /|
    //   | \/ |
    //   | /\ |
    //   |/  \|
    //   3 -- 2
    int n = 4;
    std::vector<std::tuple<int,int,int>> edges = {
        {0, 1, 1}, {1, 2, 2}, {2, 3, 3}, {3, 0, 4},
        {0, 2, 5}, {1, 3, 6}
    };

    // Demo: bangun MST greedy sederhana (sort by weight, tambah jika tidak siklus)
    std::sort(edges.begin(), edges.end(),
              [](const auto& a, const auto& b) { return std::get<2>(a) < std::get<2>(b); });

    DSU dsu(n);
    int total = 0;
    std::vector<std::pair<int,int>> mst;
    std::cout << "Membangun MST (Kruskal-like demo):\n";
    for (auto [u, v, w] : edges) {
        if (dsu.unite(u, v)) {
            mst.push_back({u, v});
            total += w;
            std::cout << "  tambah edge " << u << "-" << v << " (w=" << w << ")\n";
        } else {
            std::cout << "  skip edge " << u << "-" << v << " (w=" << w << ") - membentuk siklus\n";
        }
    }

    std::cout << "\nTotal bobot MST: " << total << "\n";
    std::cout << "Edge di MST: ";
    for (auto [u, v] : mst) std::cout << "(" << u << "-" << v << ") ";
    std::cout << '\n';

    // Verifikasi: MST harus punya n-1 edge
    std::cout << "\nVerifikasi: |MST| = " << mst.size() << " (seharusnya n-1 = " << n-1 << ")\n";

    // Bandingkan: hitung total bobot semua edge vs MST
    int all = 0;
    for (auto [u, v, w] : edges) all += w;
    std::cout << "Total bobot semua edge: " << all << "\n";
    std::cout << "Hemat: " << (all - total) << " (MST lebih ringan)\n";
    return 0;
}

Output yang Dihasilkan:

text
Membangun MST (Kruskal-like demo):
  tambah edge 0-1 (w=1)
  tambah edge 1-2 (w=2)
  tambah edge 2-3 (w=3)
  skip edge 3-0 (w=4) - membentuk siklus
  skip edge 0-2 (w=5) - membentuk siklus
  skip edge 1-3 (w=6) - membentuk siklus
  skip edge 1-3 (w=6) - membentuk siklus

Total bobot MST: 6
Edge di MST: (0-1) (1-2) (2-3) 

Verifikasi: |MST| = 3 (seharusnya n-1 = 3)
Total bobot semua edge: 21
Hemat: 15 (MST lebih ringan)

Bedah Kode Baris-per-Baris #

std::vector<std::tuple<int,int,int>> edges: list edge (u, v, weight). Kruskal memproses edge sebagai flat list, bukan adjacency list.
std::sort(..., [] (const auto& a, const auto& b) { return std::get<2>(a) < std::get<2>(b); }): urutkan edge ascending by weight. Inilah inti strategi Kruskal: proses edge dari bobot terkecil.
DSU dsu(n): Disjoint Set Union dengan path compression + union by rank. Operasi find dan unite mendekati O(α(n)) amortized — konstan praktis.
if (dsu.unite(u, v)): cek apakah u dan v berada di set berbeda. Bila ya, gabungkan dan tambahkan edge ke MST. Bila tidak (sudah satu set), edge ini akan membentuk siklus → skip sesuai cycle property.
total += w; mst.push_back({u, v});: akumulasi total bobot MST dan simpan edge. Total bobot inilah ukuran keoptimalan MST.
Hasil |MST| = 3: dengan V=4, MST harus punya V-1 = 3 edge. Verifikasi bahwa algoritma menghasilkan jumlah edge yang benar.
Hemat: 15: total bobot semua edge 1+2+3+4+5+6 = 21, MST hanya 1+2+3 = 6. MST menghapus edge berlebihan dengan bobot tertinggi pada siklus.

Ikhtisar Algoritma MST #

Algoritma	Strategi	Kompleksitas	Catatan
Kruskal	Sort edge ascending + DSU	`O(E log E)`	Cycle property. Cocok untuk sparse graph.
Prim	Greedy dari satu node + priority queue	`O((V+E) log V)`	Cut property. Cocok untuk dense graph.
Borůvka	Multi-component expansion	`O(E log V)`	Paralelisasi mudah.
Reverse-delete	Sort descending, hapus bila masih terhubung	`O(E log E)`	Cycle property (inverse).
Chu-Liu/Edmonds	Untuk graph berarah (arborescence)	`O(VE)`	Berbeda jauh dari MST biasa.

Properti Tambahan MST #

Edge unique weights → MST unik: bila semua edge punya bobot berbeda, hanya ada satu MST.
Edge maximum weight bottleneck: MST meminimalkan bobot maksimum edge pada setiap path (minimax path).
Subtree of MST: setiap subtree dari MST juga merupakan MST dari subgraph yang direduksi (optimal substructure).
Sensitivity analysis: edge yang tidak di MST mungkin akan masuk bila bobotnya diturunkan di bawah bobot edge terbesar pada path MST antara dua endpoint.

Aplikasi Nyata MST #

Network design: jaringan kabel fiber, jaringan pipa air, topologi jaringan komputer minimum.
Clustering (single-linkage): MST dari distance graph, potong edge terbesar → cluster.
Image segmentation: MST dari pixel graph, potong pada edge besar.
Approximation algorithms: MST menjadi basis algoritma 2-approximation untuk Travelling Salesman Problem (TSP) metric.
Network reliability: analisis titik kritis jaringan.

Kompleksitas Komparatif #

Aspek	Kruskal	Prim (PQ)	Prim (matrix)
Waktu	`O(E log E)`	`O((V+E) log V)`	`O(V²)`
Ruang	`O(V + E)`	`O(V + E)`	`O(V²)`
Sparse (`E << V²`)	Baik	Baik	Boros
Dense (`E ≈ V²`)	Setara	Setara	Lebih baik
Implementasi	DSU required	Priority queue	Loop sederhana

Ringkasan #

MST adalah spanning tree dengan total bobot minimum — V - 1 edge yang menghubungkan semua node.
Cut property: edge crossing minimum ada di MST — dasar algoritma Prim.
Cycle property: edge maksimum pada siklus tidak di MST — dasar algoritma Kruskal.
Algoritma utama: Kruskal (sort + DSU), Prim (PQ greedy), Borůvka (multi-component).
MST tidak unik bila ada tie bobot; namun total bobot selalu sama.
Aplikasi: network design, clustering, image segmentation, TSP approximation.

Dua bab berikutnya akan membedah secara mendalam Kruskal (sort edge + DSU) dan Prim (priority queue greedy) dengan implementasi C++ lengkap.