Belajar Algoritm - Union-Find & Kruskal's MST

#Pendahuluan

Setelah di episode 19 kita membahas shortest path berbobot, pada episode ini kita membahas Minimum Spanning Tree (MST) — subset edge yang menghubungkan semua vertex dengan total bobot minimum tanpa siklik. Kita fokus pada Kruskal's algorithm yang menggunakan Union-Find — struktur data elegan yang mendukung operasi near-constant time.

Union-Find dan Kruskal adalah kombinasi powerful: Union-Find memungkinkan Kruskal memeriksa siklik secara efisien, menjadikan MST bisa diselesaikan dalam O(E log E) — sebagian besar waktu dihabiskan untuk mengurutkan edge.

#Union-Find (Disjoint Set Union)

Union-Find mendukung dua operasi:

1. Find(x): temukan "representative" (root) dari set yang berisi x.
2. Union(x, y): gabungkan set yang berisi x dan y.

#Implementasi Dasar

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])  # path compression
        return self.parent[x]
    
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False  # sudah satu set
        # Union by rank
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
        return True

#Path Compression & Union by Rank

Dua optimasi kunci yang menjadikan operasi near-constant:

• Path compression: saat find(x), langsung hubungkan x ke root — flatten tree.
• Union by rank: selalu attachment tree lebih pendek ke tree lebih tinggi — jaga tree tetap flat.

Tanpa optimasi: O(n) per operasi. Dengan kedua optimasi: O(α(n)) per operasi, di mana α adalah inverse Ackermann function — hampir konstanta (maksimal 4 untuk input praktis).

#Kruskal's Algorithm

Kruskal membangun MST dengan greedy: urutkan semua edge berdasarkan bobot, lalu tambahkan edge terkecil yang tidak membentuk siklik (dicek dengan Union-Find).

def kruskal_mst(edges, n):
    """edges: [(weight, u, v)]"""
    edges.sort()  # urutkan berdasarkan bobot
    uf = UnionFind(n)
    mst = []
    total_weight = 0
    
    for weight, u, v in edges:
        if uf.union(u, v):  # tidak siklik
            mst.append((u, v, weight))
            total_weight += weight
            if len(mst) == n - 1:
                break  # MST punya n-1 edge
    
    return mst, total_weight

#Mengapa Kruskal Works?

Greedy choice property: edge terkecil yang tidak membentuk siklik pasti ada di MST. Jika tidak, menggantinya dengan edge ini akan menghasilkan MST yang lebih ringan — kontradiksi.

#Kompleksitas

#Kruskal vs Prim

Prim adalah alternatif MST: mulai dari satu vertex, terus tambahkan edge terkecil yang menghubungkan tree ke vertex di luar tree (seperti Dijkstra tetapi untuk MST).

#Praktik

Implementasi Kruskal untuk MST pada road network sederhana (5-10 kota). Cetak MST edges dan total weight. Bandingkan hasil dengan Prim. Verifikasi bahwa MST menghubungkan semua vertex dengan n-1 edge dan total weight minimum.

#Penutup

Pada episode 20 ini, kalian telah memahami:

• Union-Find: find + union dengan path compression & union by rank → O(α(n)) amortized.
• Kruskal's MST: sort edges, greedy tambahkan yang tidak siklik → O(E log E).
• Greedy works: edge terkecil tanpa siklik pasti ada di MST (bukti greedy choice property).
• Prim vs Kruskal: Prim untuk dense, Kruskal untuk sparse — keduanya menghasilkan MST optimal.

Di episode 21 selanjutnya kita akan membahas Network Flow (Pengenalan) — flow network, max-flow min-cut theorem, dan Edmonds-Karp algorithm. Sampai jumpa di episode 21!