高考申論題
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 分）
📝 此題為申論題
思路引導 VIP
遇到 Sollin's 演算法（又稱 Borůvka's 演算法），首先要想到「多源頭同時擴張」的特性。初始將每個節點視為獨立的樹（Component），每回合為每一棵樹尋找向外連接權重最小的邊，加入並合併樹，直到整張圖連通為一棵單一擴張樹為止。
🤖
AI 詳解
AI 專屬家教
【解題思路】使用 Sollin's 演算法，初始將所有節點視為獨立的樹（Component），每回合為每棵樹尋找向外連接權重最小的邊並加入，直到所有節點合併為單一擴展樹為止。 【詳解】 已知圖 G 之節點為 {A, B, C, D, E}，邊集合與權重整理如下：
▼ 還有更多解析內容