Penjelasan minimum spanning tree: algoritma Kruskal dan Prim

Masalah yang diselesaikan minimum spanning tree

Misalkan Anda harus menghubungkan beberapa gedung dengan kabel, beberapa kota dengan jalan, atau beberapa server dengan tautan jaringan, dan setiap sambungan yang mungkin punya biaya. Anda ingin setiap tempat terhubung (langsung maupun tidak langsung) dengan total biaya terendah. Sambungan tambahan yang membentuk lingkaran tidak pernah diperlukan, sehingga jawabannya berupa pohon: V node yang dihubungkan oleh tepat V − 1 edge. Pohon itulah minimum spanning tree.

MST bukan shortest-path tree. MST meminimalkan total bobot semua edge, bukan jarak dari satu node awal ke node lain.

Mengapa pilihan greedy berhasil: cut property

Bagi node menjadi dua kelompok mana pun. Dari edge yang menyeberang antar kelompok, edge teringan termasuk dalam suatu minimum spanning tree. Kedua algoritma bertumpu pada fakta ini:

Jika semua bobot edge berbeda, MST bersifat unik, sehingga kedua algoritma menghasilkan pohon yang sama. Dengan bobot yang sama, bisa ada beberapa MST dengan total yang sama.

Contoh langkah demi langkah

Graf tak berarah dengan 5 node dan edge A–B 4, A–C 3, B–C 1, B–D 2, C–D 4, D–E 2, C–E 5.

Algoritma Kruskal, edge diurutkan berdasarkan bobot:

Kompleksitas waktu dan ruang

Algoritma

Waktu

def kruskal(nodes, edges):
    parent = {n: n for n in nodes}

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]   # path halving
            x = parent[x]
        return x

    tree, total = [], 0
    for w, u, v in sorted(edges):
        ru, rv = find(u), find(v)
        if ru != rv:                          # different components: no cycle
            parent[ru] = rv
            tree.append((u, v, w))
            total += w
    return tree, total

nodes = "ABCDE"
edges = [(4, "A", "B"), (3, "A", "C"), (1, "B", "C"), (2, "B", "D"),
         (4, "C", "D"), (2, "D", "E"), (5, "C", "E")]
print(kruskal(nodes, edges))
# ([('B', 'C', 1), ('B', 'D', 2), ('D', 'E', 2), ('A', 'C', 3)], 8)

Ruang

Terbaik untuk

Prim's algorithm needs an adjacency list. It uses lazy deletion like Dijkstra's algorithm: push every edge that leaves the tree, and skip edges whose far end is already in the tree.

import heapq
from collections import defaultdict

def prim(edges, start):
    graph = defaultdict(list)
    for w, u, v in edges:
        graph[u].append((w, u, v))
        graph[v].append((w, v, u))
    in_tree = {start}
    heap = list(graph[start])
    heapq.heapify(heap)
    tree, total = [], 0
    while heap:
        w, u, v = heapq.heappop(heap)
        if v in in_tree:
            continue
        in_tree.add(v)
        tree.append((u, v, w))
        total += w
        for edge in graph[v]:
            if edge[2] not in in_tree:
                heapq.heappush(heap, edge)
    return tree, total

print(prim(edges, "A"))
# ([('A', 'C', 3), ('C', 'B', 1), ('B', 'D', 2), ('D', 'E', 2)], 8)

Time and space complexity

Algoritma Borůvka, dari 1926, menambahkan edge termurah dari setiap komponen sekaligus dan mudah diparalelkan.

Bug umum pada Kruskal adalah memeriksa siklus dengan himpunan node yang dikunjungi, bukan union-find. Dua node bisa sama-sama sudah dikunjungi tetapi berada di komponen berbeda, sehingga edge di antara keduanya tetap dibutuhkan. Hanya "komponen yang sama" yang berarti "akan membentuk siklus".

• Kapan memakainya dan penggunaannya di dunia nyata
• Desain jaringan: cara termurah menghubungkan lokasi dengan kabel, pipa, atau jalan, ketika tata letak terhubung apa pun dapat diterima.
• Algoritma aproksimasi: MST menghasilkan tur yang panjangnya paling banyak dua kali panjang optimal untuk metric traveling salesman problem.
• Clustering dan segmentasi gambar dengan memotong edge terberat MST.
• Soal wawancara: min cost to connect all points, connecting cities with minimum cost, optimize water distribution in a village.

Kruskal memproses semua edge secara global dari teringan ke terberat dan menggabungkan komponen dengan union-find. Prim menumbuhkan satu pohon dari satu node dengan priority queue. Keduanya menemukan minimum spanning tree.

• Apakah minimum spanning tree itu unik?
• Unik bila semua bobot edge berbeda. Dengan bobot yang sama, bisa ada beberapa pohon dengan total bobot minimum yang sama.
• Apakah minimum spanning tree sama dengan shortest path tree?
• Tidak. MST meminimalkan jumlah semua edge-nya, sedangkan shortest path tree, seperti yang dihasilkan algoritma Dijkstra, meminimalkan jarak dari satu sumber ke setiap node. Kedua pohon itu sering berbeda.