Kruskal

Pada Chapter MST kita melihat bahwa cycle property menjadi dasar sebuah algoritma elegan: urutkan semua edge dari bobot terkecil ke terbesar, lalu tambahkan edge ke MST satu per satu — selama tidak membentuk siklus. Inilah algoritma Kruskal, diterbitkan Joseph Kruskal pada 1956. Strategi sederhana ini membutuhkan satu struktur pendukung penting: Disjoint Set Union (DSU) yang mengecek apakah dua endpoint edge sudah berada di komponen yang sama (yang berarti menambahkan edge akan membentuk siklus). Pada Chapter ini kita akan membedah mekanisme Kruskal, mengimplementasikannya dengan DSU ber-path compression + union by rank, dan melihat kenapa kompleksitasnya O(E log E).

Aturan: Tambah Edge Bila Tidak Siklus #

Diberikan graph tak berarah terhubung berbobot G = (V, E, w), algoritma Kruskal:

1. Urutkan semua edge ascending by bobot.
2. Inisialisasi DSU dengan V set singleton (satu set per node).
3. Iterasi edge yang sudah di-sort: untuk setiap edge (u, v, w), bila find(u) != find(v) (u dan v di komponen berbeda), gabungkan u dan v serta tambahkan edge ke MST. Bila sama, skip (akan membentuk siklus).
4. Berhenti saat MST berisi V - 1 edge.

Mekanisme: DSU dengan Path Compression + Union by Rank #

DSU menyimpan setiap node dalam sebuah set (komponen). Operasi utama:

• find(x): cari representatif (root) dari set yang berisi x. Path compression: setiap node di sepanjang path dari x ke root langsung di-point ke root — mempercepat query berikutnya.
• unite(a, b): gabungkan dua set. Union by rank: jadikan root dengan rank lebih kecil menjadi anak dari root dengan rank lebih besar — menjamin pohon tetap pendek.

Kedua optimasi bersama memberi kompleksitas amortized O(α(n)) per operasi, di mana α adalah inverse Ackermann — praktis konstan untuk n realistis.

Implementasi Kruskal dengan DSU #

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

struct DSU {
    std::vector<int> parent, rank_;
    explicit 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]];
            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;
    }
};

// Kruskal: return (total_bobot, list_edge_MST)
std::pair<long long, std::vector<std::pair<int,int>>>
kruskal(int n, std::vector<std::tuple<int,int,int>> edges) {
    std::sort(edges.begin(), edges.end(),
              [](const auto& a, const auto& b) { return std::get<2>(a) < std::get<2>(b); });

    DSU dsu(n);
    long long total = 0;
    std::vector<std::pair<int,int>> mst;
    mst.reserve(n - 1);

    for (auto [u, v, w] : edges) {
        if ((int)mst.size() == n - 1) break; // optimasi: MST lengkap
        if (dsu.unite(u, v)) {
            mst.push_back({u, v});
            total += w;
        }
    }

    if ((int)mst.size() != n - 1) {
        // Graph tidak terhubung: tidak ada MST
        return {-1, {}};
    }
    return {total, mst};
}

int main() {
    // Graph 6 node, edge berbobot:
    //   0 -(7)- 1 -(8)- 2
    //   |       |       |
    //  (5)     (9)     (5)
    //   v       v       v
    //   3 -(15)-4 -(6)- 5
    //   |               |
    //  (6)             (4) -- edge 3-5
    int n = 6;
    std::vector<std::tuple<int,int,int>> edges = {
        {0, 1, 7}, {1, 2, 8}, {0, 3, 5}, {1, 4, 9}, {2, 5, 5},
        {3, 4, 15}, {4, 5, 6}, {3, 5, 6}
    };

    auto [total, mst] = kruskal(n, edges);
    if (total == -1) {
        std::cout << "Graph tidak terhubung - tidak ada MST!\n";
        return 0;
    }

    std::cout << "Kruskal MST:\n";
    std::cout << "  Total bobot: " << total << "\n";
    std::cout << "  Edge MST (urutan penambahan):\n";
    for (auto [u, v] : mst) {
        std::cout << "    " << u << " - " << v << "\n";
    }

    std::cout << "\nEdge di-sort ascending, lalu ditambahkan bila tidak siklus.\n";
    return 0;
}

Output yang Dihasilkan:

Kruskal MST:
  Total bobot: 29
  Edge MST (urutan penambahan):
    0 - 3
    2 - 5
    4 - 5
    3 - 5
    0 - 1

Edge di-sort ascending, lalu ditambahkan bila tidak siklus.

Bedah Kode Baris-per-Baris #

1. std::vector<int> parent, rank_;: dua array DSU. parent[x] = parent node x (atau x sendiri bila root). rank_[x] = perkiraan tinggi subtree.
2. std::iota(parent.begin(), parent.end(), 0): inisialisasi parent[i] = i — setiap node adalah root-nya sendiri (singleton set).
3. int find(int x): iteratif dengan path compression. Loop while (parent[x] != x) naik sampai root. Baris parent[x] = parent[parent[x]] adalah path halving — varian path compression yang lebih cache-friendly daripada full compression rekursif.
4. bool unite(int a, int b): gabungkan dua set. Bila find(a) == find(b) (sudah satu set), return false — edge akan membentuk siklus.
5. if (rank_[a] < rank_[b]) std::swap(a, b);: union by rank. Root dengan rank lebih besar menjadi parent. Ini menjaga pohon tetap pendek.
6. if (rank_[a] == rank_[b]) rank_[a]++: bila kedua root punya rank sama, rank hasil gabungan naik 1.
7. std::sort(edges.begin(), edges.end(), ...): urutkan edge ascending by weight. Kompleksitas O(E log E) — inilah biaya dominan Kruskal.
8. if ((int)mst.size() == n - 1) break;: optimasi early stop. Setelah MST berisi V - 1 edge, edge sisanya pasti membentuk siklus — tidak perlu diproses.
9. if (dsu.unite(u, v)): cek dan gabungkan sekaligus. Bila sukses (komponen berbeda), tambahkan edge ke MST. Bila gagal, skip otomatis.
10. return {-1, {}}: graph tidak terhubung. Hasil: spanning forest, bukan MST tunggal.
11. Hasil total = 29: edge MST adalah {0-3 (5), 2-5 (5), 4-5 (6), 3-5 (6), 0-1 (7)}. Total = 5+5+6+6+7 = 29.

Trace Step-by-Step #

Edge setelah sort ascending: 0-3(5), 2-5(5), 4-5(6), 3-5(6), 0-1(7), 1-2(8), 1-4(9), 3-4(15).

Edge 1-2 (8), 1-4 (9), 3-4 (15) tidak diproses karena MST sudah lengkap. Tanpa optimasi early stop, ketiga edge akan di-cek dan di-skip (membentuk siklus).

Kompleksitas #

Komparasi Kruskal vs Prim #

Variasi dan Penerapan #

• Second-best MST: setelah MST ditemukan, coba hapus satu edge MST, tambah satu edge non-MST terdekat — cari yang menghasilkan total minimum.
• Minimum spanning forest: bila graph tidak terhubung, jalankan Kruskal penuh tanpa early stop → spanning forest dengan satu MST per komponen.
• Dynamic MST: update MST bila ada edge yang berubah bobot. Lebih kompleks; algoritma Frederickson-JáJá.
• Euclidean MST: titik pada bidang, bobot = jarak Euclidean. Bisa dipecahkan dengan Kruskal setelah Delaunay triangulation.

Aplikasi Nyata #

• Network design: jaringan telepon/listrik/air minimum.
• Clustering (single-linkage): bangun MST dari distance matrix, potong edge terbesar k-1 untuk k cluster.
• Image segmentation: graph pixel → MST → potong edge dengan bobot tinggi → segment.
• Approximation TSP: dua kali MST traversal = tur TSP dengan biaya ≤ 2× optimal (metric TSP).
• Phylogenetic tree: MST dari distance matrix antar spesies (pendekatan sederhana).

Ringkasan #

• Kruskal membangun MST dengan strategi sort ascending + DSU cek siklus.
• DSU dengan path compression + union by rank memberi O(α(n)) per operasi.
• Kompleksitas total O(E log E) — didominasi sort.
• Early stop setelah V - 1 edge masuk MST.
• Cocok untuk graph sparse dan input berupa list edge.
• Aplikasi: network design, clustering, image segmentation, TSP approximation.

Bab berikutnya akan membahas Prim — algoritma MST yang menggunakan strategi berbeda: greedy dari satu node dengan priority queue.