高考申論題
109年
[資訊處理] 資通網路
第 一 題
📖 題組：
請將下列無方向連接圖（undirected connected graph），依子題之說明，起始節點為節點0，建構一最小費用擴張樹（minimum cost spanning tree）。（註：圖中圓圈標示節點（node）號碼，連線（link）旁標示費用；作答時必須標示加入連線的順序）（每小題10分，共20分） (一)採用Kruskal’s algorithm不含任何限制條件。 (二)採用Kruskal’s algorithm含限制條件：每一分支（branch）最多含3段連線（link）。
請將下列無方向連接圖（undirected connected graph），依子題之說明，起始節點為節點0，建構一最小費用擴張樹（minimum cost spanning tree）。（註：圖中圓圈標示節點（node）號碼，連線（link）旁標示費用；作答時必須標示加入連線的順序）（每小題10分，共20分） (一)採用Kruskal’s algorithm不含任何限制條件。 (二)採用Kruskal’s algorithm含限制條件：每一分支（branch）最多含3段連線（link）。
📝 此題為申論題，共 2 小題
小題 (一)
採用Kruskal’s algorithm不含任何限制條件。
思路引導 VIP
Kruskal 的核心是「貪婪演算法」：
- 先列出所有邊並依費用由小到大排序。
小題 (二)
採用Kruskal’s algorithm含限制條件：每一分支（branch）最多含3段連線（link）。
思路引導 VIP
這題多了限制：從起始節點（0）出發的任何分支路徑不能超過 3 個連線。這意味著在挑選邊時，除了檢查是否有「環」外，還要計算從節點 0 到該新節點的路徑長度。若路徑長度將超過 3，則必須捨棄該邊並找下一個最小邊。考生需追蹤每一點到點 0 的距離（Hop Count）。