高考申論題
111年
[資訊處理] 資料結構
第 一 題
📖 題組：
下圖是一個加權圖 G=(V, E)，其中 V 是點集合而 E 是邊集合。 （圖形描述：節點 a-i 的加權無向圖。圖中邊與權重關係如下：a-b:22, a-h:14, b-c:10, b-d:41, b-g:35, c-f:31, d-f:4, d-g:18, f-i:29, g-h:6, h-i:37）
下圖是一個加權圖 G=(V, E)，其中 V 是點集合而 E 是邊集合。 （圖形描述：節點 a-i 的加權無向圖。圖中邊與權重關係如下：a-b:22, a-h:14, b-c:10, b-d:41, b-g:35, c-f:31, d-f:4, d-g:18, f-i:29, g-h:6, h-i:37）
📝 此題為申論題，共 3 小題
小題 (一)
請使用相鄰矩陣（Adjacency Matrix）表示法來表示加權圖 G。（5 分）
思路引導 VIP
看到加權圖的相鄰矩陣題，先確認圖中所有的節點數量與名稱，建立一個 NxN 的方陣。接著將圖中每條邊的權重對應填入 [起點][終點] 的位置中。由於是無向圖，矩陣必然會是以主對角線為對稱；對角線填 0，未相連的邊通常以 $\infty$ 符號或 0 表示（以 $\infty$ 為佳，符合最短路徑演算法之實作）。
小題 (二)
不考慮權重，從節點 g 開始並按照字母順序對 G 進行廣度優先尋訪（Breadth-First Search, BFS），請繪出尋訪完後所產生的 BFS 樹（BFS Tree）。（5 分）
思路引導 VIP
看到此題應先釐清圖形中各個節點的連線關係，並將每個節點的相鄰節點按字母順序排列。接著，利用佇列（Queue）先進先出的特性，從起點 g 開始進行廣度優先尋訪（BFS），逐步推導並記錄新發現的節點以形成 BFS 樹枝邊。
小題 (三)
請利用 Prim's 演算法，從節點 d 起始，找出一個最小擴張樹（Minimum Spanning tree），請以圖示方式一步步畫出過程與結果，並說明 Prim's 演算法的時間複雜度。（10 分）
思路引導 VIP
遇到這類圖形與演算法追蹤題，第一步先確認圖中的節點與邊權重（若文字描述與圖形有出入，以圖形為主並在作答時註明）。接著依據 Prim's 演算法「從已選節點集合向外尋找權重最小且不形成迴圈的邊」的核心邏輯，逐步列出每一次選取的邊與更新後的節點集合。最後，針對時間複雜度，必須根據不同資料結構的實作方式（如陣列、Min-Heap、Fibonacci Heap）分別說明，以展現理論觀念的完整與深度。