在 Day 26～Day 28 中，我們依序介紹了「最小生成樹 (Minimum Spanning Tree, MST)」的概念、Kruskal 與 Prim 兩種經典演算法。今天，我們將不談數學推導與程式碼優化，而是聚焦在 「如何將 MST 應用到現實問題」。

這一篇文章將帶你看見: 演算法不只是考試用的理論題，而是能夠幫助你設計真實世界的解決方案。

回顧: 什麼是最小生成樹 (MST)

給定一個「連通、無向、帶權圖」，MST 的目標是: 找出一棵包含所有節點的「生成樹」，且其所有邊的總權重最小。

生成樹 (Spanning Tree) 意味著:

• 涵蓋所有節點；
• 不形成任何迴圈；
• 若有多種可能，選擇權重總和最小者。

常用演算法有:

• Kruskal: 以邊為導向，利用「並查集 (Union-Find)」防止成環。
• Prim: 以點為導向，從某個節點開始，逐步擴展整棵樹。

MST 的典型應用場景

最小生成樹的應用主要出現在「需要連通所有節點，且成本最小」的場景。以下列出三個經典案例:

網路與通訊設計 (Network Design)

• 問題描述: 假設你要建立一個網路，節點代表伺服器、邊代表電纜連接，邊的權重代表成本（距離、延遲、施工成本等）。你的目標是讓所有伺服器都互聯，並且總成本最小。
• 對應模型
  • 節點: 伺服器、交換機
  • 邊: 纜線或連線
  • 權重: 施工成本或距離
• 解法: 直接套用 MST，即可得到最省成本的網路拓撲。

import heapq

def prim(graph, start=0):
    visited = [False] * len(graph)
    pq = [(0, start, -1)]
    mst = []

    while pq:
        w, u, p = heapq.heappop(pq)
        if visited[u]:
            continue
        visited[u] = True
        if p != -1:
            mst.append((p, u, w))
        for v, w2 in graph[u]:
            if not visited[v]:
                heapq.heappush(pq, (w2, v, u))
    return mst

graph = {
    0: [(1, 10), (2, 6), (3, 5)],
    1: [(0, 10), (3, 15)],
    2: [(0, 6), (3, 4)],
    3: [(0, 5), (1, 15), (2, 4)]
}

mst = prim(graph)
total_cost = sum(w for _, _, w in mst)

print("最小生成樹:", mst)
print("總成本:", total_cost)

• 結果說明: MST 給出最小化總成本的網路結構。
• 這樣的架構在現實中可用於
  • ISP 光纖佈線規劃；
  • 企業區網設計；
  • 雲端機房機架 (Rack) 配線

電力輸送與管線設計 (Utility Distribution)

• 問題描述: 在城市中建構電力輸送系統、水管、天然氣管線等，需要連接所有地點，且希望建設成本最低。
• 對應模型
  • 節點: 建築物、城市、工廠
  • 邊: 管線路徑
  • 權重: 鋪設成本
• 解法: 同樣使用 MST，可求出最短連接網路。若考慮容量或安全因素，MST 可作為初始解，進一步延伸為 Steiner Tree 問題。

資料科學中的聚類分析 (Clustering via MST)

• 問題描述: 在無監督學習中，我們常需要將資料分群。若資料以距離構成圖，可以使用 MST 輔助分群。
• 核心概念
  • 對所有資料點建立完全圖，邊權重為距離
  • 建立 MST
  • 移除最大的 $k-1$ 條邊，得到 $k$ 個群集

import numpy as np
from scipy.spatial.distance import pdist, squareform
from heapq import heappush, heappop

def kruskal_clustering(points, k):
    n = len(points)
    dist_matrix = squareform(pdist(points, metric='euclidean'))

    edges = []
    for i in range(n):
        for j in range(i + 1, n):
            edges.append((dist_matrix[i][j], i, j))
    edges.sort()

    parent = list(range(n))

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

    mst_edges = []
    for w, u, v in edges:
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[rv] = ru
            mst_edges.append((u, v, w))

    # 依照邊權重排序，移除最大的 k-1 條邊
    mst_edges.sort(key=lambda x: x[2], reverse=True)
    for _ in range(k - 1):
        mst_edges.pop(0)

    return mst_edges

# 測試
points = np.array([[0,0], [1,1], [2,2], [8,8], [9,9]])
clusters = kruskal_clustering(points, k=2)
print("MST-based clustering edges:", clusters)

• 結果說明: 透過 MST，可自然地將距離遙遠的兩群分開，是 層次式聚類 (Hierarchical Clustering) 的一種變體。

MST 與其他演算法的關聯

MST 雖然是圖論中的基礎，但它與多種應用都有緊密關聯:

MST 的限制

• 僅適用於無向連通圖: 若圖不連通，需對每個子圖各自構建 MST
• 不能處理容量限制: 若邊有容量或流量限制，需用其他演算法 (如最短路徑或最大流)
• 不保證全局最佳對應需求: 若需求是多目標優化 (例如成本與時間並存)，MST 只能提供單一目標下的最優解

結語

今天，我們將 MST 從理論帶入實務，示範了三種典型應用:

• 網路與通訊設計：最小成本連通；
• 電力與管線佈線：基礎設施規劃；
• 聚類分析：基於距離的分群。

MST 的美，在於它的「結構最簡」與「成本最小」兩種特性兼具。透過它，我們可以在多領域中找到最優結構的解決方案。