申論題 - 阿摩線上測驗

申論題資訊

試卷：103年 - 103年地方三等-三等資料結構#42936
科目：公職◆資料結構
年份：103年
排序：0

一、給定一個權重圖（weighted graph）G(V, E) 如下圖所示。

(三)假設最小生成樹 MST(G) 已知。若在原圖 G(V, E) 中加入一個新的邊 vi - vj 且其權重為 w。請設計一個 O(V) 的演算法，從已知的 MST(G) 中快速找出新圖的最小生成樹。請以文字敘述說明。（10 分）