Algoritma Kruskal: Pengertian, Cara Kerja dan Implementasi

Algoritma Kruskal merupakan salah satu algoritma greedy yang paling populer dalam teori graf untuk menemukan Minimum Spanning Tree (MST). Algoritma ini banyak digunakan dalam ilmu komputer, jaringan komputer, sistem transportasi, hingga optimasi jaringan karena mampu menghasilkan jalur dengan total bobot minimum secara efisien.

Bagi mahasiswa informatika, programmer, maupun pelajar yang sedang mempelajari struktur data dan algoritma, memahami cara kerja algoritma Kruskal merupakan hal yang penting. Pada artikel ini, kita akan membahas pengertian algoritma Kruskal, prinsip kerja, langkah-langkah implementasi, kelebihan, kekurangan, serta contoh penerapannya dalam dunia nyata.

Apa itu Algoritma Kruskal?

Algoritma Kruskal adalah algoritma greedy dalam teori graf yang digunakan untuk mencari Minimum Spanning Tree (MST) pada graf berbobot. Algoritma ini diperkenalkan oleh Joseph Kruskal pada tahun 1956 dan menjadi salah satu metode paling populer untuk menyelesaikan masalah optimasi jaringan.

Minimum Spanning Tree (MST) merupakan himpunan sisi yang menghubungkan seluruh simpul dalam graf tanpa membentuk siklus dan memiliki total bobot minimum. Untuk membangun MST, algoritma Kruskal memilih sisi dengan bobot terkecil terlebih dahulu, kemudian menambahkannya ke dalam pohon selama tidak membentuk siklus.

Karena pendekatannya yang sederhana dan efisien, algoritma Kruskal banyak digunakan dalam jaringan komputer, desain jaringan listrik, sistem transportasi, dan berbagai masalah optimasi lainnya.

Baca Juga: Algoritma Adalah: Jenis, Fungsi dan Contoh

Kenapa Algoritma Kruskal Penting?

Algoritma ini penting karena dapat membantu menyelesaikan masalah yang melibatkan jaringan atau hubungan yang memiliki bobot atau biaya terkecil. Contoh penggunaan algoritma ini termasuk dalam bidang jaringan komputer, rute pengiriman dan pemodelan sosial.

Prinsip Kerja Algoritma Kruskal

Prinsip kerja algoritma ini adalah dengan memilih sisi dengan bobot terkecil yang tidak membentuk siklus dalam himpunan solusi yang sedang dibangunah. Algoritma ini bekerja dengan memilih sisi-sisi dengan bobot terkecil secara berurutan dan memeriksa apakah sisi-sisi tersebut membentuk siklus. Jika sisi yang dipilih tidak membentuk siklus, maka sisi tersebut ditambahkan ke dalam himpunan solusi. Langkah ini diulangi hingga semua simpul terhubung dan MST terbentuk.

Baca Juga: Algoritma Greedy: Konsep, Karakteristik dan Contohnya

Cara Kerja Algoritma Kruskal

Berikut adalah langkah-langkah yang dilakukan oleh algoritma ini dalam mencari MST:

1. Mengurutkan semua sisi dalam graf berdasarkan bobotnya.
2. Membuat himpunan subset dari setiap simpul awal.
3. Memilih sisi dengan bobot terkecil dari sisi-sisi yang telah diurutkan.
4. Memeriksa apakah penambahan sisi tersebut membentuk siklus.
5. Jika tidak membentuk siklus, tambahkan sisi tersebut ke dalam himpunan solusi.
6. Ulangi langkah 3-5 hingga semua simpul terhubung dan MST terbentuk.

Dalam langkah pertama, kita mengurutkan semua sisi berdasarkan bobotnya. Langkah ini memerlukan waktu O(E log E), di mana E adalah jumlah sisi dalam graf. Kemudian, dalam langkah kedua, kita membuat himpunan subset dari setiap simpul awal. Setiap simpul awal akan menjadi simpul terisolasi dalam MST yang belum terhubung dengan simpul lain.

Langkah ketiga dan keempat merupakan inti dari algoritma ini. Dalam langkah ketiga, kita memilih sisi dengan bobot terkecil dari sisi-sisi yang telah diurutkan. Kemudian, dalam langkah keempat, kita memeriksa apakah penambahan sisi tersebut akan membentuk siklus atau tidak. Jika tidak membentuk siklus, kita akan menambahkan sisi tersebut ke dalam himpunan solusi.

Langkah kelima dan keenam adalah proses ulang yang dilakukan hingga semua simpul terhubung dan MST terbentuk. Kita akan memilih sisi dengan bobot terkecil yang belum terhubung ke MST pada setiap iterasi dan menambahkannya ke dalam himpunan solusi jika tidak membentuk siklus.

Baca Juga: Algoritma Backtracking: Cara Kerja dan Implementasinya 

Keuntungan dan Kekurangan Algoritma Kruskal

Keuntungan Algoritma Kruskal

Penggunaan algoritma ini memiliki beberapa keuntungan, antara lain:

1. Mudah diimplementasikan dan dipahami.
2. Efisien dalam menemukan MST pada graf dengan jumlah sisi yang besar.
3. Tidak tergantung pada simpul awal yang dipilih.
4. Dapat digunakan pada graf berarah atau tidak berarah.

Kekurangan Algoritma Kruskal

Namun, algoritma ini juga memiliki beberapa kekurangan, di antaranya:

1. Membutuhkan waktu yang relatif lebih lama jika jumlah sisi sangat besar.
2. Tidak efisien jika graf memiliki banyak sisi yang tidak relevan atau tidak diperlukan dalam pembentukan MST.

Penerapan Algoritma Kruskal dalam Dunia Nyata

Algoritma ini memiliki berbagai penerapan dalam dunia nyata. Beberapa contoh penerapannya adalah:

1. Jaringan Komputer: Digunakan dalam penentuan rute terpendek dalam jaringan komputer. Dengan mencari MST pada graf yang mewakili jaringan, kita dapat menemukan jalur yang paling efisien untuk mengirim data antara simpul-simpul dalam jaringan.
2. Rute Pengiriman: Dalam masalah logistik atau pengiriman barang, dapat digunakan untuk mencari jalur pengiriman dengan biaya minimum antara lokasi pengirim dan penerima. Dengan algoritma Kruskal, perusahaan logistik dapat mengoptimalkan rute pengiriman mereka dan mengurangi biaya operasional.
3. Pemodelan Sosial: Dapat diterapkan dalam pemodelan sosial, misalnya dalam analisis jaringan sosial. Dengan menggunakan algoritma Kruskal pada graf yang merepresentasikan koneksi sosial antara individu, kita dapat mengidentifikasi hubungan yang paling penting atau mempengaruhi dalam jaringan sosial tersebut.
4. Desain Jaringan Listrik: Dalam desain jaringan listrik, dapat digunakan untuk mencari jalur penghubung yang efisien antara pembangkit listrik dan konsumen. Dengan meminimalkan biaya kabel atau jarak, algoritma Kruskal membantu meningkatkan efisiensi dan keandalan jaringan listrik.
5. Sistem Transportasi: Dalam perencanaan sistem transportasi, dapat digunakan untuk menentukan jalur transportasi yang paling efisien antara titik asal dan tujuan. Misalnya, algoritma ini dapat membantu memilih rute yang meminimalkan waktu perjalanan atau biaya bahan bakar dalam jaringan jalan atau jaringan transportasi publik.

Baca Juga: Algoritma Dijkstra: Cara Kerja, Contoh Soal dan Implementasi 

Pseudocode Algoritma Kruskal

Kruskal(G):
  Urutkan semua edge berdasarkan bobot

  Untuk setiap edge:
      Jika tidak membentuk siklus:
          Tambahkan edge ke MST

  Kembalikan MST

Implementasi Algoritma Kruskal Python

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []

    def add_edge(self, u, v, w):
        self.graph.append([u, v, w])

    def find(self, parent, i):
        if parent[i] == i:
            return i
        return self.find(parent, parent[i])

    def union(self, parent, rank, x, y):
        xroot = self.find(parent, x)
        yroot = self.find(parent, y)

        if rank[xroot] < rank[yroot]:
            parent[xroot] = yroot
        elif rank[xroot] > rank[yroot]:
            parent[yroot] = xroot
        else:
            parent[yroot] = xroot
            rank[xroot] += 1

    def kruskal(self):
        result = []
        i = 0
        e = 0

        self.graph = sorted(self.graph,
                           key=lambda item: item[2])

        parent = []
        rank = []

        for node in range(self.V):
            parent.append(node)
            rank.append(0)

        while e < self.V - 1:
            u, v, w = self.graph[i]
            i += 1

            x = self.find(parent, u)
            y = self.find(parent, v)

            if x != y:
                e += 1
                result.append([u, v, w])
                self.union(parent, rank, x, y)

        return result
Code language: HTML, XML (xml)

Kesimpulan

Pada pembahasan di atas dapat disimpulkan bahwa Algoritma Kruskal adalah salah satu algoritma greedy yang digunakan untuk mencari Minimum Spanning Tree (MST) pada graf berbobot. Dengan memilih sisi berbobot paling kecil secara bertahap tanpa membentuk siklus, algoritma ini mampu menghasilkan struktur jaringan dengan total biaya minimum secara efisien.

Karena sederhana, mudah diimplementasikan, dan memiliki performa yang baik pada graf dengan jumlah sisi yang besar, algoritma Kruskal banyak digunakan dalam jaringan komputer, sistem transportasi, desain jaringan listrik, hingga berbagai masalah optimasi dalam ilmu komputer. Memahami algoritma ini juga menjadi dasar penting sebelum mempelajari algoritma graf yang lebih kompleks.

Artikel ini merupakan bagian dari seri Algoritma KantinIT.com. Jika artikel ini bermanfaat, jangan lupa bagikan ke media sosial atau ke teman kamu.