是的——最小生成樹求解器接受負邊權重，只要每個權重都是有限的實數，而且 Kruskal 演算法不論正負號，都能產生正確的最小權重樹。這裡介紹的最小生成樹求解器明確允許權重為正、零或負，因為底層的 Kruskal 程序是以數值方式比較權重，只有在加入邊會形成環路時才會跳過，而不是根據數值是否大於或小於零來決定。將權重視為純量，正是讓這項技術得以延伸到各種問題的關鍵——在這些問題中，負權重代表的是獎勵、節省、高度差或溫度懲罰，而不是字面上的長度。由普林斯頓大學演算法課程維護的 Kruskal 參考實作正是本工具行為的模型，該實作對負數輸入套用了與正數輸入相同的規則，而最小生成樹求解器的產品合約也明確指出權重可以是正、零或負，因為 Kruskal 對有限的實數邊權重仍然有效。
為什麼負權重不會破壞 Kruskal
Kruskal 演算法的正確性證明奠基於三個操作:依權重排序邊、挑選連通分量不同的端點中最輕的可用的邊，以及在接受 V−1 條邊後停止。這些操作都不依賴權重的正負號。排序仍然會把最負的數字排在最前面;「不同分量」的意義始終不變;V−1 條邊的停止規則也仍然適用。一個有用的理解方式是:Kruskal 在有限的候選生成樹集合中，將某個純量總和最小化——不管那個純量總和最後是正或負，最小值仍然明確且可達。
這與最短路徑演算法形成鮮明對比。Dijkstra 演算法假設權重為非負數，若輸入負邊可能會給出錯誤答案。最小生成樹演算法則沒有這種限制，這也是為什麼 MST 方法會出現在相關聚類、影像分割，以及某些自然產生有號數值的最小比率目標等問題中。產品合約反映了這點，直接聲明權重可以是正、零或負，而 Kruskal 仍然有效。
| 特性 | 正權重 | 零權重 | 負權重 |
|---|---|---|---|
| Kruskal 最先排序 | 最輕的正邊 | 零權重邊(平手) | 最負的邊 |
| 環路測試 | 標準 | 標準 | 標準 |
| 端點不同時選入 | 是 | 是 | 是(通常等同於免費收益) |
| 端點已連接時跳過 | 是 | 是 | 是 |
| 最終總權重的正負 | 通常為正 | 視混合情況而定 | 可能為負 |
有號權重並不會改變答案的型別或演算法的判定——只有數值總和最後可能小於零。這就是為什麼對標題問題的簡短答案是肯定的:負權重是有效的輸入，最小生成樹求解器會像處理任何其他有限數字一樣處理它們。
如何使用負邊權重求解 MST
- 開啟最小生成樹求解器，在節點欄位中輸入 2 到 50 個以逗號分隔的唯一節點名稱。
- 針對每條邊，以「起點，終點，權重」的格式輸入一行，使用您所宣告的名稱，包含任何有限實數權重，例如 -3、-12.5 或 0。
- 確認每一行使用完全相同的已宣告節點名稱——節點名稱的大小寫不敏感但必須唯一，且標籤不能包含逗號，因為逗號是欄位分隔符。
- 點選建立動作。求解器會正規化節點名稱、驗證最多 500 條唯一且權重為有限實數的無向邊、依權重與輸入順序進行穩定排序，並執行不相交集聯合結構以只接受連接不同分量的邊。
- 讀取選中的邊清單。在連通圖上，清單必須恰好包含 V−1 條邊;若邊無法讓所有節點連通，頁面會顯示明確的「圖不連通」錯誤訊息。
- 將選中的邊和總權重以純文字複製。總和可能為負;這就是您所輸入數字的正確最小值。
混合有號權重的完整範例
考慮三個節點 A、B、C，其無向邊為 A–B 權重 4、B–C 權重 −3、A–C 權重 2。節點數為 3，因此生成樹必須恰好包含 2 條邊。依權重排序得到 −3 (B–C)，然後是 2 (A–C)，最後是 4 (A–B)。Kruskal 先接受 B–C，因為其兩端點位於不同分量;接著接受 A–C，因為 A 是 B–C 分量外唯一的節點。這兩條選中的邊總和為 −1;這是合法的最小總權重。若改用另一組兩邊組合 A–B 加上 B–C，總和會是 1，大於 −1，證實負權重邊確實是最佳解的一部分。
這類情境也可用於人工驗證工具。同樣的形式出現在工具的多項稽核檢查中——八個經人工稽核的黃金案例涵蓋了雙節點邊界、三角形、平手權重、零與負權重、五節點環路，以及由一條昂貴橋接邊連接的不連通分量——並斷言 MST 包含 V−1 條選中的邊，且總和等於人工計算結果。您可以透過在求解器中輸入 A,B,4、B,C,-3 和 A,C,2 來自行重播這套稽核邏輯。
需要注意的限制與邊界情況
負權重雖然被接受，但仍有幾項相關規則需要遵守。圖必須是無向的:若以相同權重同時宣告「A,B」與「B,A」，會被視為重複配對而遭到拒絕，而不是默默地相互競爭;而像是「A,A」這類自迴圈對生成樹沒有幫助，也會被拒絕。平行邊——即兩條端點相同但權重不同(包含負權重)的邊——不在簡化的輸入合約範圍內:工具會要求您預先選擇一個有效權重，或以額外的節點來模擬其他選擇，並記錄該決定，避免被誤認為是演算法選擇。
連通性無論正負號都會強制檢查。若處理完所有邊後，可接受的分量連接邊少於 V−1 條，頁面會顯示明確的「圖不連通」錯誤訊息，而不是回傳一個誤導性的森林。這與教科書定義一致:生成樹僅存在於連通圖上，與權重為負、零或正無關。
瀏覽器將輸入上限設為 50 個節點與 500 條邊，以保持互動流暢;超過這些上限的值並非負權重問題，而是超出處理範圍。平手權重會保留輸入順序，因此當存在多個最佳生成樹時，所選的集合是確定且可重現的——無論平手權重為正、零或負，行為皆相同。
何時 MST 不是合適的工具
MST 是一種將純量總和最小化的分支結構——它既不是從某處出發、造訪每個節點的路徑，也不是所選兩個節點之間的最短路徑。它也忽略邊的方向。若您的「負權重」實際上代表的是一種應該翻轉目標的效益(您想最大化總和而非最小化)，正確的做法是將正負號反轉為最小化問題，或是選擇完全不同的模型。對於經過座標的封閉拜訪順序，旅行推銷員求解器是自然選擇;對於點對點最短距離，請使用具備合適權重的 Dijkstra 類最短路徑工具;對於有向分支，則應使用有向樹狀分支方法。
在實務的網路設計中，請記得最小純量權重樹完全沒有冗餘，可能在營運上相當脆弱。地理、冗餘、容量、可靠性、法規、現有資產與施工限制在真實規劃中都很重要，這些考量與權重為負、零或正無關。最小生成樹求解器非常適合用於演算法學習、小型網路設計草圖、纜線佈局範例，以及驗證人工 Kruskal 推導過程，但任何影響實體基礎建設的決策都應該驗證模型——而負權重是否被允許，僅是其中一小部分驗證而已。
若想要與本工具搭配的補充概念說明，逐步 MST 指南涵蓋了人工推導範例，並使用與本文相同的 Kruskal 規則。
若您正在權衡各種選擇，紙張基重換算:GSM 與 lb 解析對此有詳細說明。