Kruskal 與 Union-Find

Union-Find 實作

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])  # 路徑壓縮
        return self.parent[x]
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py: return False
        # 按秩合併
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

Kruskal MST

def kruskal(n, edges):
    """
    n: 節點數量
    edges: (u, v, weight)
    """
    edges.sort(key=lambda x: x[2])  # 按權重排序
    uf = UnionFind(n)
    mst = []
    total = 0
    
    for u, v, w in edges:
        if uf.union(u, v):
            mst.append((u, v, w))
            total += w
    
    return mst, total

Vibe Prompt

🔥 詠唱：「請用隨機產生的 50 個城市座標，實作 Kruskal MST 並用 Matplotlib 畫出生成樹。」