線上最小生成樹計算工具會從無向邊列表中剛好回傳 V−1 條邊，並忽略任何會形成環的邊。這裡的「V」代表你輸入的具名節點數量;「V−1」則是樹結構在不產生環的情況下連接到所有節點所需的邊數。當 Kruskal 演算法依權重排序邊、並僅保留連接兩個原本分離元件的邊後,結果會是針對你提供的輸入、權重總和最小的樹——不是一條路線、不是兩點之間的最短路徑,也不是有向結構。這個區別很重要,因為同一張圖在不同的問題定義下,可能會產生不同的最佳解,例如旅行推銷員問題(一個封閉的拜訪順序)、Dijkstra 風格的最短路徑(在合適權重下的點對點距離),或有向最小生成樹形圖(有向圖上以某個節點為根的分支結構)。本頁提供的線上 MST 工具專門處理無向、純量權重、單一連通元件的情境——也就是說,建模問題真的是「把這些具名節點連起來最便宜的方法是什麼」。
線上最小生成樹計算工具實際上會產生什麼
連通無向圖的最小生成樹,是邊的一個子集合,須連到所有頂點、不含環,並且在所有符合條件的子集合中,擁有最小的總權重。所選邊的數量永遠剛好是 V−1,其中 V 是節點數,因為 V 個頂點的樹會有 V−1 條邊,這是在連通圖中達到完全連接所需的最少邊數。多一條邊就會產生環,少一條邊則至少會留下一個孤立的頂點。本工具內部採用的正式定義,遵循 Princeton Algorithms 課程筆記中關於最小生成樹的 Kruskal 風格處理方式。
「線上」這個詞只是表示計算在瀏覽器中執行,而不是需要本機安裝或伺服器往返:你在表單中輸入節點名稱與加權邊,網頁會在本地套用 Kruskal 演算法,然後結果會列出所選的 V−1 條邊以及它們的總權重。Minimum Spanning Tree Solver 正是依照這個契約實作,使用 disjoint-set union 來追蹤每條邊會合併哪些元件,因此即使邊數增加,拒絕步驟也能維持接近常數時間。
MST 計算工具在輸入欄位中預期的內容
輸入契約既精簡又嚴格,遵守它正是結果可信賴的原因:
- 2 到 50 個不重複的節點名稱,以逗號分隔(例如 A, B, C, D)。
- 1 到 500 條邊,每條佔一行,使用 from, to, weight 的格式,且節點名稱必須與你宣告的完全一致。
- 所有邊的端點都必須對應到一個已宣告的節點,且節點名稱的大小寫不敏感——「A」和「a」會被視為同一個頂點。
- 邊的權重可以是正數、零或負數,因為 Kruskal 演算法對任何有限的實數權重都仍然有效。
- 圖是無向的,因此以 A,B,7 輸入的邊若再以 B,A,7 輸入會被視為重複,計算工具會拒絕後者,而不是把它們當成兩個互相競爭的選項。
標籤不能包含逗號,因為逗號是欄位分隔符;自環(self-loop)對生成樹沒有幫助,因此也會被拒絕。同一對端點之間的多重邊不在這個簡化輸入契約的範圍內;若你在 A 和 B 之間有好幾個候選權重,請先挑選你想讓演算法使用的權重,並把這個決定記錄下來,以免被捨棄的選項被誤認為是演算法的選擇。
在瀏覽器中從邊列表建立 MST
以下是在計算工具頁面上的核心工作流程:
- 在瀏覽器中開啟 Minimum Spanning Tree Solver。
- 把所有節點名稱輸入到節點欄位,以逗號分隔——例如 A, B, C, D, E。
- 每一條邊各佔一行,使用 from, to, weight 的格式,兩個端點都必須對應到已宣告的名稱。
- 點擊建立按鈕,在本地對輸入的圖執行 Kruskal 演算法。
- 讀取結果面板頂部的連通圖確認訊息;若顯示的是未連通圖錯誤,請再次確認每個節點都已透過輸入的邊連接起來。
- 將結果面板中選出的 V−1 條邊以純文字複製出來,用於書面報告、簡報或後續模型。
你可以在不離開頁面的情況下反覆操作:編輯名稱、調整權重,或新增另一條邊後重新建立,即可看到每次變更如何影響所選的集合。
範例演練:一個可以用手驗證的四節點圖
取四個節點 A, B, C, D 以及五條無向邊(from, to, weight):
A, B, 3 A, C, 1 A, D, 4 B, C, 2 C, D, 5Kruskal 首先依權重排序,權重相同時則依邊的輸入順序決定優先順序:
- A, C, 1 — 接受;合併 {A} 與 {C}。
- B, C, 2 — 接受;把 {B} 合併進 {A, C},形成 {A, B, C}。
- A, B, 3 — 拒絕;兩個端點都已在 {A, B, C} 中,加上會形成環。
- A, D, 4 — 接受;把 {D} 接上 {A, B, C},在處理第四條邊時即連到所有節點。
- C, D, 5 — 拒絕;兩個端點都已在 {A, B, C, D} 之中。
選出的 V−1 = 3 條邊為 {A,C;1}、{B,C;2}、{A,D;4},總權重為 1 + 2 + 4 = 7。第五條候選邊是這個列表中最重的,在四個頂點已透過 C 以更便宜的路徑連接起來後,演算法完全不需要它。把同樣的邊列表送進 Minimum Spanning Tree Solver,結果應該會與上述推導完全一致。
若把 A,D,4 改成 A,D,10,演算法在第四步就會改為接受 C,D,5,總權重上升為 1 + 2 + 5 = 8——這是一個快速驗證計算工具會依你的新輸入重新執行 Kruskal、而不是快取先前結果的方法。
平手、負權重,以及未連通圖錯誤
在相信輸出之前,有三種情況值得了解,因為每一種都會改變結果能與你進行的對話:
- 存在多棵最小樹的相同權重。當好幾棵生成樹共享同樣最低的總權重時,Kruskal 演算法仍然只會產生其中一個有效的最佳解,而不是「全部」。平手會依輸入順序而非隨機數產生器來打破,因此輸出可以重現:重跑同樣的輸入,每次都會得到同一棵樹。
- 負權重。Kruskal 對任何有限的實數權重都有效,包含負值,因為其正確性證明只依賴邊的排序結果。一條有用的負權重邊只要不形成環就能被選入,總權重也可能因此低於你直覺預期的全為正數的最小值。
- 未連通的圖。對於有多個連通元件的圖,不存在任何生成樹,因為沒有任何一組邊能從單一的分支結構連到所有頂點。計算工具不會回傳一個誤導人的森林,而是顯示明確的未連通圖錯誤,讓你知道要新增一條連接邊或重新檢視節點列表。
MST 與 TSP、最短路徑及有向分支樹的比較
同一份邊列表,依你實際想問的問題不同,可能產生截然不同的「最佳」答案。下表摘要說明四個密切相關的圖論問題有何差異;本頁的線上工具只處理第一列。
| 你想問的問題 | 最佳解是 | 是否對順序敏感? | 方向是否重要? | 處理工具 |
|---|---|---|---|---|
| 連接所有節點最便宜的方式(MST) | V−1 條無向邊,不含環 | 否 | 否 | Minimum Spanning Tree Solver |
| 造訪所有節點的最短封閉路線(TSP) | 通過所有節點的 Hamiltonian 環 | 是 | 否 | Traveling Salesman Solver |
| 選定一對節點之間的最短路徑 | 一條點對點路徑 | 否 | 否(通常為無向) | Dijkstra 風格的最短路徑函式庫 |
| 在有向圖中以選定來源為根的最便宜分支 | 一個有向分支樹(arborescence) | 否 | 是 | 專用的 arborescence 演算法 |
若你的問題牽涉地理、備援、容量、法規、現有資產或施工限制,MST 只是一個起點草圖。樹本身沒有內建的備援,操作上也可能脆弱,因此在做出任何實體決定之前,都應該再依據真實限制進行驗證。
需要留意的限制與模型假設
瀏覽器為了保持操作流暢,上限為 50 個節點與 500 條邊;更大的問題需要在本機使用專門的函式庫,而不是用計算工具頁面。標籤不能包含逗號,自環會被拒絕,重複的無向配對——亦即把 A,B 與 B,A 分別輸入——會被拒絕,而不是默默視為互相競爭。MST 只最小化你所輸入的抽象邊總和:它不會聲稱任何單一路線是最短的,也完全忽略邊的方向。此工具適合用於演算法學習、小型網路設計草稿、佈線範例,以及驗證手寫的 Kruskal 推導;請把真實的基礎建設規劃視為另一個獨立的建模工作,在最小權重草圖之上再加入地理、備援、容量與可靠度等考量。