高考申論題
114年
[資訊處理] 資料結構
第 三 題
三、假設 G 為一個無方向連通加權圖（Undirected connected weighted graph），包含五個節點：A、B、C、D、E。各節點間相連情形如下，邊權（邊的權重）為正整數，代表邊的成本。
A 與 B 相連，邊權為 16；
A 與 C 相連，邊權為 18；
A 與 D 相連，邊權為 14；
B 與 C 相連，邊權為 15；
C 與 D 相連，邊權為 13；
D 與 E 相連，邊權為 12；
C 與 E 相連，邊權為 17；
請使用 Sollin’s 演算法，寫出最終形成的最小成本擴展樹的邊集合與總成本，請寫出每一步的演算法與該步驟形成的擴展樹。每一合併過程，列出選中的邊與合併的組成（component）。（20 分）
A 與 B 相連，邊權為 16；
A 與 C 相連，邊權為 18；
A 與 D 相連，邊權為 14；
B 與 C 相連，邊權為 15；
C 與 D 相連，邊權為 13；
D 與 E 相連，邊權為 12；
C 與 E 相連，邊權為 17；
請使用 Sollin’s 演算法，寫出最終形成的最小成本擴展樹的邊集合與總成本，請寫出每一步的演算法與該步驟形成的擴展樹。每一合併過程，列出選中的邊與合併的組成（component）。（20 分）
📝 此題為申論題
思路引導 VIP
遇到 Sollin's 演算法（又稱 Borůvka's 演算法），首先要想到「多源頭同時擴張」的特性。初始將每個節點視為獨立的樹（Component），每回合為每一棵樹尋找向外連接權重最小的邊，加入並合併樹，直到整張圖連通為一棵單一擴張樹為止。
🤖
AI 詳解
AI 專屬家教
【解題思路】使用 Sollin's 演算法，初始將所有節點視為獨立的樹（Component），每回合為每棵樹尋找向外連接權重最小的邊並加入，直到所有節點合併為單一擴展樹為止。 【詳解】 已知圖 G 之節點為 {A, B, C, D, E}，邊集合與權重整理如下：
▼ 還有更多解析內容
Sollin's 演算法
💡 多個連通元件同步尋找對外最小權重邊，反覆合併直到形成最小生成樹。
🔗 Sollin's 演算法執行邏輯
- 1 初始化組成 — 將 n 個節點視為 n 個獨立的樹（Component）
- 2 同步找邊 — 每個 Component 分別找出權重最小的對外邊
- 3 去重與合併 — 剔除重複選邊後，加入邊並合併 Component
- 4 判斷終止 — 若尚未完全連通則回步驟 2，若已連通則輸出 MST
↓
↓
↓
🔄 延伸學習：延伸學習：Sollin's (Boruvka's) 演算法因其同步特性，極適合應用於平行處理運算環境。
