Prim

Kruskal memandang MST dari sudut edge: sort semua, ambil yang tidak membentuk siklus. Algoritma Prim memandang dari sudut node: mulai dari satu node, perluas MST dengan menambahkan edge berbobot minimum yang menghubungkan node-tree ke node non-tree. Strategi ini secara langsung memanfaatkan cut property yang telah kita diskusikan — cut-nya adalah “node di MST” vs “node belum di MST”, dan edge crossing minimum adalah kandidat berikutnya. Dengan priority queue untuk mencari edge minimum dengan cepat, kompleksitas Prim adalah O((V + E) log V). Pada Chapter ini kita akan membedah mekanisme Prim, mengimplementasikannya dengan std::priority_queue, dan membandingkannya dengan Kruskal.

Aturan: Grow Tree dari Sumber #

Diberikan graph tak berarah terhubung berbobot G = (V, E, w) dan node sumber src:

1. Inisialisasi: min_edge[src] = 0, semua min_edge[v] = INF. parent[v] = -1. Push (0, src) ke min-heap.
2. Selama heap tidak kosong:
   • Pop (w, u) dari heap. Bila u sudah di MST, skip (lazy deletion).
   • Tandai u di MST. Tambah w ke total. Bila parent[u] != -1, tambahkan edge (parent[u], u) ke MST.
   • Untuk setiap edge (u, v, weight) ke v yang belum di MST: bila weight < min_edge[v], update min_edge[v] = weight, parent[v] = u, push (weight, v) ke heap.
3. Berhenti saat MST berisi V - 1 node (atau heap kosong = graph terputus).

Mekanisme: Cut Property + Priority Queue #

Setiap langkah, Prim mengambil edge minimum crossing cut {node di MST} | {node belum di MST}. Sesuai cut property, edge ini aman ditambahkan ke MST.

min_edge[v] menyimpan bobot edge terkecil yang diketahui dari MST ke v. Saat node baru u ditambahkan ke MST, semua edge (u, v) diperiksa — bila weight < min_edge[v], v punya kandidat edge yang lebih murah.

Implementasi Prim dengan std::priority_queue #

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

// Prim: return (total_bobot, list_edge_MST)
std::pair<long long, std::vector<std::pair<int,int>>>
prim(int n, const std::vector<std::vector<std::pair<int,int>>>& adj, int src = 0) {
    std::vector<long long> min_edge(n, LLONG_MAX);
    std::vector<int> parent(n, -1);
    std::vector<bool> in_mst(n, false);

    using P = std::pair<long long,int>; // (weight, node)
    std::priority_queue<P, std::vector<P>, std::greater<P>> pq;

    min_edge[src] = 0;
    pq.push({0, src});

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

    while (!pq.empty()) {
        auto [w, u] = pq.top();
        pq.pop();
        if (in_mst[u]) continue; // lazy deletion

        in_mst[u] = true;
        total += w;
        if (parent[u] != -1) {
            mst.push_back({parent[u], u});
        }

        for (auto [v, weight] : adj[u]) {
            if (!in_mst[v] && weight < min_edge[v]) {
                min_edge[v] = weight;
                parent[v] = u;
                pq.push({weight, v});
            }
        }
    }

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

int main() {
    // Graph yang sama dengan Chapter Kruskal (untuk verifikasi):
    //   0 -(7)- 1 -(8)- 2
    //   |       |       |
    //  (5)     (9)     (5)
    //   v       v       v
    //   3 -(15)-4 -(6)- 5
    //   |               |
    //  (6)             (4) -- edge 3-5 (catatan: bobot 6, konsisten dengan Kruskal)
    int n = 6;
    std::vector<std::vector<std::pair<int,int>>> adj(n);
    auto add = [&](int u, int v, int w) {
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    };
    add(0, 1, 7); add(1, 2, 8); add(0, 3, 5); add(1, 4, 9); add(2, 5, 5);
    add(3, 4, 15); add(4, 5, 6); add(3, 5, 6);

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

    std::cout << "Prim MST (mulai dari node 0):\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 << "\nCatatan: total harus sama dengan Kruskal (" << total << ")\n";
    return 0;
}

Output yang Dihasilkan:

Prim MST (mulai dari node 0):
  Total bobot: 29
  Edge MST (mulai dari node 0):
    0 - 3
    3 - 5
    5 - 2
    5 - 4
    0 - 1

Catatan: total harus sama dengan Kruskal (29)

Bedah Kode Baris-per-Baris #

1. std::vector<long long> min_edge(n, LLONG_MAX): bobot edge minimum yang diketahui dari MST ke setiap node. Inisialisasi LLONG_MAX = belum ada kandidat.
2. std::vector<int> parent(n, -1): node induk di MST untuk setiap node. Berguna untuk merekonstruksi edge MST.
3. std::priority_queue<P, std::vector<P>, std::greater<P>> pq: min-heap berisi (weight, node). std::greater membalik urutan default (max-heap) menjadi min-heap.
4. min_edge[src] = 0; pq.push({0, src});: inisialisasi. Node sumber punya bobot 0 ke dirinya sendiri.
5. auto [w, u] = pq.top(); pq.pop();: ambil kandidat edge minimum. Structured binding C++17 mempermudah dekomposisi pair.
6. if (in_mst[u]) continue;: lazy deletion. Karena min_edge[v] bisa di-update beberapa kali, beberapa entri v ada di heap. Skip bila v sudah di MST.
7. in_mst[u] = true; total += w;: tambahkan u ke MST. Bobot w adalah bobot edge minimum yang menghubungkan u ke MST sebelumnya.
8. if (parent[u] != -1) mst.push_back({parent[u], u});: catat edge (parent[u], u) ke MST. Skip untuk node sumber (parent = -1).
9. for (auto [v, weight] : adj[u]): iterasi edge keluar u. Adjacency list menyimpan (tetangga, bobot).
10. if (!in_mst[v] && weight < min_edge[v]): hanya update bila v belum di MST dan bobot edge lebih kecil dari kandidat sebelumnya.
11. min_edge[v] = weight; parent[v] = u; pq.push({weight, v});: perbarui kandidat edge minimum ke v, simpan parent, push ke heap untuk dipertimbangkan di iterasi berikutnya.
12. Hasil total = 29: sama dengan Kruskal! Edge MST: {0-3 (5), 3-5 (6), 5-2 (5), 5-4 (6), 0-1 (7)}. Total = 5+6+5+6+7 = 29. Set edge sama dengan Kruskal, hanya urutan penambahan berbeda.

Trace Step-by-Step #

Kompleksitas #

Komparasi Prim vs Kruskal #

Implementasi Prim Versi O(V²) (Adjacency Matrix) #

Untuk completeness, berikut sketsa versi tanpa priority queue:

long long prim_matrix(int n, const std::vector<std::vector<long long>>& w) {
    std::vector<long long> min_edge(n, LLONG_MAX);
    std::vector<bool> in_mst(n, false);
    min_edge[0] = 0;
    long long total = 0;

    for (int i = 0; i < n; ++i) {
        int u = -1;
        for (int v = 0; v < n; ++v)
            if (!in_mst[v] && (u == -1 || min_edge[v] < min_edge[u]))
                u = v;
        in_mst[u] = true;
        total += min_edge[u];
        for (int v = 0; v < n; ++v)
            if (!in_mst[v] && w[u][v] < min_edge[v])
                min_edge[v] = w[u][v];
    }
    return total;
}

Kompleksitas O(V²) — setiap iterasi memilih node minimum dengan linear scan, lalu update min_edge dengan loop linear.

Variasi #

• Prim multi-source: push beberapa sumber ke heap sekaligus dengan bobot 0. Berguna untuk spanning forest.
• Prim dengan decrease-key: gunakan struktur yang mendukung decrease-key (Fibonacci heap, indexed priority queue). Hindari lazy deletion — O(E + V log V) teoritis.
• Borůvka: varian MST yang memproses semua komponen sekaligus, paralelisasi mudah. Kompleksitas O(E log V).

Aplikasi Nyata #

• Network design: jaringan minimum antar lokasi (telepon, pipa, listrik).
• Image segmentation: graph pixel → MST → potong edge besar → segment.
• Clustering: MST-based clustering (mirip Kruskal, edge terbesar dipotong).
• Real-time navigation: minimum-cost subset jaringan untuk broadcast/multicast tree.

Ringkasan #

• Prim membangun MST dengan strategi greedy: tambah edge minimum crossing cut {tree} | {non-tree}.
• Implementasi dengan std::priority_queue + lazy deletion memberi O((V + E) log V).
• Variabel kunci: min_edge[] (bobot edge minimum ke MST), parent[] (rekonstruksi MST), in_mst[] (penanda).
• Versi O(V²) tanpa PQ lebih cepat untuk adjacency matrix dan V kecil.
• Hasil total bobot sama dengan Kruskal — hanya urutan penambahan edge berbeda.

Bab berikutnya beralih ke topik baru: Strongly Connected Components — bagaimana mengidentifikasi kelompok node yang saling terjangkau pada graph berarah.