最小生成樹計算機

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

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

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

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

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

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

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

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

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

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

Q: MST 是否適用於非連通圖？

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

用 Kruskal 或 Prim 演算法求出加權圖的最小生成樹。圖上會逐步標出選到的邊。

免費使用無需註冊2026年2月更新

最小生成樹計算機立即免費試用 ▼

Embed 最小生成樹計算機 Widget

最小生成樹計算機

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

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

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

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

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

MST 性質

$$|E_{MST}| = |V| - 1 \quad \text{且} \quad W_{MST} = \sum_{e \in E_{MST}} w(e) \text{ 已最小化}$$

Kruskal 演算法

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

Kruskal 虛擬碼

function Kruskal(Graph):
  MST ← 空集合
  按權重對所有邊進行排序（升序）
  為所有頂點初始化並查集

  for each 邊 (u, v, w) 在排序後的邊中:
    if Find(u) ≠ Find(v): // 屬於不同分量
      MST ← MST ∪ {(u, v, w)}
      Union(u, v) // 合併分量

  return MST

Kruskal 時間複雜度

$$O(E \log E) = O(E \log V)$$

Prim 演算法

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

Prim 虛擬碼

function Prim(Graph, start):
  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

Prim 時間複雜度 (二元堆積)

$$O((V + E) \log V)$$

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，通過自然語言問答解決您的數學問題。

最小生成樹計算機

最小生成樹計算機

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

Kruskal 演算法

Kruskal 虛擬碼

Prim 演算法

Prim 虛擬碼

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

如何使用本計算機

理解結果

MST 邊緣表格

圖形視覺化

逐步追蹤

MST 的現實應用

網路設計

群集分析

圖像分割

近似演算法

電路設計

MST 的關鍵性質

常見問題

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

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

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

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

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

MST 是否適用於非連通圖？

其他資源

進階數學計算:

熱門與最新工具:

升級 Pro，一個 ZIP 下載全部檔案