申論題 - 阿摩線上測驗

申論題資訊

試卷：109年 - 109 高等考試_三級_資訊處理：資通網路#88768
科目：電腦網路(計算機網路網路工程資通網路)
年份：109年
排序：0

四、請將下列無方向連接圖（undirected connected graph），依子題之說明，起始節點為節點0，建構一最小費用擴張樹（minimum cost spanning tree）。（註：圖中圓圈標示節點（node）號碼，連線（link）旁標示費用；作答時必須標示加入連線的順序）

(二)採用Kruskal’s algorithm含限制條件：每一分支（branch）最多含3段連線（link）。

詳解提供者：牛奶鍋

分支分為0到3以及0到4，這兩條線路只能含有3條以下的links以及不能含有cycle

0到1的18形成cycle不加入

2到6的20超過分支所能有的links (0到3的分支)

3到6的22超過分支所能有的links (0到3的分支)