最小生成樹計算機

歡迎使用 最小生成樹計算機，這是一個用於使用 Kruskal 或 Prim 演算法計算加權圖 MST 的互動式工具。無論您是在學習圖論、設計網路基礎設施，還是優化資源分配，本計算機都能為這兩個組合優化領域的基礎演算法提供直觀、分步的探索。

什麼是最小生成樹 (MST)？

連通、無向、加權圖的 最小生成樹 是邊的一個子集，滿足以下條件：

• 連接所有頂點（生成）
• 不包含環路（樹）
• 具有最小的總邊權重

對於具有 V 個頂點的圖，MST 始終恰好有 V - 1 條邊。如果圖是非連通的，結果將是 最小生成森林 (Minimum Spanning Forest) —— 每個連通分量的 MST 集合。

Kruskal 演算法

Kruskal 演算法 是一種基於邊的貪婪演算法，透過按權重遞增順序處理邊來建構 MST。它使用 並查集 (Union-Find) 資料結構來高效地檢測環路。

Kruskal 虛擬碼

Prim 演算法

Prim 演算法 是一種基於頂點的貪婪演算法，從起始頂點開始生長 MST。在每一步中，它都會添加連接樹內頂點與樹外頂點的最便宜邊。

Prim 虛擬碼

Kruskal vs Prim：何時使用哪一個？

如何使用本計算機

1. 定義您的圖形邊： 以 node1, node2, weight 的格式輸入邊，每行一個。MST 運作於無向圖，因此每條邊在兩個方向上都有效。
2. 選擇演算法： 稀疏圖選擇 Kruskal，稠密圖選擇 Prim。兩者都會產生最佳 MST。
3. 設定起始節點（僅限 Prim）： 可選擇指定 Prim 演算法開始的位置。這會影響邊的選擇順序，但不會影響總 MST 權重。
4. 計算 MST： 點擊「尋找 MST」運行演算法。探索互動式視覺化、邊緣表格和逐步追蹤。
5. 查看步驟： 使用「下一步/上一步」按鈕觀看演算法執行過程，並配合即時 Canvas 高亮顯示。

理解結果

MST 邊緣表格

顯示為 MST 選擇的每一條邊（按添加順序）、個別權重以及 MST 總權重。

圖形視覺化

互動式 Canvas 使用顏色編碼顯示您的圖形：

• 綠色節點與邊 = MST 的一部分
• 橘色高亮 = 目前正在檢查
• 灰色元素 = 尚未加入 MST

逐步追蹤

顯示演算法的每個決策：檢查哪條邊、是否接受或拒絕（以及原因），以及 MST 建構的當前狀態。

MST 的現實應用

網路設計

最經典的應用。當以最小的電纜、光纖或管道總長度連接節點（城市、伺服器、電氣設備）時，MST 提供最佳解決方案。電信公司使用基於 MST 的演算法來最小化基礎設施成本。

群集分析

在機器學習和資料科學中，基於 MST 的分群（如單一連結聚類）透過移除 MST 中最長的邊來對資料點進行分組。這可以在不需要預先指定組數的情況下產生自然的分群。

圖像分割

電腦視覺演算法使用 MST 將圖像分割成有意義的區域。畫素是節點，邊權重代表顏色/強度的差異，切割 MST 邊可以分離不同的對象。

近似演算法

MST 為度量旅行推銷員問題 (TSP) 提供了一個 2-近似解。MST 權重是最佳 TSP 路徑的下限，將 MST 邊加倍可得到一個在最佳解 2 倍範圍內的路徑。

電路設計

超大型積體電路 (VLSI) 晶片設計使用 MST（透過 Steiner Tree 變體）來最小化連接電路板組件的總導線長度，從而減少訊號延遲和製造成本。

MST 的關鍵性質

• 切割性質 (Cut Property)： 對於圖的任何切割，橫跨該切割的權重最小的邊必在 MST 中。
• 環性質 (Cycle Property)： 對於圖中的任何環，環中權重最大的邊不在 MST 中（假設權重唯一）。
• 唯一性： 如果所有邊權重均不相同，則 MST 是唯一的。若有重複權重，則可能存在多個具有相同總權重的有效 MST。
• 子圖： MST 是一個具有 V-1 條邊且無環的子圖。

常見問題

什麼是最小生成樹 (MST)？

最小生成樹是連通、無向、加權圖中邊的子集，它將所有頂點連接在一起且總邊權重最小，同時不形成任何環路。對於具有 V 個頂點的圖，MST 恰好有 V-1 條邊。

Kruskal 和 Prim 演算法有什麼區別？

Kruskal 演算法是以邊為基礎的：它按權重對所有邊進行排序，並貪婪地添加不會創建環路的邊，使用並查集 (Union-Find) 資料結構。Prim 演算法是以頂點為基礎的：它從起始節點開始生長 MST，始終添加將樹連接到新頂點的最便宜邊，使用優先隊列。兩者都能產生最佳 MST，但邊的選擇順序可能不同。

什麼時候應該使用 Kruskal 或 Prim 演算法？

Kruskal 通常更適合稀疏圖（相對於節點，邊較少），時間複雜度為 O(E log E)。Prim 更適合稠密圖，使用二元堆積時時間複雜度為 O(E log V)。對於非常稠密的圖，使用 Fibonacci 堆積的 Prim 演算法可以達到 O(E + V log V)。

一個圖可以有多個有效的 MST 嗎？

是的，如果圖中存在權重相等的邊，則可能有多個有效的 MST。不同的 MST 將具有相同的總權重，但可能包含不同的邊。Kruskal 和 Prim 對同一個圖可能產生不同的 MST，但兩者都具有相同的最小總權重。

MST 在現實世界中有哪些應用？

MST 用於網路設計（最小化電纜/光纖長度）、電路板佈局、群集分析、圖像分割、分類學建構、近似 NP-Hard 問題（如旅行推銷員問題 TSP），以及以最低成本建設道路/管道/電力網路。

MST 是否適用於非連通圖？

真正的 MST 需要連通圖。如果圖是非連通的，演算法將產生最小生成森林 (Minimum Spanning Forest) —— 每個連通分量的 MST 集合。本計算機將指示圖何時不完全連通。

其他資源

• 最小生成樹 - 維基百科
• Kruskal 演算法 - 維基百科
• Prim 演算法 - 維基百科