申論題

三、假設 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 分）