Algoritma Kruskal adalah metode untuk membangun Minimum Spanning Tree (MST) dari graf berbobot dengan memilih sisi berurutan dari bobot terkecil selama tidak membentuk siklus. Algoritma ini termasuk greedy dan dipakai pada jaringan komunikasi, desain sirkuit, serta masalah optimasi jaringan lain.
Apa Itu Minimum Spanning Tree?
Minimum Spanning Tree dari graf terhubung dan berbobot adalah pohon yang menghubungkan semua simpul dengan total bobot sisi minimum. Pohon ini memiliki tepat V-1 sisi, dengan V adalah jumlah simpul, dan tidak mengandung siklus. Algoritma Kruskal adalah salah satu cara menemukannya, bersama algoritma Prim.
Konsep Dasar Algoritma Kruskal
Algoritma Kruskal mengurutkan semua sisi berdasarkan bobotnya, lalu memilih sisi satu per satu dari yang terkecil. Sisi diambil jika penambahannya tidak menyebabkan siklus pada hutan yang sedang dibangun. Untuk mendeteksi siklus, algoritma ini biasanya memakai struktur data Union-Find (Disjoint Set).
Langkah-langkah Algoritma Kruskal
Berikut langkah menjalankan algoritma Kruskal pada graf berbobot:
- Inisialisasi: Buat himpunan untuk setiap simpul (Union-Find), dan sebuah himpunan kosong untuk menyimpan sisi MST.
- Urutkan sisi: Urutkan semua sisi graf berdasarkan bobot secara menaik.
- Iterasi: Untuk setiap sisi dalam urutan tersebut, periksa apakah kedua simpul ujungnya berada dalam himpunan berbeda. Jika ya, tambahkan sisi ke MST dan gabungkan (union) kedua himpunan. Jika tidak, lewati sisi karena akan membentuk siklus.
- Hentikan: Hentikan proses ketika MST memiliki V-1 sisi atau setelah semua sisi diperiksa.
Contoh Penerapan
Misalkan ada graf dengan 4 simpul (A, B, C, D) dan sisi berbobot: (A-B, 1), (A-C, 3), (B-C, 2), (B-D, 4), (C-D, 5). Mari jalankan algoritma Kruskal:
- Urutkan sisi: (A-B,1), (B-C,2), (A-C,3), (B-D,4), (C-D,5).
- Pilih (A-B,1): tidak ada siklus, tambahkan ke MST. Himpunan: {A,B}, {C}, {D}.
- Pilih (B-C,2): B dan C berbeda himpunan, tambahkan. Himpunan: {A,B,C}, {D}.
- Pilih (A-C,3): A dan C sudah satu himpunan, lewati karena membentuk siklus.
- Pilih (B-D,4): B dan D berbeda, tambahkan. Himpunan: {A,B,C,D}. MST memiliki 3 sisi, selesai.
MST yang terbentuk: (A-B,1), (B-C,2), (B-D,4) dengan total bobot 7.
Implementasi Algoritma Kruskal dalam Python
Contoh implementasi algoritma Kruskal dengan Union-Find di Python:
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
xr, yr = self.find(x), self.find(y)
if xr == yr:
return False
if self.rank[xr] < self.rank[yr]:
self.parent[xr] = yr
elif self.rank[xr] > self.rank[yr]:
self.parent[yr] = xr
else:
self.parent[yr] = xr
self.rank[xr] += 1
return True
def kruskal(vertices, edges):
uf = UnionFind(vertices)
mst = []
edges.sort(key=lambda x: x[2])
for u, v, w in edges:
if uf.union(u, v):
mst.append((u, v, w))
return mst
Fungsi kruskal menerima jumlah simpul dan daftar sisi (u, v, w), mengurutkan sisi, lalu memprosesnya dengan Union-Find. Hasilnya berupa daftar sisi MST.
Analisis Kompleksitas
Kompleksitas waktu algoritma Kruskal didominasi pengurutan sisi, yaitu O(E log E) dengan E jumlah sisi. Operasi Union-Find dengan path compression dan union by rank berjalan hampir konstan per operasi, sehingga totalnya O(E log E) atau O(E log V). Ruang yang dibutuhkan O(V + E) untuk menyimpan graf dan struktur Union-Find.
Kapan Menggunakan Algoritma Kruskal?
Algoritma Kruskal cocok untuk graf jarang (sparse graph) karena pengurutan sisi tidak terlalu membebani. Untuk graf padat, algoritma Prim dengan matriks ketetanggaan bisa lebih efisien. Kruskal juga mudah diimplementasikan dan dipahami, sehingga sering menjadi pilihan pertama dalam pembelajaran MST.
Jika Anda ingin memperdalam algoritma graf lain, panduan seperti Algoritma Bellman-Ford dan Floyd-Warshall dapat menjadi lanjutan. Untuk membangun fondasi, mulailah dengan tips praktis memulai belajar algoritma untuk pemula.
Dalam pengembangan antarmuka, prinsip pemilihan jalur minimum juga dapat diilhami oleh panduan merancang antarmuka dengan pola peta panas yang membantu mengarahkan perhatian pengguna. Jika Anda bekerja dengan animasi web, mengelola antrean animasi jQuery dengan .queue() dan .dequeue() dapat menjaga urutan eksekusi.
Pertanyaan yang Sering Diajukan
Apa perbedaan algoritma Kruskal dan Prim?
Kruskal memilih sisi secara global dari yang terkecil, sedangkan Prim tumbuh dari satu simpul dengan memilih sisi terkecil yang menghubungkan pohon ke simpul luar. Kruskal lebih sederhana untuk graf jarang, Prim lebih baik untuk graf padat.
Apakah algoritma Kruskal selalu menghasilkan MST yang unik?
Tidak selalu. Jika ada beberapa sisi dengan bobot sama, mungkin ada lebih dari satu MST dengan total bobot sama. Algoritma Kruskal akan menghasilkan salah satunya.
Bisakah algoritma Kruskal diterapkan pada graf tidak terhubung?
Jika graf tidak terhubung, algoritma Kruskal menghasilkan hutan spanning minimum (minimum spanning forest), yaitu kumpulan MST untuk setiap komponen terhubung.
Algoritma Kruskal adalah metode greedy untuk membangun MST dengan mengurutkan sisi dan menggunakan Union-Find untuk menghindari siklus. Kompleksitasnya O(E log E), dan implementasinya relatif mudah. Gunakan algoritma ini untuk graf jarang, dan pertimbangkan Prim untuk graf padat.
