最小生成樹（Minimum Spanning Tree，簡稱 MST）是一組剛好 V−1 條邊的集合，能在加權無向圖中以最小的邊權總和連接每一個已命名的節點，而且不會形成循環，其中 V 是你所列出節點的數量。因此，最小生成樹的「用途」就是任何需要以最便宜的方式連結網路中每個節點、卻不形成迴圈的工作：鋪設連接所有站點且成本最低的纜線、繪製叢集的最小長度骨幹、為演算法課程建立可手動檢查的範例，或將圖形送入下游的近似步驟。此定義與普林斯頓大學 Minimum Spanning Trees 章節中的說法一致，該章節將 MST 描述為在該圖所有生成樹中，邊權總和最小的那棵生成樹。
由於 MST 能將單一純量（總邊權）最小化，因此當連線成本只是一個數字、且唯一限制是每個節點都必須可達時，它與這類問題是完美契合。當你還需要路線、方向，或每對節點間的最小距離時，它就不是合適的工具。Minimum Spanning Tree Solver 可直接在瀏覽器中處理連通的、無向的、單一成本的情況，使用 Kruskal 演算法搭配 disjoint-set union（並查集）來剛好選取 V−1 條邊，並拒絕重複邊、自環（self-loop）以及不連通的輸入。
最小生成樹實際上會在哪裡被使用
最精簡的 MST 實際用途清單，來自於它在教科書網路設計與叢集問題中出現的頻率，但同樣的概念也被重新運用於真實的工程與分析工作。
- 骨幹網路設計。 電話、光纖與公用事業配送的規劃問題，通常會被描述為「以最便宜的纜線路徑連接每個站點，且絕不在方案中放入多餘的迴圈」。只要每對節點的成本是一個數字、且可達性是唯一限制，MST 就能給出答案。
- 單鏈結與歐幾里得叢集。 許多叢集管線會先計算成對距離上的 MST，再切掉最長的邊來形成叢集。二維座標上的幾何 MST 是這種方法的典型輸入，也是聚合式單鏈結叢集（agglomerative single-linkage clustering）背後的結構。
- 路徑問題的近似解。 一個經典結果是利用 MST 在度量空間中為旅行推銷員問題（traveling salesman problem）建立 2-近似（2-approximation）。MST 本身不是路線，但當路線被建立時，其邊會被重新使用，這正是 MST 成為 TSP 近似中標準成分的原因。
- 演算法學習與驗證。 教師與學生會利用小型 MST 問題，在含有相同權重、負權重或零權重的輸入上練習 Kruskal 或 Prim，並用手動追蹤結果與確定性的求解器對照。求解器中經人工稽核的測試案例，能讓你輕鬆將課堂作業與已知答案進行比對。
- 纜線與管線佈局草圖。 對於小型概念性的佈局，例如在房間內連接六個感測器節點的線路，或繪製五條公用管線的路徑，MST 可讓你在加入地理、容量或冗餘條件之前，以同樣的標準比較兩種設計。
貫穿這些用途的共同主題是：只要每條連線的單一純量成本有意義、且「連接到每個節點」是硬性要求，MST 就能適用。一旦你還需要方向、容量或拜訪順序，MST 就不再是合適的工具。
MST 與 TSP、Dijkstra 及有向最小生成樹的比較
搜尋「minimum spanning tree use」時，結果經常會把 MST 與相關的圖論問題混為一談。下表依據每個工具實際解決的根本問題來區分它們，讓你能挑選最符合你工作的那一個。
| 工具 | 根本問題 | 方向性 | 回傳結果 | 典型用途 |
|---|---|---|---|---|
| 最小生成樹 (MST) | 以最小總邊權連接所有節點，且不形成循環 | 無向 | 剛好 V−1 條邊 | 連通網路中最便宜的骨幹 |
| 旅行推銷員 (TSP) | 經過每個節點的最短封閉拜訪順序 | 無向路線 | Hamilton 迴圈 | 配送路線、巡檢迴圈 |
| 最短路徑 (Dijkstra) | 選定一對節點之間，或從單一來源出發的最小成本路徑 | 無向或有向 | 一條路徑 | 點對點導航、延遲規劃 |
| 有向最小生成樹 | 邊遵循選定根節點方向的成本最小分支 | 有向 | V−1 條有向邊 | 從來源節點向外的生成樹 |
如果你面對的是有向圖，MST 就是錯誤的選擇，因為它會忽略方向，求解器可能選到你模型中禁止的邊。如果你需要一條單一最短路徑，MST 並不會產生它，因為 MST 最小化的是總成本，而非每對節點間的成本。如果你需要一個拜訪每個節點一次的封閉迴圈，你需要的是 TSP 模型而非 MST。Minimum Spanning Tree Solver 只針對表中第一列的情況而設計；其他情況請選擇不同的工具。
在瀏覽器中計算 MST
Minimum Spanning Tree Solver 會在已宣告的節點上，以並查集實作 Kruskal 演算法，根據邊權和輸入順序進行穩定排序（stable sort），並且只接受能連接兩個不同元件的邊。若要得到一個確定性的 V−1 邊集合，請依三個步驟準備你的輸入。
- 以逗號分隔列出 2–50 個不重複的節點名稱。 名稱在比對時不分大小寫，因此「RouterA」和「routera」會被視為同一個節點。由於逗號用於分隔欄位，請避免在標籤中使用逗號。
- 使用已宣告的節點名稱，以 from, to, weight 的格式加入每條無向邊。 兩個端點都必須存在於節點清單中，且圖為無向圖；像 A,B 和 B,A 這樣的平行配對會被拒絕而非重複計算。自環對生成樹毫無幫助，因此也會被拒絕。
- 建立 MST、確認連通性與模型假設，然後複製所選的 V−1 條邊。 求解器會在本地端處理所有資料，顯示被選中的邊與精確的總權重，並讓你將結果以純文字複製。若你的圖不連通，頁面會明確顯示「不連通圖」的錯誤訊息，而不會回傳一個誤導性的森林。
若想進一步逐步了解相同的工作流程與更多範例輸入，請參考 how to solve a minimum spanning tree problem。
逐步示範：四個節點與五條邊
考慮四個站點 A、B、C、D，它們之間有下列無向加權連線：
- A — C，權重 1
- B — C，權重 2
- A — D，權重 3
- A — B，權重 4
- C — D，權重 5
Kruskal 會依權重排序這些邊：A–C (1)、B–C (2)、A–D (3)、A–B (4)、C–D (5)。接著它只會在邊連接兩個不同元件時才予以接受：
- 接受 A–C (1)。元件：{A, C}、{B}、{D}。
- 接受 B–C (2)。元件：{A, B, C}、{D}。
- 接受 A–D (3)。元件：{A, B, C, D}。
- 略過 A–B (4)，因為兩個端點已位於同一個元件。
- 略過 C–D (5)，原因相同。
被選中的邊為 A–C (1)、B–C (2) 與 A–D (3)。總權重：1 + 2 + 3 = 6。結果共有 V−1 = 3 條邊，每個節點都可達、不存在循環，而且無法透過替換任何未使用的邊來降低總權重。在 Minimum Spanning Tree Solver 中執行相同的流程，你完全不需要自己手動計算。
Minimum Spanning Tree Solver 的規則與限制
求解器會套用 Kruskal 程序，並強制執行一組小而明確的輸入規則。了解這些規則能讓你的輸出保持確定性，並使被拒絕的邊數為零。
- 節點數與邊數。 瀏覽器端將輸入上限設為 50 個不重複的節點與 500 條不重複的無向邊。在這些上限內執行速度會很順暢；超過則必須先縮減圖規模，工具才會開始運作。
- 權重在正負號上沒有限制。 正數、零與負數權重皆為有效，因為 Kruskal 對有限的實數權重仍然正確。只要不形成循環，負權重邊也會被接受，因此一條有用的負權連結仍會被選中。
- 平手打破方式是穩定的。 當兩條邊具有相同權重時，先輸入的那一條會先被檢查。當存在多個 MST 時，這能讓結果具有確定性，因為求解器不會默默地重新排序平手。
- 標籤的格式要求。 由於逗號用於分隔欄位，標籤中不能包含逗號。每條邊的端點必須與已宣告的節點名稱完全相符，且比對時不分大小寫。
- 被拒絕的形狀。 自環、重複的無向配對，以及同一對節點之間的多重邊會被拒絕，而非默默地互相競爭。如果你需要平行的替代方案，請以額外的節點建模，或預先選取一個有效的權重，並記錄下該決策，避免被捨棄的選項被誤認為是演算法所選擇的結果。
- 不連通的輸入。 若所輸入的圖無法連接到每個節點，求解器會回報「不連通圖」的錯誤，而不會回傳一個森林或誤導性的部分樹。
八個經人工稽核的測試案例涵蓋了兩個節點的邊界情況、三角形、平手權重、零與負權重、五節點循環，以及透過一條昂貴橋樑連接的連通元件。每個案例都會斷言精確的 V−1 邊數與精確的總權重，因此執行通過代表答案已經過這些情境的驗證，而不僅僅是「最便宜的那組邊」。
Minimum Spanning Tree 不適合用於哪些情境
由於搜尋關鍵字強調的是「用途」，列出 Minimum Spanning Tree Solver 因正確理由卻給出錯誤答案的問題會有所幫助。MST 是在整張圖上最小化一個純量總和；一旦你的任務引入了不同的目標、不同的結構或不同的領域，MST 就不再合適。
- 不是路線。 MST 沒有起點、沒有終點，也沒有拜訪順序。如果你需要從某個站點出發，在恰好造訪每個其他站點一次後回到原點，你面對的是 TSP 而不是 MST。請改用 TSP 求解器來處理該問題。
- 不是最短路徑。 MST 會最小化所有被選取邊的權重總和。A 和 B 之間 MST 中最便宜的邊，不一定是整張圖中 A 到 B 最便宜的路徑，而且 MST 可能會保留一條繞了很遠的路徑，因為它從來不需要考慮這件事。如果是針對成對距離，請使用 Dijkstra 這類最短路徑演算法。
- 不考慮方向性。 邊的方向會被忽略。如果你的模型中某條街道是單行道，無向 MST 可能會選到錯誤的方向，或選到你有向圖中根本不存在的邊。當邊的方向很重要時，請使用有向最小生成樹（directed minimum arborescence）工具。
- 不是完整的基礎設施規劃。 真實的纜線、管線或道路設計還需考量地理、備援、容量、可靠性、法規、現有資產以及施工成本。一棵最小純量權重的樹沒有備援，且在運作上可能很脆弱，因此請在據以行動前先驗證模型。
如果你的任務符合上述四種情境中的任何一種，MST 的結果對模型而言在技術上是正確的，但對決策本身沒有幫助。請選擇與問題相符的工具：拜訪順序用 TSP、成對距離用最短路徑，當邊具有方向性時則用有向生成樹（directed-arborescence）方法。
相關閱讀：如何計算圓錐的側表面積：實用方法。