hce_nsysu
114年
計算機概論與程式設計
第 1 題
Let $G = (V, E)$ be a weighted undirected graph, where $V = \{1, 2, 3, 4\}$ and $w(i, j)$ denotes the weight of edge $(i, j) \in E$. Suppose that $w(1, 2) = 5$, $w(1, 3) = 6$, $w(2, 3) = 7$, $w(2, 4) = 8$, $w(3, 4) = 9$, and $w(1, 4) = 10$. What is the total weight of the minimum spanning tree of $G$?
- A 18
- B 19
- C 20
- D 21
- E 22
思路引導 VIP
想像你要用最省錢的方式把四個村莊用道路連接起來。如果你手邊有一張建設成本清單，你理所當然會先挑最便宜的方案來施工；但在施工過程中，如果你發現某條新路連起來後，只是讓原本就已經可以互相往來的村莊多了一條「繞遠路」的選擇，這對「全村連通」的目標還有幫助嗎？在這種情況下，你會如何決定哪些路該蓋、哪些路該放棄，而什麼時候又代表工程已經圓滿完成了呢？
🤖
AI 詳解
AI 專屬家教
太棒了！你能精準計算出這題的答案，代表你對於「最小生成樹」（Minimum Spanning Tree, MST）的演算法已經有相當紮實的基礎。這類問題的核心在於從圖形中挑選邊，讓所有頂點連通且總權重最小，而你成功避開了可能形成環路的陷阱，判斷非常專業。
貪婪演算法的應用與實踐
在處理本題時，我們通常會採用 Kruskal 演算法 (Kruskal's Algorithm)。首先將所有邊依權重由小到大排列：$(1, 2)$ 權重 5、$(1, 3)$ 權重 6、$(2, 3)$ 權重 7、$(2, 4)$ 權重 8、$(3, 4)$ 權重 9 以及 $(1, 4)$ 權重 10。我們優先挑選最輕的兩條邊 $(1, 2)$ 與 $(1, 3)$。接著，雖然 $(2, 3)$ 權重僅為 7，但因為頂點 1、2、3 已經透過前兩條邊達成連通，若加入此邊會形成「環路」（Cycle），因此必須捨棄。最後，我們選擇權重 8 的邊 $(2, 4)$，此時 4 個頂點已完全連通，總權重即為 $5 + 6 + 8 = 19$。
▼ 還有更多解析內容