最小生成樹計算機
使用 Kruskal's 或 Prim's 演算法計算加權圖的最小生成樹 (MST)。具備互動式圖形視覺化、演算法步驟追蹤以及邊緣選擇動畫功能。
偵測到廣告封鎖，導致我們無法顯示廣告
MiniWebtool 依靠廣告收入免費提供服務。如果這個工具幫到你，歡迎升級 Premium（無廣告 + 更快），或將 MiniWebtool.com 加入允許清單後重新整理頁面。
- 或升級 Premium（無廣告）
- 允許 MiniWebtool.com 顯示廣告，然後重新載入
最小生成樹計算機
歡迎使用 最小生成樹計算機，這是一個用於使用 Kruskal 或 Prim 演算法計算加權圖 MST 的互動式工具。無論您是在學習圖論、設計網絡基礎設施，還是優化資源分配，本計算機都能為這兩個組合優化領域的基礎演算法提供直觀、分步的探索。
什麼是最小生成樹 (MST)？
連通、無向、加權圖的 最小生成樹 是邊的一個子集，滿足以下條件：
- 連接所有頂點（生成）
- 不包含環路（樹）
- 具有最小的總邊權重
對於具有 V 個頂點的圖，MST 始終恰好有 V - 1 條邊。如果圖是非連通的，結果將是 最小生成森林 (Minimum Spanning Forest) —— 每個連通分量的 MST 集合。
Kruskal 演算法
Kruskal 演算法 是一種基於邊的貪婪演算法，透過按權重遞增順序處理邊來建構 MST。它使用 並查集 (Union-Find) 資料結構來高效地檢測環路。
Kruskal 虛擬碼
MST ← 空集合
按權重對所有邊進行排序（升序）
為所有頂點初始化並查集
for each 邊 (u, v, w) 在排序後的邊中:
if Find(u) ≠ Find(v): // 屬於不同分量
MST ← MST ∪ {(u, v, w)}
Union(u, v) // 合併分量
return MST
Prim 演算法
Prim 演算法 是一種基於頂點的貪婪演算法，從起始頂點開始生長 MST。在每一步中，它都會添加連接樹內頂點與樹外頂點的最便宜邊。
Prim 虛擬碼
MST ← 空集合
inMST ← {start}
PQ ← 包含從 start 出發之邊的優先隊列
while PQ 不為空 and |inMST| < |V|:
(w, u, v) ← 從 PQ 中提取最小值
if v ∉ inMST:
MST ← MST ∪ {(u, v, w)}
inMST ← inMST ∪ {v}
將從 v 出發的所有邊加入 PQ
return MST
Kruskal vs Prim：何時使用哪一個？
| 特性 | Kruskal 演算法 | Prim 演算法 |
|---|---|---|
| 方法 | 基於邊（全域排序） | 基於頂點（局部增長） |
| 資料結構 | 並查集 (Union-Find) | 優先隊列 |
| 時間複雜度 | \( O(E \log E) \) | \( O((V + E) \log V) \) |
| 最適用於 | 稀疏圖 | 稠密圖 |
| 非連通圖 | 產生生成森林 | 僅生成起始節點所在的分量 |
| 可並行性 | 較容易並行化 | 本質上是序列化的 |
如何使用本計算機
- 定義您的圖形邊： 以
node1, node2, weight的格式輸入邊，每行一個。MST 運作於無向圖，因此每條邊在兩個方向上都有效。 - 選擇演算法： 稀疏圖選擇 Kruskal，稠密圖選擇 Prim。兩者都會產生最佳 MST。
- 設定起始節點（僅限 Prim）： 可選擇指定 Prim 演算法開始的位置。這會影響邊的選擇順序，但不會影響總 MST 權重。
- 計算 MST： 點擊「尋找 MST」運行演算法。探索互動式視覺化、邊緣表格和逐步追蹤。
- 查看步驟： 使用「下一步/上一步」按鈕觀看演算法執行過程，並配合即時 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 集合。本計算機將指示圖何時不完全連通。
其他資源
引用此內容、頁面或工具為：
"最小生成樹計算機" 於 https://MiniWebtool.com/zh-tw//，來自 MiniWebtool，https://MiniWebtool.com/
由 miniwebtool 團隊製作。最後更新日期：2026年2月19日
您還可以嘗試我們的 AI數學解題器 GPT，通過自然語言問答解決您的數學問題。