一個連通、無向、帶權重圖形的最小生成樹（MST），是指一組 V−1 條邊的集合——其中 V 為節點數——它連接了每一個節點而不形成任何迴圈，並且具有所有邊權重總和的最小可能值。求解最小生成樹問題就是找出那組最佳邊集合。經典且確定性的做法是 Kruskal 演算法，它會將每一條邊依權重由輕到重排序，然後依序走訪列表，只有當某條邊的兩個端點目前屬於不同的連通元件時才加入該邊；若兩端點已屬於同一元件則跳過，因為加入會形成迴圈。並查集（disjoint-set union）資料結構能有效追蹤各連通元件。一旦恰好接受了 V−1 條邊，便得到最小生成樹。當存在多組同樣最小的生成樹時，依輸入順序進行確定性的平手決勝，便能挑出唯一且有效的解答。最小生成樹求解器在瀏覽器中執行此程序，驗證每一條輸入規則，並回傳可複製的邊列表與總權重。
最小生成樹問題究竟是什麼
最小生成樹問題是圖論上的一個組合最佳化問題。圖形（graph）是由節點（也稱為頂點）透過邊相連所組成的集合。在帶權重的圖形中，每條邊都帶有一個數值——可以是成本、長度、容量，或是模型建立者想要最小化的任何純量標籤。圖形必須是連通的，意即任兩個節點之間至少存在一條路徑，且邊是無向的，代表邊在兩個方向上的作用相同。
此類圖形的一個生成樹（spanning tree）是指一組邊的子集合，能觸及每一個節點（生成）、不包含迴圈（即為樹），且恰好包含 V−1 條邊，其中 V 為節點數。最小生成樹是指邊權重總和盡可能最小的生成樹。最小生成樹僅會最小化所輸入的總權重；它並不表示任何單一邊是其兩端點之間的最短路徑，也沒有描述拜訪順序。普林斯頓大學的最小生成樹演算法課程同時記載了定義與 Kruskal 程序，本文中的求解器亦遵循該規格。
Kruskal 演算法如何建構生成樹
Kruskal 演算法是標準的貪婪法，也是本工具所採用的方法。此程序相當直覺，足以在小型案例上手動驗證：
- 將每個節點名稱標準化，使大小寫差異（例如 A 與 a）不會被視為不同的節點。
- 驗證邊：拒絕自環（self-loop）、拒絕重複的無向配對（A,B 與 B,A 為同一條邊），並要求每個端點皆為已宣告的節點。
- 將剩餘邊以權重進行穩定排序，並以原始輸入順序作為平手決勝依據。當存在多個最小生成樹時，這個確定性的步驟能讓單一有效的最佳解具有可重現性。
- 初始化並查集（union-find）結構，使每個節點一開始都獨立處於自己的元件中。
- 走訪已排序的列表。針對每一條邊，檢查其兩個端點是否位於不同的元件中。若是，則將該邊加入樹中，並合併兩個元件。若否，則跳過該邊，因為它會形成迴圈。
- 當已接受 V−1 條邊時停止。若列表用盡前仍未接受 V−1 條邊，表示圖形不連通，不存在生成樹。
普林斯頓的KruskalMST 參考實作完全遵循此順序，本工具的行為亦與該公開原始碼一致。
使用本工具求解最小生成樹問題
最小生成樹求解器在瀏覽器中執行上述步驟，因此資料不會離開此頁面。使用方式如下：
- 開啟最小生成樹求解器，在節點欄位中以逗號分隔列出 2 到 50 個不重複的節點名稱。節點名稱在大小寫不敏感下必須唯一，因此 Hub, hub 會被視為同一個節點並觸發驗證錯誤。
- 將每條無向邊單獨列於一行，格式為 from, to, weight（起點, 終點, 權重）。兩個端點皆必須完全符合已宣告的節點，權重則為有限的實數，可為正數、零或負數。
- 點擊建構按鈕。求解器會標準化名稱、拒絕自環與重複的 A,B / B,A 配對、排序剩餘邊，並執行 union-find 迴圈。
- 確認連通性檢查通過。若邊無法觸及每個節點，頁面會明確顯示「不連通」錯誤，而非回傳一個誤導性的局部森林。
- 從結果面板以純文字格式複製所選出的 V−1 條邊。每一列顯示其端點與權重，面板同時會回報總權重。
實作範例：一個四節點圖形
為了實際觀察程序產出解答，考慮四個節點——A、B、C、D——由五條帶權重的邊連接：
| from（起點） | to（終點） | weight（權重） |
|---|---|---|
| A | B | 1 |
| A | C | 4 |
| B | C | 3 |
| B | D | 2 |
| C | D | 5 |
依權重排序（平手時保留輸入順序）：(A,B,1)、(B,D,2)、(B,C,3)、(A,C,4)、(C,D,5)。
以 union-find 走訪列表：
- (A,B,1) — A 與 B 位於不同元件，接受。目前總和：1。元件：{A,B}、{C}、{D}。
- (B,D,2) — B 與 D 位於不同元件，接受。目前總和：3。元件：{A,B,D}、{C}。
- (B,C,3) — B 與 C 位於不同元件，接受。目前總和：6。元件：{A,B,C,D}。
- (A,C,4) — A 與 C 目前位於同一元件，跳過（會形成迴圈）。
- (C,D,5) — C 與 D 位於同一元件，跳過。
接受了三條邊——在 V = 4 時恰好為 V−1 = 3——因此結果即為一最小生成樹：{(A,B,1)、(B,D,2)、(B,C,3)}，總權重為 6。將這些列貼入求解器中即可驗證。
最小生成樹求解器不適用的情境
最小生成樹既不是路徑，也不是最短路徑。以下三個相關問題很容易與之混淆，而本求解器刻意不設計來處理它們：
| 問題 | 所求的答案 | 適合的工具 |
|---|---|---|
| 最小生成樹 | 連接所有節點且無迴圈、總權重最小的連接方式 | 本求解器 |
| 兩節點間的最短路徑 | 從一個節點到另一個節點、權重最小的路徑 | 支援有向或無向邊的 Dijkstra 風格求解器 |
| 走訪所有節點的封閉順序 | 從某節點出發、每個其他節點各拜訪一次並返回的路徑 | 旅行推銷員（traveling-salesperson）模型 |
| 一對一最小成本指派 | 將工作者指派給任務，使每位工作者各得一項任務且總成本最小 | 匈牙利演算法求解器，例如指派問題逐步解析教學 |
這些問題具有相同的嚴謹輸入、驗證與結果模式，但它們所最佳化的目標不同，因此各自需要獨立的模型。
必須遵守的輸入規則與限制
求解器的輸入規範刻意訂得嚴格，目的是讓模型錯誤以清楚的訊息呈現，而非產生不知不覺的錯誤生成樹：
- 2 到 50 個不重複的節點名稱。標籤中不可包含逗號，因為逗號已作為欄位分隔符。
- 最多 500 條不重複的無向邊，權重為有限的實數。權重可為正數、零或負數；Kruskal 演算法在這三種情況下皆有效。
- 拒絕自環——自環對生成樹毫無助益。
- A,B 與 B,A 視為重複配對並予以拒絕，因此工具無需對同一條邊的兩種定義進行平手決勝。
- 平行邊（同一對端點之間的兩條不同邊）不在簡化的輸入規範範圍內。若模型中包含平行邊，請預先在原始資料上選取一有效的權重，或以額外節點來表示各個替代方案，並記錄該決策，以免將被捨棄的選項誤判為演算法的選擇。
- 圖形必須連通。若已輸入的邊無法將各獨立元件連接起來，頁面會回報錯誤，而不會回傳誤導性的森林。
- 相同權重時保留輸入順序，使結果在多個最小生成樹並存時仍具有確定性。
這些規則能抓出僅挑選最便宜邊卻未防止迴圈的實作——這在粗糙的最小生成樹程式碼中是知名的陷阱。
實際應用結果
在演算法學習與小型網路設計草稿方面，本求解器可用來快速檢查手動的 Kruskal 演算過程，或產生一組乾淨的範例資料。八個經人工稽核的測試案例涵蓋了通常會使小型實作出錯的邊界情況：兩節點圖形、三角形、權重平手、零與負權重、五節點的迴圈，以及由一條昂貴橋接邊相連的連通元件。每個案例皆斷言恰好選出了 V−1 條邊，且總和與已知值相符；此外還要求不連通的圖形必須回報失敗。
對於實際的基礎設施規劃——纜線佈設、管線、公路設計——同樣的純量權重邏輯並無法涵蓋地理、冗餘、容量、可靠度、法規、現有資產或施工限制。純粹的最小生成樹也是單一樹而無冗餘，因此在運作上可能較為脆弱。本求解器對於抽象的邊權重問題是一個健全的模型，也是對手動演算過程的有用檢查點；它無法取代以真實資料來驗證模型所代表內容的工作。
欲深入了解，請參閱旅行推銷員問題：最佳解路徑建構器。