Prim 演算法

Prim 演算法是另一種找 MST 的方法，從一個起點開始，每次加入最近的未連接節點。

Vibe Prompt

「幫我用 Prim 演算法找出隨機 20 個點的最小生成樹，用 Matplotlib 畫出 MST。」

import heapq, math, random, matplotlib.pyplot as plt

def prim(points):
    n = len(points)
    visited = [False] * n
    pq = [(0, 0, -1)]  # (cost, node, parent)
    mst = []
    total = 0
    
    while pq:
        cost, node, parent = heapq.heappop(pq)
        if visited[node]:
            continue
        visited[node] = True
        total += cost
        if parent != -1:
            mst.append((parent, node, cost))
        for neighbor in range(n):
            if not visited[neighbor]:
                dx = points[node][0] - points[neighbor][0]
                dy = points[node][1] - points[neighbor][1]
                dist = math.sqrt(dx*dx + dy*dy)
                heapq.heappush(pq, (dist, neighbor, node))
    return mst, total

random.seed(42)
pts = [(random.random()*100, random.random()*100) for _ in range(20)]
mst, total = prim(pts)
print(f"MST 總長: {total:.2f}")