地特三等申論題
105年
[資訊處理] 資料結構
第 三 題
試針對下列無向網路圖形（Undirected Network Graph）
N(V,E,C),V={1,2,3,4,5,6},N={(1,2,6),(1,5,19),(1,6,21),(2,3,5),(2,4,16),(2,5,11),
(3,4,10),(4,5,8),(4,6,9),(5,6,7)}，成本 C(1,2)=6, C(1,5)=19…等，
求最小成本擴張樹（minimal cost spanning tree）的最小成本。（10 分）
📝 此題為申論題
思路引導 VIP
看到求解「最小成本擴張樹（MST）」時，應立即聯想 Kruskal 演算法或 Prim 演算法。建議考試時使用 Kruskal 演算法，先將所有邊依成本由小到大排序，接著依序挑選不產生迴路（Cycle）的邊，直到選出 V-1 條邊即可求出最小成本。
🤖
AI 詳解
AI 專屬家教
【解題關鍵】利用 Kruskal 演算法，將所有邊依成本遞增排序後，依序挑選不形成迴路的邊，直到選出 V-1 條邊。 【解答】 計算：以 Kruskal 演算法進行逐步推導
▼ 還有更多解析內容