二、用G=(V,E)表示一個無方向性圖形，其中V是點的集合，E是一組節點（Vertices）形成邊的集合。今有一圖形G=(V,E)，V(G)={T,W,X,Y,Z}, E(G)={(T,W),(T,Y),(T,Z),(W, X),(W, Z),(X, Z)}，每一個邊對應的權重值分別為 2, 1, 7, 4, 3, 6，請用相鄰矩陣（Adjacency Matrix）與相鄰串列（Adjacency List）表示此圖形，並使用 Prim’s 演算法，計算最小成本擴張樹（Minimum Cost Spanning Tree），依序寫出從點 X 加入邊的順序，最小成本擴張樹的權重總和為何？（25 分）

内容查看

首先，我們來表示這個圖形G的相鄰矩陣和相鄰串列。

相鄰矩陣（Adjacency Matrix）：

相鄰串列（Adjacency List）：

接下來，我們使用Prim’s演算法來計算最小成本擴張樹。首先從節點X開始：

選擇節點X，加入邊 (X, W)。目前的MST包含邊 [(X, W)]。
選擇節點W，加入邊 (W, T)。目前的MST包含邊 [(X, W), (W, T)]。
選擇節點T，加入邊 (T, Y)。目前的MST包含邊 [(X, W), (W, T), (T, Y)]。
選擇節點Y。由於已無其他點，回過之前看過的點來看。
5.邊 (T, Z)是7且(W, Z)是3，所以選(W, Z)，目前的MST包含邊 [(X, W), (W, T), (T, Y), (W, Z)]。

所以，從點X加入邊的順序是：(X, W) -> (W, T) -> (T, Y) -> (W, Z)

最小成本擴張樹的權重總和為：4 + 2 + 1 + 3 = 10。

点点赞赏，手留余香给TA打赏