題組內容

三、有一無向性連結圖（undirected connected graph）如圖所示，每一鏈路（link）的成本標示在該鏈路旁邊。試依圖建構一個最小成本生成樹（minimum cost spanning tree）並標示其生成順序。（每小題 10 分，共 20 分） phpRVKgMg

(二)採用 Kruskal’s algorithm 但限制每一分支（branch）最多只能有兩條鏈路。

詳解提供者：白龍@菜鳥公務員(107/10/29)

使用Kruskal's algorithm 且限制每一分支最多只能有兩條鏈路之建構最小生成樹的順序如下:

1. 連接AD，權重5

2. 連接BE，權重6

3. 連接DE，權重7

4. 連接CF，權重9

5. 連接GF，權重12

6. 連接BC，權重14