地方政府公務人員四等-電子工程類科計算機概要107 年第 18 題單選題
下圖中邊長總和最大的生成樹（spanning tree），其邊長總和為何？
C正確答案
本題求「最大生成樹」，可利用 Kruskal 演算法變形，將邊權重由大到小排序並依序加入，避開迴圈即可求得總和 43。
為什麼答案是 C
依序選取不構成迴圈的最大邊：c-i(8), e-f(7), f-i(6), g-h(6), a-b(5), a-c(4), h-i(4), a-d(3)。共 8 條邊，總和為 43。
載入中…
完整詳解
Pro · 無限重點 本題求「最大生成樹」，可利用 Kruskal 演算法變形，將邊權重由大到小排序並依序加入，避開迴圈即可求得總和 43。
邊權重由大到小：8, 7, 6, 6, 5, 4(a-c), 4(h-i), 3(a-d)。注意 4(e-i) 會形成迴圈需捨棄，加總即為 43。
逐選項分析
A✕
若在挑選邊的過程中，誤判迴圈而提早捨棄了較大的邊，或者計算加總時發生失誤，可能會得出此錯誤數值。
B✕
此為錯誤的加總結果。在執行 Kruskal 演算法挑選最大邊時，若未正確避開迴圈或漏算某條邊，可能導致此結果。
C✓ 正確
依序選取不構成迴圈的最大邊：c-i(8), e-f(7), f-i(6), g-h(6), a-b(5), a-c(4), h-i(4), a-d(3)。共 8 條邊，總和為 43。
D✕ 陷阱
若未檢查迴圈，誤將權重為 4 的 e-i 邊加入（會形成 e-f-i 迴圈），可能會算出大於 43 的錯誤總和。
Kruskal 演算法 (最大生成樹應用)
| 步驟 | 核心概念 | 本題實作細節 |
|---|
| 1. 排序 | 將所有邊的權重依需求排序 | 由大到小排序：8, 7, 6, 6, 5, 4, 4, 4, 3... |
| 2. 依序選取 | 從權重最大（或最小）的邊開始挑選 | 優先加入 8(c-i), 7(e-f), 6(f-i), 6(g-h) |
| 3. 迴圈偵測 | 若加入該邊會與已選邊形成封閉迴圈，則捨棄 | 遇到 4(e-i) 時，因 e-f-i 已連通形成迴圈，必須捨棄 |
| 4. 終止條件 | 當選取了「頂點數 - 1」條邊時即完成 | 本圖有 9 個頂點，選滿 8 條邊即停止，總和為 43 |
一般資料結構考題多半要求計算「最小生成樹 (MST)」，但本題題幹明確要求「最大」生成樹。若考生習慣性地從權重最小的邊開始挑選，將會完全算錯。 
