Algoritma Prim
Terakhir diperbarui
Algoritma Prim adalah algoritma untuk membangun minimum spanning tree (MST), yaitu himpunan edge termurah yang menghubungkan setiap node tanpa siklus, dengan menumbuhkan satu pohon ke luar dari sebuah node awal. Di setiap langkah, algoritma ini memeriksa setiap edge yang menyeberang dari pohon ke node di luarnya, lalu menambahkan yang termurah. Tekan Putar di atas untuk melihat pohon meluas, selalu mengambil edge berbobot terendah yang mencapai node baru.
Karena selalu memilih edge penyeberang yang minimum, setiap penambahan dijamin aman (pasti menjadi bagian dari suatu MST). Dengan priority queue berbasis binary heap yang diurutkan berdasarkan edge termurah ke setiap node di luar pohon, Prim berjalan dalam O(E log V). Ini berbeda dengan Kruskal, yang mengurutkan semua edge secara global alih-alih menumbuhkan satu pohon yang terhubung.
Kompleksitas waktu dan ruang
| Implementasi | Kompleksitas | Catatan |
|---|---|---|
| Binary heap | O(E log V) | Priority queue berisi edge penyeberang |
| Adjacency matrix | O(V²) | Lebih sederhana; bagus untuk graf padat |
| Ruang | O(V + E) | Keanggotaan pohon + priority queue |
| Paling cocok untuk | Graf padat | Tumbuh dari satu node awal |
Langkah demi langkah
| Langkah | Apa yang terjadi |
|---|---|
| 1 | Mulai pohon dengan satu node mana pun. |
| 2 | Periksa semua edge yang menyeberang dari pohon ke node di luarnya. |
| 3 | Pilih edge penyeberang dengan bobot terkecil. |
| 4 | Tambahkan edge itu beserta node barunya ke pohon. |
| 5 | Ulangi sampai setiap node ada di dalam pohon. |
Contoh penerapan
Membangun MST dari graf 4 node dengan edge A-B=1, A-C=3, B-C=2, B-D=4, C-D=5, dimulai dari A:
| Langkah | Pohon | Edge penyeberang | Edge terpilih |
|---|---|---|---|
| 1 | {A} | A-B=1, A-C=3 | A-B (bobot 1) |
| 2 | {A, B} | A-C=3, B-C=2, B-D=4 | B-C (bobot 2) |
| 3 | {A, B, C} | B-D=4, C-D=5 | B-D (bobot 4) |
| 4 | {A, B, C, D} | tidak ada: semua node sudah di pohon | selesai: bobot MST 1+2+4 = 7 |
Kapan memakai algoritma Prim
| Pakai saat | Hindari saat |
|---|---|
| Kamu butuh minimum spanning tree dari graf berbobot yang terhubung dan tidak berarah. | Grafnya berarah atau kamu butuh jalur terpendek: pakai Dijkstra atau Bellman-Ford. |
Grafnya padat (E mendekati V²); bentuk matriks O(V²) sederhana dan cepat. | Grafnya renggang dan edge-nya sudah terurut atau mudah diurutkan: Kruskal sering lebih sederhana. |
| Kamu ingin pohon tumbuh dari satu wilayah ke luar (misalnya tata letak jaringan yang bertahap). | Grafnya tidak terhubung: Prim hanya mencakup satu komponen, padahal kamu butuh minimum spanning forest. |
| Kamu sudah punya struktur adjacency dan priority queue. | Kamu perlu mendeteksi siklus pada himpunan edge global: union-find (Kruskal) lebih cocok untuk bentuk itu. |
Kode Prim's Algorithm
Implementasi Prim's Algorithm yang rapi dan siap dijalankan dalam Python, JavaScript, Java, C++, C. Pilih bahasa, salin kodenya, atau buka langsung di Coddy Playground.
Kode Prim's Algorithm dalam Python
1import heapq2
3
4def prim(graph, start):5 visited = {start}6 heap = [(w, start, v) for v, w in graph[start]]7 heapq.heapify(heap)8 mst, total = [], 09 while heap and len(visited) < len(graph):10 w, u, v = heapq.heappop(heap)11 if v in visited:12 continue13 visited.add(v)14 mst.append((u, v, w))15 total += w16 # Offer the new node's edges to the frontier17 for neighbor, weight in graph[v]:18 if neighbor not in visited:19 heapq.heappush(heap, (weight, v, neighbor))20 return mst, total21
22
23graph = {24 "A": [("B", 4), ("C", 1)],25 "B": [("A", 4), ("C", 3), ("D", 2)],26 "C": [("A", 1), ("B", 3), ("D", 5)],27 "D": [("B", 2), ("C", 5), ("E", 7)],28 "E": [("D", 7)],29}30
31mst, total = prim(graph, "A")32for u, v, w in mst:33 print(f"{u} - {v} (weight {w})")34print("Total MST weight:", total)Kode Prim's Algorithm dalam JavaScript
1const graph = {2 A: { B: 4, C: 2 },3 B: { A: 4, C: 1, D: 5 },4 C: { A: 2, B: 1, D: 8, E: 10 },5 D: { B: 5, C: 8, E: 2 },6 E: { C: 10, D: 2 },7};8
9function prim(start) {10 const inTree = new Set([start]);11 const mst = [];12 let total = 0;13 while (inTree.size < Object.keys(graph).length) {14 // JS has no built-in heap: scan all crossing edges for the cheapest15 let best = null;16 for (const u of inTree) {17 for (const [v, w] of Object.entries(graph[u])) {18 if (!inTree.has(v) && (best === null || w < best[2])) {19 best = [u, v, w];20 }21 }22 }23 const [u, v, w] = best;24 inTree.add(v);25 mst.push(`${u}-${v} (${w})`);26 total += w;27 }28 return { mst, total };29}30
31const { mst, total } = prim("A");32console.log("MST edges:", mst.join(", "));33console.log("Total weight:", total);Kode Prim's Algorithm dalam Java
1import java.util.ArrayList;2import java.util.List;3import java.util.PriorityQueue;4
5public class Main {6 public static void main(String[] args) {7 int n = 6;8 List<List<int[]>> adj = new ArrayList<>();9 for (int i = 0; i < n; i++) adj.add(new ArrayList<>());10 int[][] edges = {11 {0, 1, 4}, {0, 2, 3}, {1, 2, 1}, {1, 3, 2},12 {2, 3, 4}, {3, 4, 2}, {4, 5, 6}, {2, 5, 7}13 };14 for (int[] e : edges) {15 adj.get(e[0]).add(new int[]{e[1], e[2]});16 adj.get(e[1]).add(new int[]{e[0], e[2]});17 }18
19 boolean[] inMst = new boolean[n];20 // Always grow the tree along the cheapest crossing edge21 PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);22 pq.add(new int[]{0, 0}); // {node, edge weight}23 int total = 0, taken = 0;24 while (!pq.isEmpty() && taken < n) {25 int[] cur = pq.poll();26 if (inMst[cur[0]]) continue;27 inMst[cur[0]] = true;28 total += cur[1];29 taken++;30 for (int[] edge : adj.get(cur[0])) {31 if (!inMst[edge[0]]) pq.add(edge);32 }33 }34 System.out.println("MST nodes reached: " + taken);35 System.out.println("MST total weight: " + total);36 }37}Kode Prim's Algorithm dalam C++
1#include <iostream>2#include <queue>3#include <vector>4
5int main() {6 // Undirected weighted graph: adj[u] = {(neighbor, weight), ...}7 std::vector<std::vector<std::pair<int, int>>> adj = {8 {{1, 2}, {3, 6}}, // 09 {{0, 2}, {2, 3}, {3, 8}, {4, 5}}, // 110 {{1, 3}, {4, 7}}, // 211 {{0, 6}, {1, 8}}, // 312 {{1, 5}, {2, 7}}, // 413 };14 int n = static_cast<int>(adj.size());15 std::vector<bool> inMST(n, false);16 using State = std::pair<int, int>; // (edge weight, node)17 std::priority_queue<State, std::vector<State>, std::greater<State>> pq;18 pq.push({0, 0});19 int total = 0, picked = 0;20 // Always grow the tree along the cheapest crossing edge21 while (!pq.empty() && picked < n) {22 auto [w, u] = pq.top();23 pq.pop();24 if (inMST[u]) continue;25 inMST[u] = true;26 total += w;27 ++picked;28 std::cout << "Add node " << u << " (edge weight " << w << ")\n";29 for (auto [v, weight] : adj[u]) {30 if (!inMST[v]) pq.push({weight, v});31 }32 }33 std::cout << "MST total weight: " << total << "\n";34 return 0;35}Kode Prim's Algorithm dalam C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 55#define INF 10000000006
7int main(void) {8 // Undirected weighted graph: w[u][v] = 0 means no edge9 int w[N][N] = {10 {0, 2, 0, 6, 0},11 {2, 0, 3, 8, 5},12 {0, 3, 0, 0, 7},13 {6, 8, 0, 0, 0},14 {0, 5, 7, 0, 0},15 };16 int key[N], parent[N];17 bool inMST[N] = {false};18 for (int v = 0; v < N; v++) {19 key[v] = INF;20 parent[v] = -1;21 }22 key[0] = 0;23 int total = 0;24 // O(V^2) scan for the cheapest crossing edge (no heap needed here)25 for (int iter = 0; iter < N; iter++) {26 int u = -1;27 for (int v = 0; v < N; v++) {28 if (!inMST[v] && (u == -1 || key[v] < key[u])) u = v;29 }30 inMST[u] = true;31 total += key[u];32 if (parent[u] != -1) {33 printf("Add edge %d - %d (weight %d)\n", parent[u], u, key[u]);34 }35 for (int v = 0; v < N; v++) {36 if (w[u][v] > 0 && !inMST[v] && w[u][v] < key[v]) {37 key[v] = w[u][v];38 parent[v] = u;39 }40 }41 }42 printf("MST total weight: %d\n", total);43 return 0;44}FAQ Algoritma Prim
Berapa kompleksitas waktu algoritma Prim?
O(E log V). Versi adjacency matrix yang lebih sederhana, yang memindai edge penyeberang minimum di setiap langkah, bernilai O(V²) dan bisa lebih cepat pada graf padat. Keduanya memakai ruang O(V + E).Apa perbedaan algoritma Prim dan algoritma Kruskal?
Keduanya mencari minimum spanning tree secara greedy. Prim menumbuhkan satu pohon yang terhubung dari sebuah node awal, berulang kali menambahkan edge termurah yang keluar dari pohon (memakai priority queue). Kruskal mempertimbangkan semua edge yang diurutkan berdasarkan bobot dan menambahkan yang termurah yang tidak membentuk siklus (memakai union-find). Prim sering dipilih untuk graf padat, Kruskal untuk graf renggang.
Apakah algoritma Prim selalu menemukan MST yang optimal?
Ya. Di setiap langkah, edge termurah yang menyeberangi pohon saat ini aman untuk ditambahkan, karena edge itu termasuk dalam suatu minimum spanning tree (cut property). Menambahkan edge aman berulang kali menghasilkan minimum spanning tree yang sebenarnya, asalkan grafnya terhubung.
Kapan sebaiknya memakai algoritma Prim, bukan Kruskal?
O(V²) miliknya tidak perlu mengurutkan semua E edge dan menumbuhkan satu pohon dari sebuah node awal. Kruskal unggul pada graf renggang, di mana mengurutkan daftar edge itu murah dan union-find menjaga pengecekan siklus tetap cepat. Keduanya menghasilkan MST yang benar, jadi pilihannya terutama bergantung pada kepadatan edge dan struktur data yang sudah kamu punya.Apakah node awal memengaruhi MST yang dihasilkan?
Tidak. Total bobot MST selalu sama dari node mana pun kamu mulai, karena bobot minimum spanning tree pada graf yang terhubung itu unik. Edge yang terpilih hanya bisa berbeda jika beberapa edge punya bobot yang sama dan ada lebih dari satu MST. Selain kasus itu, Prim menghasilkan pohon yang persis sama apa pun node awalnya.
Bisakah algoritma Prim menangani graf yang tidak terhubung?
Tidak secara langsung. Prim menumbuhkan satu pohon, jadi algoritma ini hanya mencakup komponen terhubung yang berisi node awal dan membiarkan sisanya tidak tersentuh. Untuk mencakup setiap komponen, kamu perlu menjalankan Prim berulang kali dari node yang belum dikunjungi, sehingga menghasilkan minimum spanning forest, bukan satu pohon.
Sumber terkait
Visualisasi lainnya
