Algoritma Kruskal
Terakhir diperbarui
Algoritma Kruskal adalah algoritma untuk membangun minimum spanning tree (MST), yaitu himpunan edge termurah yang menghubungkan setiap node tanpa siklus. Algoritma ini mengurutkan semua edge berdasarkan bobotnya, lalu secara greedy menambahkan edge termurah berikutnya selama edge itu menghubungkan dua node yang belum terhubung. Tekan Putar di atas untuk melihat pohon tumbuh, satu edge aman termurah demi satu edge.
Pengecekan "sudah terhubung?" dilakukan dengan struktur data union-find (disjoint set): sebuah edge dilewati jika kedua ujungnya sudah berada di komponen yang sama, karena menambahkannya akan membentuk siklus. Pengurutan mendominasi biayanya, sehingga totalnya O(E log E). Kruskal unggul pada graf yang renggang.
Kompleksitas waktu dan ruang
| Ukuran | Kompleksitas | Catatan |
|---|---|---|
| Waktu | O(E log E) | Didominasi oleh pengurutan edge |
| Operasi union-find | ≈ O(E α(V)) | Hampir konstan per pengecekan dengan path compression |
| Ruang | O(V + E) | Daftar edge + struktur disjoint set |
| Paling cocok untuk | Graf renggang | Bekerja dari daftar edge global |
Langkah demi langkah
| Langkah | Apa yang terjadi |
|---|---|
| 1 | Urutkan setiap edge berdasarkan bobot, dari kecil ke besar. |
| 2 | Masukkan setiap node ke komponennya sendiri (union-find). |
| 3 | Ambil edge termurah berikutnya. |
| 4 | Jika kedua ujungnya ada di komponen yang berbeda, tambahkan edge itu ke pohon dan gabungkan (union) komponennya. |
| 5 | Jika tidak, lewati (edge itu akan membentuk siklus). |
| 6 | Berhenti begitu pohon punya V − 1 edge. |
Contoh penerapan
Graf dengan node A, B, C, D dan edge A-B(1), B-C(2), A-C(3), C-D(4), B-D(5). Edge yang sudah diurutkan: A-B(1), B-C(2), A-C(3), C-D(4), B-D(5):
| Edge (bobot) | Komponen sebelumnya | Aksi |
|---|---|---|
A-B(1) | {A} {B} {C} {D} | Komponen berbeda: tambahkan ke MST, gabungkan menjadi {A,B}. |
B-C(2) | {A,B} {C} {D} | Komponen berbeda: tambahkan ke MST, gabungkan menjadi {A,B,C}. |
A-C(3) | {A,B,C} {D} | A dan C sudah bersama: lewati (akan membentuk siklus). |
C-D(4) | {A,B,C} {D} | Komponen berbeda: tambahkan ke MST, gabungkan menjadi {A,B,C,D}. |
| Berhenti | {A,B,C,D} | Pohon punya V - 1 = 3 edge. MST = A-B, B-C, C-D, total bobot 7. |
Kapan memakai algoritma Kruskal
| Pakai saat | Hindari saat |
|---|---|
| Grafnya renggang (sedikit edge dibandingkan jumlah node). | Grafnya padat: algoritma Prim dengan heap biasanya lebih cepat. |
| Edge sudah tersedia sebagai daftar global yang bisa kamu urutkan. | Edge hanya tersedia lewat adjacency list yang harus kamu pindai per node. |
| Kamu ingin implementasi sederhana yang didukung union-find. | Kamu butuh pohon yang tumbuh dari satu node awal tertentu. |
| Kamu ingin membangun spanning forest dari graf yang tidak terhubung. | Kamu harus menangani edge yang datang terus-menerus tanpa pengurutan penuh. |
Kode Kruskal's Algorithm
Implementasi Kruskal's Algorithm yang rapi dan siap dijalankan dalam Python, JavaScript, Java, C++, C. Pilih bahasa, salin kodenya, atau buka langsung di Coddy Playground.
Kode Kruskal's Algorithm dalam Python
1def find(parent, x):2 while parent[x] != x:3 parent[x] = parent[parent[x]] # path compression4 x = parent[x]5 return x6
7
8def kruskal(vertices, edges):9 # Take the cheapest edge that does not close a cycle10 parent = {v: v for v in vertices}11 mst, total = [], 012 for w, u, v in sorted(edges):13 root_u, root_v = find(parent, u), find(parent, v)14 if root_u != root_v:15 parent[root_u] = root_v16 mst.append((u, v, w))17 total += w18 return mst, total19
20
21vertices = ["A", "B", "C", "D", "E"]22edges = [23 (4, "A", "B"), (1, "A", "C"), (3, "B", "C"), (2, "B", "D"),24 (5, "C", "D"), (6, "C", "E"), (7, "D", "E"),25]26
27mst, total = kruskal(vertices, edges)28for u, v, w in mst:29 print(f"{u} - {v} (weight {w})")30print("Total MST weight:", total)Kode Kruskal's Algorithm dalam JavaScript
1const nodes = ["A", "B", "C", "D", "E"];2const edges = [3 ["A", "B", 4], ["A", "C", 2], ["B", "C", 1], ["B", "D", 5],4 ["C", "D", 8], ["C", "E", 10], ["D", "E", 2],5];6
7function kruskal() {8 // Union-find with path compression detects cycles cheaply9 const parent = Object.fromEntries(nodes.map((n) => [n, n]));10 const find = (x) => (parent[x] === x ? x : (parent[x] = find(parent[x])));11 const mst = [];12 let total = 0;13 const sorted = [...edges].sort((a, b) => a[2] - b[2]);14 for (const [u, v, w] of sorted) {15 const rootU = find(u);16 const rootV = find(v);17 if (rootU !== rootV) {18 parent[rootU] = rootV;19 mst.push(`${u}-${v} (${w})`);20 total += w;21 }22 }23 return { mst, total };24}25
26const { mst, total } = kruskal();27console.log("MST edges:", mst.join(", "));28console.log("Total weight:", total);Kode Kruskal's Algorithm dalam Java
1import java.util.Arrays;2
3public class Main {4 static int[] parent;5
6 static int find(int x) {7 if (parent[x] != x) parent[x] = find(parent[x]); // path compression8 return parent[x];9 }10
11 static boolean union(int a, int b) {12 int rootA = find(a), rootB = find(b);13 if (rootA == rootB) return false; // would create a cycle14 parent[rootA] = rootB;15 return true;16 }17
18 public static void main(String[] args) {19 int n = 6;20 int[][] edges = {21 {0, 1, 4}, {0, 2, 3}, {1, 2, 1}, {1, 3, 2},22 {2, 3, 4}, {3, 4, 2}, {4, 5, 6}, {2, 5, 7}23 };24 Arrays.sort(edges, (a, b) -> a[2] - b[2]);25 parent = new int[n];26 for (int i = 0; i < n; i++) parent[i] = i;27
28 int total = 0, used = 0;29 for (int[] e : edges) {30 if (union(e[0], e[1])) {31 System.out.println("Take edge " + e[0] + "-" + e[1] + " (weight " + e[2] + ")");32 total += e[2];33 if (++used == n - 1) break;34 }35 }36 System.out.println("MST total weight: " + total);37 }38}Kode Kruskal's Algorithm dalam C++
1#include <algorithm>2#include <iostream>3#include <numeric>4#include <vector>5
6struct Edge {7 int u, v, weight;8};9
10struct DSU {11 std::vector<int> parent;12 explicit DSU(int n) : parent(n) {13 std::iota(parent.begin(), parent.end(), 0);14 }15 int find(int x) {16 if (parent[x] != x) parent[x] = find(parent[x]); // path compression17 return parent[x];18 }19 bool unite(int a, int b) {20 int ra = find(a), rb = find(b);21 if (ra == rb) return false; // would create a cycle22 parent[ra] = rb;23 return true;24 }25};26
27int main() {28 const int n = 5;29 std::vector<Edge> edges = {30 {0, 1, 4}, {0, 2, 2}, {1, 2, 1}, {1, 3, 5},31 {2, 3, 8}, {2, 4, 10}, {3, 4, 3},32 };33 // Greedily take the cheapest edge that connects two components34 std::sort(edges.begin(), edges.end(),35 [](const Edge& a, const Edge& b) { return a.weight < b.weight; });36 DSU dsu(n);37 int total = 0;38 std::cout << "MST edges:\n";39 for (const Edge& e : edges) {40 if (dsu.unite(e.u, e.v)) {41 std::cout << " " << e.u << " - " << e.v42 << " (weight " << e.weight << ")\n";43 total += e.weight;44 }45 }46 std::cout << "Total weight: " << total << "\n";47 return 0;48}Kode Kruskal's Algorithm dalam C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5#define N 56
7typedef struct {8 int u, v, weight;9} Edge;10
11int parent[N];12
13int find(int x) {14 if (parent[x] != x) parent[x] = find(parent[x]); // path compression15 return parent[x];16}17
18bool unite(int a, int b) {19 int ra = find(a), rb = find(b);20 if (ra == rb) return false; // would create a cycle21 parent[ra] = rb;22 return true;23}24
25int cmpEdge(const void* a, const void* b) {26 return ((const Edge*)a)->weight - ((const Edge*)b)->weight;27}28
29int main(void) {30 Edge edges[] = {31 {0, 1, 4}, {0, 2, 2}, {1, 2, 1}, {1, 3, 5},32 {2, 3, 8}, {2, 4, 10}, {3, 4, 3},33 };34 int m = sizeof(edges) / sizeof(edges[0]);35 for (int i = 0; i < N; i++) parent[i] = i;36 // Greedily take the cheapest edge that connects two components37 qsort(edges, m, sizeof(Edge), cmpEdge);38 int total = 0;39 printf("MST edges:\n");40 for (int i = 0; i < m; i++) {41 if (unite(edges[i].u, edges[i].v)) {42 printf(" %d - %d (weight %d)\n",43 edges[i].u, edges[i].v, edges[i].weight);44 total += edges[i].weight;45 }46 }47 printf("Total weight: %d\n", total);48 return 0;49}FAQ Algoritma Kruskal
Apa itu minimum spanning tree?
V - 1 edge untuk V node.Apa perbedaan algoritma Kruskal dan algoritma Prim?
Keduanya membangun minimum spanning tree secara greedy. Kruskal mengurutkan semua edge secara global dan menambahkan edge termurah yang tidak membentuk siklus, dengan bantuan union-find. Prim menumbuhkan satu pohon ke luar dari sebuah node awal, selalu menambahkan edge termurah yang keluar dari pohon. Kruskal cocok untuk graf renggang; Prim (dengan heap) cocok untuk graf padat.
Mengapa algoritma Kruskal memakai union-find?
Sebelum menambahkan sebuah edge, Kruskal harus memeriksa apakah kedua ujungnya sudah terhubung, karena menambahkan edge seperti itu akan membentuk siklus. Union-find (disjoint set) menjawab "apakah keduanya ada di komponen yang sama?" dan menggabungkan komponen dalam waktu amortisasi yang hampir konstan, sehingga algoritmanya tetap efisien.
Kapan sebaiknya memakai algoritma Kruskal, bukan Prim?
O(E log E) murah saat E kecil. Algoritma Prim dengan binary heap atau Fibonacci heap cenderung menang pada graf padat dengan E mendekati V², karena tidak perlu mengurutkan setiap edge di awal.Apakah algoritma Kruskal bekerja pada graf yang tidak terhubung?
V - 1 edge dan justru menghasilkan minimum spanning forest, yaitu satu MST untuk setiap komponen terhubung. Hal ini terjadi secara alami karena union-find tidak pernah menggabungkan node yang tidak punya jalur di antaranya.Apa kesalahan paling umum saat mengimplementasikan algoritma Kruskal?
Tidak memakai path compression dan union by rank pada union-find, sehingga setiap pengecekan keterhubungan berubah dari hampir konstan menjadi hampir linear dan bisa mendominasi waktu berjalannya. Bug lain yang sering terjadi adalah lupa benar-benar menggabungkan dua komponen setelah menambahkan sebuah edge, sehingga edge berikutnya bisa membentuk siklus.
Sumber terkait
Visualisasi lainnya
