Algoritma Kruskal: Pengertian, Cara Kerja, dan Implementasi

Algoritma Kruskal adalah salah satu algoritma dalam teori graf yang digunakan untuk menemukan Minimum Spanning Tree (MST) dari graf berbobot dan tidak berarah.

MST sendiri adalah subgraf yang mencakup semua simpul dalam graf tanpa membentuk siklus, dengan jumlah bobot sisi paling minimum.

Algoritma ini dikenal karena pendekatannya yang berbasis greedy, yakni memilih sisi dengan bobot terkecil terlebih dahulu hingga membentuk MST.

Berikut penjelasan lengkap mengenai Algoritma Kruskal, cara kerjanya, langkah implementasi, dan perbandingannya dengan Algoritma Prim.

Mengenal Algoritma Kruskal

Algoritma Kruskal pertama kali diperkenalkan oleh Joseph Kruskal pada tahun 1956. Metode ini sangat efektif untuk graf yang memiliki jumlah simpul banyak namun sedikit sisi (sparse graph).

Prinsip utama dari algoritma ini adalah memilih sisi-sisi graf dengan bobot terkecil secara bertahap, sambil memastikan tidak ada siklus yang terbentuk.

Struktur data seperti disjoint-set sering digunakan dalam implementasi untuk membantu mendeteksi siklus.

Algoritma Kruskal memiliki kompleksitas waktu O(Elog⁡E)O(E \log E)O(ElogE), di mana EEE adalah jumlah sisi dalam graf. Hal ini disebabkan oleh proses pengurutan sisi berdasarkan bobot.

Cara Kerjanya

Algoritma Kruskal bekerja melalui beberapa langkah utama, yaitu:

1. Urutkan semua sisi berdasarkan bobot: Semua sisi dalam graf diurutkan dari bobot terkecil hingga terbesar.
2. Inisialisasi struktur data untuk mendeteksi siklus: Biasanya, disjoint-set atau union-find digunakan untuk melacak komponen-komponen yang terhubung.
3. Tambahkan sisi ke MST jika tidak membentuk siklus: Iterasi dilakukan pada sisi-sisi yang sudah diurutkan. Jika sisi yang dipilih tidak membentuk siklus, sisi tersebut ditambahkan ke MST.
4. Hentikan jika semua simpul sudah terhubung: Proses berakhir ketika MST terbentuk, yakni mencakup semua simpul dengan jumlah sisi n−1n-1n−1 (di mana nnn adalah jumlah simpul dalam graf).

Langkah Implementasi

Implementasi Algoritma Kruskal dalam kode memerlukan beberapa langkah, yakni:

1. Representasi graf: Gunakan daftar sisi untuk merepresentasikan graf, di mana setiap sisi memiliki pasangan simpul dan bobot.
2. Pengurutan sisi: Gunakan algoritma pengurutan seperti quicksort atau fungsi bawaan untuk mengurutkan sisi berdasarkan bobot.
3. Union-Find: Implementasikan struktur data union-find untuk mendeteksi siklus.
4. Iterasi dan pemilihan sisi: Pilih sisi satu per satu dari daftar yang diurutkan, tambahkan ke MST jika tidak membentuk siklus.

Berikut contoh implementasi dalam Python:

class Edge:
    def __init__(self, u, v, weight):
        self.u = u
        self.v = v
        self.weight = weight
def kruskal(edges, num_nodes):
    edges.sort(key=lambda e: e.weight)  # Urutkan sisi berdasarkan bobot
    parent = list(range(num_nodes))
    rank = [0] * num_nodes
    def find(node):
        if parent[node] != node:
            parent[node] = find(parent[node])
        return parent[node]
    def union(u, v):
        root_u = find(u)
        root_v = find(v)
        if root_u != root_v:
            if rank[root_u] > rank[root_v]:
                parent[root_v] = root_u
            elif rank[root_u] < rank[root_v]:
                parent[root_u] = root_v
            else:
                parent[root_v] = root_u
                rank[root_u] += 1
    mst = []
    for edge in edges:
        if find(edge.u) != find(edge.v):
            mst.append(edge)
            union(edge.u, edge.v)
    return mst

Algoritma Kruskal vs Algoritma Prim

Algoritma Kruskal dan Algoritma Prim adalah dua algoritma populer untuk menemukan Minimum Spanning Tree (MST) dalam graf berbobot.

Meski sama-sama bertujuan untuk memperoleh hasil yang sama, pendekatan dan cara kerja kedua algoritma ini memiliki perbedaan mendasar. Berikut adalah perbandingan antara keduanya:

1. Pendekatan Kerja

• Kruskal:
  • Berbasis greedy dan memilih sisi dengan bobot terkecil dari seluruh graf.
  • Bekerja secara global, tanpa memulai dari simpul tertentu.
• Prim:
  • Juga berbasis greedy, tetapi fokus pada perluasan MST dari simpul yang sudah dipilih.
  • Bekerja secara lokal, dimulai dari satu simpul dan menambahkan sisi-sisi terhubung dengan bobot terkecil.

2. Pemrosesan Graf

• Kruskal:
  • Cocok untuk graf yang jarang (sparse graph), karena hanya mempertimbangkan sisi-sisi bobot terkecil.
  • Representasi graf sering menggunakan daftar sisi (Edge List).
• Prim:
  • Lebih efisien untuk graf padat (dense graph), karena mempertimbangkan semua sisi yang terhubung dengan MST.
  • Representasi graf biasanya menggunakan matriks ketetanggaan (Adjacency Matrix) atau daftar ketetanggaan (Adjacency List).

3. Deteksi Siklus

• Kruskal:
  • Menggunakan struktur data disjoint-set atau union-find untuk memastikan tidak ada siklus yang terbentuk.
• Prim:
  • Tidak memerlukan struktur data khusus untuk deteksi siklus, karena hanya menambahkan sisi yang terhubung dengan simpul yang sudah ada dalam MST.

4. Kompleksitas Waktu

• Kruskal:
  • Kompleksitas utamanya berasal dari pengurutan sisi, yaitu O(Elog⁡E)O(E \log E)O(ElogE), di mana EEE adalah jumlah sisi.
  • Cocok untuk graf dengan jumlah sisi lebih kecil dibandingkan simpul (E<V2E < V^2E<V2).
• Prim:
  • Menggunakan struktur data min-heap (atau priority queue), dengan kompleksitas O(E+Vlog⁡V)O(E + V \log V)O(E+VlogV), di mana VVV adalah jumlah simpul.
  • Lebih efisien untuk graf padat (E≈V2E \approx V^2E≈V2).

5. Contoh Implementasi

• Kruskal: Memilih sisi-sisi berbobot terkecil secara global. Cocok untuk graf terpisah atau yang memiliki banyak komponen.
• Prim: Membutuhkan graf yang terhubung untuk bekerja secara optimal, karena dimulai dari satu simpul tertentu.

Dengan memahami Algoritma Kruskal dan membandingkannya dengan Algoritma Prim, Anda dapat memilih metode yang paling cocok untuk kebutuhan pemrosesan graf berbobot.