Belajar Data Structure - Minimum Spanning Tree (Kruskal & Prim)

#Pendahuluan

Setelah di episode 18 kita memahami shortest path — Dijkstra dan Bellman-Ford — pada episode ini kita mempelajari Minimum Spanning Tree (MST): subset edge dari connected weighted undirected graph yang menghubungkan semua node dengan total bobot minimum, tanpa cycle.

MST bukan hanya konsep teori — ia digunakan dalam desain jaringan (menyambung kota dengan kabel minimum), clustering, dan approximations untuk masalah NP-hard. Dua algoritma utama: Kruskal (edge-centric, greedy) dan Prim (vertex-centric, greedy).

#Konsep Dasar

#Apa Itu MST?

MST dari graph G adalah subtree T yang:

• Menghubungkan semua node di G
• Memiliki total bobot minimum dari semua possible spanning trees
• Tidak ada cycle

#Sifat MST

• Jika semua edge weight unik, MST unik
• Jika ada edge weight duplikat, MST mungkin tidak unik
• MST memiliki tepat V-1 edge (V = jumlah node)
• MST bisa ditemukan dengan greedy approach

#Kruskal's Algorithm

#Konsep

Kruskal memilih edge dengan bobot terkecil terlebih dahulu, asalkan tidak membentuk cycle. Menggunakan Union-Find (Disjoint Set Union) untuk mendeteksi cycle secara efisien.

#Implementasi

Kruskal's algorithm

def kruskal(num_nodes, edges):
    edges.sort(key=lambda x: x[2])
    parent = list(range(num_nodes))
    rank = [0] * num_nodes
 
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
 
    def union(x, y):
        rx, ry = find(x), find(y)
        if rx == ry:
            return False
        if rank[rx] < rank[ry]:
            rx, ry = ry, rx
        parent[ry] = rx
        if rank[rx] == rank[ry]:
            rank[rx] += 1
        return True
 
    mst = []
    for u, v, weight in edges:
        if union(u, v):
            mst.append((u, v, weight))
 
    return mst

#Kompleksitas

• O(E log E) — didominasi oleh sorting edges
• Union-Find operasi hampir O(1) amortized

#Prim's Algorithm

#Konsep

Prim memulai dari satu vertex, lalu terus menambahkan edge terpendek yang menghubungkan tree ke node di luar tree. Menggunakan priority queue.

#Implementasi

Prim's algorithm

import heapq
 
def prim(graph, start=0):
    visited = set()
    mst = []
    pq = [(0, start, -1)]
 
    while pq:
        weight, node, prev = heapq.heappop(pq)
        if node in visited:
            continue
        visited.add(node)
        if prev != -1:
            mst.append((prev, node, weight))
 
        for neighbor, w in graph[node]:
            if neighbor not in visited:
                heapq.heappush(pq, (w, neighbor, node))
 
    return mst

#Kompleksitas

• O((V + E) log V) dengan binary heap
• Lebih baik untuk dense graph (banyak edge)

#Perbandingan Kruskal vs Prim

#Praktik

Uji Kruskal dan Prim

edges = [
    (0, 1, 4), (0, 2, 2), (1, 2, 1),
    (1, 3, 5), (2, 3, 8), (2, 4, 10),
    (3, 4, 2)
]
 
mst_kruskal = kruskal(5, edges)
print("Kruskal MST:", mst_kruskal)
print("Total weight:", sum(w for _, _, w in mst_kruskal))
 
graph = {
    0: [(1, 4), (2, 2)],
    1: [(0, 4), (2, 1), (3, 5)],
    2: [(0, 2), (1, 1), (3, 8), (4, 10)],
    3: [(1, 5), (2, 8), (4, 2)],
    4: [(2, 10), (3, 2)]
}
 
mst_prim = prim(graph, 0)
print("Prim MST:", mst_prim)
print("Total weight:", sum(w for _, _, w in mst_prim))

#Aplikasi

• Desain jaringan: menyambung kota dengan kabel minimum
• Clustering: algoritma clustering berbasis MST
• Approximation TSP: MST sebagai approximated solution untuk traveling salesman
• Network redundancy: mengidentifikasi edge kritis dalam jaringan

#Penutup

Inti yang harus dibawa pulang:

• MST: subset edge minimum yang menghubungkan semua node tanpa cycle.
• Kruskal: sort edges + Union-Find, O(E log E), cocok untuk sparse graph.
• Prim: priority queue, O((V+E) log V), cocok untuk dense graph.
• Keduanya greedy: pilih edge terpendek yang tidak membentuk cycle.
• Aplikasi: desain jaringan, clustering, TSP approximation.

Ini adalah episode terakhir di Fase 4: Graphs. Di episode 20 selanjutnya kita memasuki Fase 5: Struktur Lanjutan & Khusus dengan membahas Union-Find (Disjoint Set Union) — struktur data yang memungkinkan merge dan query set secara hampir O(1). Union-Find adalah komponen kunci dari Kruskal's algorithm yang baru saja kita pelajari!