高考申論題
111年
[資訊處理] 資料結構
第 四 題
用 G = (V, E)表示一個無方向性圖形，其中 V 是點的集合，E 是一組節點（Vertices）形成邊及對應權重（Weights）所組成的集合。今有一圖形 G = (V, E)，V = {0, 1, 2, 3, 4, 5}，圖形的邊與權重值以如下的定義儲存對應連接矩陣(Adjacency matrix)表示中的值
#define MAX_EDGES 100
typedef struct {
int col;
int row;
int weight;
} edge;
edge a[MAX_EDGES];
已知陣列 a 儲存對應連接矩陣相連接邊的內容如下：a = {(3, 0, 2), (4, 0, 1), (5, 0, 20), (2, 1, 7), (5, 1, 24), (3, 2, 15), (4, 2, 10), (5, 2, 25), (4, 3, 3)}。請畫出陣列 a 所儲存的圖形，然後，利用 Prim 演算法從節點 0 開始依加入其它節點的順序，畫出此圖之最小擴張樹（Minimum spanning tree），並計算其最低權重或成本值。（25 分）
#define MAX_EDGES 100
typedef struct {
int col;
int row;
int weight;
} edge;
edge a[MAX_EDGES];
已知陣列 a 儲存對應連接矩陣相連接邊的內容如下：a = {(3, 0, 2), (4, 0, 1), (5, 0, 20), (2, 1, 7), (5, 1, 24), (3, 2, 15), (4, 2, 10), (5, 2, 25), (4, 3, 3)}。請畫出陣列 a 所儲存的圖形，然後，利用 Prim 演算法從節點 0 開始依加入其它節點的順序，畫出此圖之最小擴張樹（Minimum spanning tree），並計算其最低權重或成本值。（25 分）
📝 此題為申論題
思路引導 VIP
這是一題關於「圖形（Graph）」與「最小擴張樹（MST）」的計算題。
- 畫圖（Graph Drawing）：根據
a陣列中的row,col,weight資訊繪製。例如(3, 0, 2)表示點 0 與點 3 之間有一條權重為 2 的邊。
🤖
AI 詳解
AI 專屬家教
【考點分析】 本題考查圖形的表示法（邊清單）以及 Prim 演算法建構最小擴張樹（MST）的步驟。重點在於正確辨識節點間的連接關係與權重。 【理論/法規依據】
▼ 還有更多解析內容
Prim 演算法與 MST
💡 從起始點開始，依序選取與當前集合相連之權重最小邊以建立 MST。
🔗 Prim 演算法執行流程
- 1 選定起始點 — 任意選擇一節點（如題目要求的節點 0）作為根。
- 2 尋找最小邊 — 找出與目前已選集合相連且權重最小的邊。
- 3 納入新節點 — 將最小邊連接的未選節點加入已選集合。
- 4 迭代至完成 — 重複直到所有節點皆被選入，形成最小擴張樹。
↓
↓
↓
🔄 延伸學習：延伸學習：使用優先佇列（Priority Queue）可優化 Prim 尋找最小邊的效率。
