申論題 - 阿摩線上測驗

申論題資訊

試卷：106年 - 106 專技高考_電子工程技師：電子計算機原理#66508
科目：計算機概論、大意(資訊科學概論,電腦常識,電子計算機概論)
年份：106年
排序：3

三、有一無向性連結圖（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