Minimum Spanning Tree

सबको जोड़ने का सबसे सस्ता तरीका

Minimum Spanning Tree (MST) सभी V nodes को ठीक V-1 edges से जोड़ता है, न्यूनतम कुल weight के साथ, और कोई cycle नहीं। सोचें: शहरों को न्यूनतम लागत पर केबल से जोड़ना।

Kruskal's — edges क्रमबद्ध करें, union-find

सभी edges को weight से क्रमबद्ध करें। एक edge जोड़ें अगर उसके दो सिरे अलग-अलग components में हों (Union-Find से जांचा गया), जिससे cycle से बचा जाता है।

def kruskal(n, edges):
    parent = list(range(n))

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

    mst_weight, count = 0, 0
    for w, u, v in sorted(edges):        # edges as (weight, u, v)
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru] = rv
            mst_weight += w
            count += 1
            if count == n - 1:
                break
    return mst_weight

Prim's — एक node से बढ़ाएँ

किसी भी node से शुरू करें और बार-बार वर्तमान tree से किसी नए node तक जाने वाला सबसे सस्ता edge जोड़ें, एक min-heap के साथ — आकार में Dijkstra जैसा।

import heapq

def prim(n, g, start=0):
    visited = [False] * n
    pq = [(0, start)]
    total = 0
    while pq:
        w, u = heapq.heappop(pq)
        if visited[u]:
            continue
        visited[u] = True
        total += w
        for v, wt in g[u]:
            if not visited[v]:
                heapq.heappush(pq, (wt, v))
    return total

Kruskal बनाम Prim

Kruskal's, O(E log E), sparse graphs पर बेहतर है क्योंकि यह edge-by-edge काम करता है। Prim's, heap के साथ O(E log V), dense graphs पर बेहतर है क्योंकि यह एक tree को node-by-node बढ़ाता है।