地特四等申論題
109年
[統計] 資料處理概要
第 一 題
給定一個有權重的圖形 G=(V, W)，V 為頂點集合，W 為邊以及該邊上權重的集合。
假設 V={A,B,C,D,E,F}，
W={{A,B,2},{A,C,6},{B,D,7},{C,D,4},{C,E,5},{D,F,10},{E,F,9}}，
請找出 G 的最小生成樹（Minimum Spanning Tree），並詳細說明執行的步驟。（25分）
📝 此題為申論題
思路引導 VIP
看到「最小生成樹 (MST)」，應立即聯想到 Kruskal 或 Prim 演算法。建議作答時明確標示採用 Kruskal 演算法，先將所有邊依權重由小到大排序，接著依序挑選不產生迴圈的邊，直到選滿 V-1 條邊為止，此方法在紙筆測驗中步驟最為清晰且易於驗算。
🤖
AI 詳解
AI 專屬家教
【解題思路】採用 Kruskal 演算法，將圖形中所有邊依權重排序，並在不形成迴圈的前提下，依序選取 N-1 條邊構成最小生成樹。 【詳解】 已知：
▼ 還有更多解析內容