113 年 國立臺灣聯合大學系統（清華、政治、陽明交通、中央四校聯招）研究所電機類《資料結構》

核心觀念

此題考查「反轉對（inversion）」的定義，以及線性期望值。

對陣列中的一對位置 $(i,j)$，若 $i<j$ 且 $A[i]>A[j]$，則稱 $(i,j)$ 為反轉對。陣列共有

對不同的位置配對。

在隨機排列中，對任意固定的 $i<j$，$A[i]>A[j]$ 與 $A[i]<A[j]$ 的機率相同，因此形成反轉對的機率為

解題方法

對每一對位置 $(i,j)$ 定義指示變數：

反轉對總數 $X$ 可表示為所有位置配對的總和：

對固定的一對 $(i,j)$：

利用期望值的線性性，即使各對位置之間並非彼此獨立，仍有：

共有 $\binom{n}{2}$ 對位置，因此：

選項分析

核心觀念
此題屬於「相對位置」推理，重點在於利用已知的相對關係（前後、相鄰）逐步排除不符合條件的排列，最後判斷哪一個人無法出現在第 3 位。

(a) 解題步驟與推理

1. 列出已知條件

   • $A$ 站在 $C$ 後面 → $C$ 必在 $A$ 前方。
   • $B$ 不與 $D$ 相鄰。
   • $D$ 與 $E$ 互相相鄰 → $D$、$E$ 必連續站立，且可以是「$D$ 前 $E$」或「$E$ 前 $D$」。

2. 先處理相鄰條件
   把 $D$、$E$ 看成一個「相鄰組」$(DE)$ 或 $(ED)$，此組在隊列中佔兩個連續位置。

3. 考慮 $A$、$C$ 的相對順序
   只知道 $C$ 在 $A$ 前面，兩人之間可以隔任意人。

4. 檢驗每個人是否可能站在第 3 位
   我們逐一嘗試把每個人放在第 3 位，並檢驗是否能滿足所有條件。

   • 把 $A$ 放第 3 位
     需要 $C$ 在 $A$ 前面，即 $C$ 必在第 1 或第 2 位。
     同時 $D$、$E$ 必相鄰，剩下的兩個位置（第 4、5 位）可以容納 $(DE)$ 或 $(ED)$，而 $B$ 則放在剩下的空位。
     只要 $B$ 不與 $D$ 鄰近即可。若 $(DE)$ 位於第 4、5 位，則 $B$ 只能在第 1、2 位之一，與 $D$ 不相鄰。
     結論：$A$ 可以是第 3 位。

   • 把 $B$ 放第 3 位
     $B$ 不與 $D$ 相鄰，故 $D$ 必不在第 2、4 位。
     因 $D$、$E$ 必連續，唯一可容納的情形是 $(DE)$（或 $(ED)$）佔第 1、2 位或第 4、5 位。

     • 若 $(DE)$ 在第 1、2 位，則 $D$ 在第 2 位，與 $B$（第 3 位）相鄰，違反條件。
     • 若 $(DE)$ 在第 4、5 位，則 $D$ 在第 4 位，同樣與 $B$ 相鄰。
       因此無法安排 $B$ 為第 3 位。

核心觀念

本題考查各種排序法的最壞情況時間複雜度。若輸入資料筆數為 $n$，比較各演算法在最不利輸入下的執行時間：

• Merge Sort：$O(n\log n)$
• Quick Sort：最壞為 $O(n^2)$
• Heap Sort：$O(n\log n)$
• Radix Sort：通常為 $O(d(n+k))$，其中 $d$ 為位數，$k$ 為每一位的取值範圍

其中，$O(n^2)$ 的成長速度高於 $O(n\log n)$；在固定資料格式與位數下，Radix Sort 通常可視為接近線性時間。

解題方法

直接比較各選項的最壞情況複雜度：

因此，只要某演算法的最壞情況為 $O(n^2)$，便會高於最壞情況為 $O(n\log n)$ 或線性級別的演算法。

Quick Sort 在每次分割都極度不平衡時，例如每次選到的 pivot 都是目前資料中的最小值或最大值，遞迴規模會形成：

其總比較次數為：

所以 Quick Sort 的最壞情況時間複雜度是 $O(n^2)$。

選項分析

(A) Merge Sort

Merge Sort 每一層將資料分成兩半，遞迴深度為 $O(\log n)$；每一層合併所有元素需花費 $O(n)$，因此：

由遞迴樹或主定理可得：

最壞情況不是 $O(n^2)$，故不是答案。

(B) Quick Sort

核心觀念

本題考查排序演算法的「額外記憶體空間複雜度」，也就是除了原始輸入陣列之外，演算法執行時額外使用的記憶體。

常見排序法的額外空間如下：

• Insertion Sort：$O(1)$
• Selection Sort：$O(1)$
• Merge Sort：$O(n)$
• Heap Sort：$O(1)$

其中，$n$ 表示待排序資料筆數。

解題方法

逐一比較各排序法是否需要建立與原陣列同等規模的暫存區：

Merge Sort 採用分割與合併策略。合併兩個已排序子陣列時，通常需要額外配置暫存陣列保存合併結果，其大小與資料筆數成正比，因此：

Merge Sort 的遞迴呼叫堆疊通常為 $O(\log n)$，但相較於合併所需的 $O(n)$ 暫存陣列，主要空間複雜度仍為：

其餘三種演算法通常可直接在原陣列內交換或搬移元素，不需要建立大型暫存陣列，因此額外空間為 $O(1)$。

選項分析

(A) Insertion Sort

Insertion Sort 將目前元素插入前方已排序區段，主要使用少量變數保存待插入元素，並在原陣列內搬移資料。

因此額外空間為：

本題考驗對鏈結串列反轉 (reversing a linked list) 演算法的理解，特別是當使用指標傳遞指標 (pointer to pointer) 時，如何更新鏈結串列的頭指標。

核心觀念：
在 C 語言中，如果函數需要修改傳入的指標所指向的內容 (例如，修改頭指標 head 所指向的節點)，就必須傳入該指標的指標 (pointer to pointer)。
鏈結串列反轉的核心邏輯是迭代地將每個節點的 next 指標指向前一個節點。迭代結束後，prev 指標會指向原鏈結串列的最後一個節點，也就是反轉後的新頭節點。

解題過程：
函數 reverse 的參數是 struct node ** head，這表示 head 是一個指向 struct node* 型別指標的指標。這意味著函數可以透過 *head 來存取並修改原始呼叫者傳入的頭指標。

演算法的迭代部分已經正確地完成了鏈結串列的反轉：

• prev 初始化為 NULL，最終會指向反轉後鏈結串列的頭節點 (原鏈結串列的尾節點)。
• current 初始化為 *head，即原鏈結串列的頭節點，並在迴圈中逐一移動。
• next 用於暫存 current->next，以便在修改 current->next 後仍能移動到下一個節點。
• 迴圈 while (current != NULL) 結束時：
  • current 會變成 NULL (因為它是最後一個節點的下一個節點)。
  • prev 會指向原鏈結串列的最後一個節點，也就是反轉後的新頭節點。

核心觀念

Quick Sort 的 partition（分割）會選定一個 pivot，將陣列重新排列，使 pivot 位於分割後的最終位置，並滿足：

本題所有元素互異，因此可直接使用嚴格大小關係判斷。左右兩側的元素不必維持原本順序。

分割後陣列為：

解題方法

逐一檢查各選項所指定的數字，是否能作為分割後的位置基準。

若某數字是 pivot，則它左邊不能出現比它大的元素，右邊不能出現比它小的元素。

選項分析

(A) pivot could be 6：錯誤

$6$ 位於第二個位置，左側有 $7$：

左側出現比 pivot 大的元素，不符合 partition 的條件，因此 $6$ 不可能是 pivot。

(B) pivot could be 9：正確

$9$ 左側為 $7,6$：

$9$ 右側為 $20,12,15,11$：

核心觀念

穩定排序（stable sorting）的定義是：

若兩個元素的排序鍵值相等，排序後仍維持它們在原始資料中的先後相對順序。

例如，原始陣列中有：

以分數為排序鍵進行遞增排序後，結果為：

因為 $A$ 與 $C$ 的分數相同，且排序後仍維持 $A$ 在 $C$ 之前，所以此排序符合穩定性。

穩定性只關心「鍵值相等的元素」之間的相對順序，與排序時間複雜度、額外空間需求，以及是否採用分治法無直接關係。

解題方法

判斷選項是否描述穩定排序的定義即可。題幹中的關鍵語句是：

maintains the relative order of equal elements

其意思是「維持相等元素原本的相對順序」，正好符合穩定排序的正式定義，因此正確答案為 (C)。

選項分析

(A) It requires $O(n^2)$ extra space for sorting.

此敘述錯誤。

$O(n^2)$ 額外空間描述的是排序演算法的空間複雜度，與穩定性沒有關係。穩定排序可以使用 $O(1)$ 額外空間，也可以使用 $O(n)$ 額外空間。

例如：

• Insertion sort 通常可視為穩定排序，額外空間為 $O(1)$。
• Merge sort 通常為穩定排序，額外空間為 $O(n)$。

因此，是否需要 $O(n^2)$ 額外空間不能用來定義穩定排序。

(B) It employs a divide and conquer strategy for sorting.

此敘述錯誤。

Divide and conquer（分治法）是演算法設計策略，不是穩定排序的判斷條件。

核心觀念

本題考查圖形的深度優先搜尋（Depth-First Search, DFS）。

程式的主要流程為：

1. 將目前節點加入 visited。
2. 立即輸出目前節點。
3. 依照 graph[start] 中鄰居的排列順序逐一檢查。
4. 若鄰居尚未造訪，便遞迴執行 DFS。
5. 某節點所有鄰居都造訪完畢後，才返回上一層。

因此，遍歷順序不只取決於圖的結構，也取決於鄰接串列中的排列順序。

解題方法

從節點 A 開始，依程式執行順序追蹤：

1. 從 A 開始

A 尚未造訪：

• 加入 visited
• 輸出 A
• 鄰居依序為 B、C

目前順序：

$A$

接著先走 B。

2. 走訪 B

B 尚未造訪：

• 加入 visited
• 輸出 B
• 鄰居依序為 D、E

目前順序：

$AB$

接著先走 D。

3. 走訪 D

D 尚未造訪：

• 加入 visited
• 輸出 D
• D 沒有鄰居

目前順序：

$ABD$

返回 B，繼續檢查 E。

4. 走訪 E

E 尚未造訪：

• 加入 visited
• 輸出 E
• 鄰居為 F

目前順序：

$ABDE$

接著走 F。

5. 走訪 F

F 尚未造訪：

• 加入 visited
• 輸出 F
• F 沒有鄰居

目前順序：

$ABDEF$

返回 E，再返回 B，最後返回 A。

6. 回到 A 檢查 C

A 的下一個鄰居是 C，且 C 尚未造訪，因此走訪 C：

本題考驗對圖搜尋演算法的識別能力。題目要求識別第 10 題 (實際上是第 8 題的程式碼) 所實現的搜尋概念。

核心觀念：
圖搜尋演算法主要有兩種：廣度優先搜尋 (Breadth-First Search, BFS) 和深度優先搜尋 (Depth-First Search, DFS)。

• BFS 通常使用佇列 (queue) 來實現，它會逐層地探索圖，先訪問離起始節點最近的節點。
• DFS 通常使用堆疊 (stack) 或遞迴 (implicit stack) 來實現，它會盡可能深地探索圖的一個分支，然後回溯。

解題過程：
我們需要檢查第 8 題提供的 Python 程式碼的結構，判斷它屬於哪種搜尋概念。

第 8 題的程式碼：

def search(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=' ')
    for neighbor in graph[start]:
        if neighbor not in visited:
            search(graph, neighbor, visited) # 遞迴呼叫

觀察程式碼的關鍵部分：

1. 遞迴呼叫： search(graph, neighbor, visited) 是一個遞迴呼叫。遞迴本身就是一種利用堆疊 (系統堆疊) 來實現的機制。

在無向樹中，邊的數量恆等於頂點數減一：

$|E| = |V|-1$

題目給定 $|V| = 10$，因此任何包含 10 個頂點的樹必有

核心觀念

單向鏈結串列中，每個節點的 next 指標最多只能指向一個節點，但同一個節點可以被多個節點指向。因此：

• 出度（out-degree）最多為 $1$；
• 入度（in-degree）可以大於 $1$；
• 若不同鏈結串列中的節點指向同一節點，兩條串列會在該節點合併，形成相交結構；
• 若沿著 next 指標再次回到已經走過的節點，則形成迴圈（loop），也稱循環串列結構（cyclical list structure）。

所以，「兩個節點的 next 指標指向同一節點」本身並不違反單向鏈結串列的指標規則。

解題方法

觀察兩個節點 $u$、$v$ 滿足：

接著分別判斷後續結構：

1. 若從 $x$ 開始繼續走，最後回到已經走過的節點，會形成迴圈。
2. 若 $u$、$v$ 分別來自兩條鏈結串列，且共同指向 $x$，兩條串列會在 $x$ 處相交。
3. 若兩條串列必須保持完全獨立，則不可能共享同一個後繼節點。

因此可行的結構包括「有迴圈」以及「兩條串列相交」。

選項分析

(A) There are two normal singly linked lists

錯誤。若兩個節點的 next 指標指向同一個節點，兩條鏈結串列便共享後續節點，不再是兩條彼此獨立、互不相交的正常單向鏈結串列。

這種情況應歸類為「兩條單向鏈結串列相交」，而不是兩條完全獨立的正常串列。

(B) There is a loop in the linked list

正確。若共同指向的節點後續又沿著 next 指標回到先前節點，就會形成迴圈。例如：

從 $A$ 出發會形成：

核心觀念

本題考查：

• 堆疊的 後進先出（LIFO） 特性。
• 使用另一個堆疊進行排序的插入排序概念。
• 最佳、最差時間複雜度與空間複雜度。
• 判斷「堆疊排序方向」時，必須明確區分「由堆疊頂端往下」的順序。

程式會將元素逐一從 $S1$ 取出，插入到已排序的 $S2$ 中：

tmp = S1.pop();

while (!S2.isEmpty() && S2.peek() > tmp) {
    S1.push(S2.pop());
}

S2.push(tmp);

當 $S2$ 的頂端元素大於 tmp 時，便將較大的元素移回 $S1$，直到 tmp 可以放入正確位置。因此，處理完成後，$S2$ 的堆疊頂端是最小值，往下依序變大。

解題方法：判斷排序方向

假設輸入元素為 $3,1,2$，並以堆疊頂端先被取出的順序表示。

1. 取出 $3$：

   $S2: 3$

2. 取出 $1$：

   因為 $S2.peek()=3>1$，先將 $3$ 移回 $S1$，再放入 $1$：

   $S2: 1$

3. 再取出 $3$：

   因為 $S2.peek()=1>3$ 不成立，直接放入：

   $S2: 3,1$

4. 取出 $2$：

   因為 $S2.peek()=3>2$，移出 $3$；此時頂端為 $1$，不再大於 $2$，放入 $2$：

   $S2: 2,1$

此時由 $S2$ 頂端往下看為：

$2,1$

最後執行：

while (!S2.isEmpty()) {
    S1.push(S2.pop());
}

$S2$ 的元素會依序由小到大取出，並推入 $S1$。因此，較大的元素會最後被推入 $S1$，位於堆疊頂端。

最後 $S1$ 由頂端往下為：

$3,2,1$

所以此演算法使 $S1$ 的堆疊頂端到下方呈現遞減順序，也就是：

• 堆疊頂端到下方：降冪排列。
• 若將元素由底部取出觀察：升冪排列。

時間複雜度分析

外層迴圈每次從 $S1$ 取出一個元素，共執行 $n$ 次。

核心觀念

本題考查 Merge Sort 的下列性質：

1. 時間複雜度
2. 穩定性（stable）
3. 與 Quick Sort 的最壞情況比較
4. 額外空間複雜度

Merge Sort 的基本流程是：

1. 將陣列遞迴切成左右兩半。
2. 分別排序左右子陣列。
3. 將兩個已排序的子陣列合併。

其時間複雜度可由遞迴式表示：

其中 $2T(n/2)$ 代表排序左右兩半，$O(n)$ 代表合併全部元素。由主定理可得：

而且 Merge Sort 在最佳、平均、最壞情況下皆為：

解題方法

逐一套用 Merge Sort 的標準性質判斷：

• 時間複雜度：是否為 $O(n\log n)$。
• 穩定性：相同鍵值元素的相對順序是否能維持。
• 最壞情況：與 Quick Sort 的 $O(n^2)$ 比較。
• 額外空間：合併時是否需要暫存陣列，以及空間成長階數。

選項分析

(A) It has a worst-case time complexity of $O(n \log n)$.

正確。

Merge Sort 每一層遞迴都需處理總共 $n$ 個元素，而遞迴深度為：

因此總時間為：

即使輸入資料已經排序完成，Merge Sort 通常仍會執行完整的分割與合併流程，所以最壞情況時間複雜度為：

(B) It is not a stable sorting algorithm.

錯誤。

標準 Merge Sort 是穩定排序法。

在合併兩個已排序序列時，若左右兩邊目前元素的鍵值相同，優先取左邊元素，便能維持它們原本的相對順序。例如：

若先取 $L$ 中的 $(2,a)$，合併結果為：

因此只要合併程序正確處理相同鍵值，Merge Sort 就能保持穩定性。

(A) 正確：在最壞情況下所有鍵都落在同一鏈結桶，查詢、插入與刪除皆退化為 $O(n)$。
(B) 錯誤：雜湊函式應只依賴資料內容而非資料大小，大小不影響雜湊值。

核心觀念

本題比較三種圖形演算法：

• Dijkstra’s Algorithm：求單一起點到其他頂點的最短路徑。
• Prim’s Algorithm：求無向連通加權圖的最小生成樹（Minimum Spanning Tree, MST）。
• Kruskal’s Algorithm：以邊為單位，選取權重最小且不形成環的邊，求無向圖的最小生成樹。

最小生成樹必須建立在：

1. 無向圖；
2. 圖為連通圖；
3. 邊具有權重。

若圖不連通，Prim 或 Kruskal 得到的是最小生成森林，而非單一生成樹。

解題方法

逐一檢查每個敘述是否符合演算法的適用條件與功能：

1. Dijkstra 是否要求邊權重非負；
2. Kruskal 是否適用於有向圖；
3. Prim 選擇下一個頂點的依據；
4. Dijkstra 解決的是最短路徑還是最長路徑；
5. Prim 從任意起點開始是否仍能得到 MST。

選項分析

(A) Dijkstra's Algorithm operates on graphs with non-negative edge weights only.

正確。

Dijkstra 每次選取目前距離起點最近、且尚未確定的頂點，並將其距離視為最終最短距離。這項貪心策略成立的關鍵，是所有邊權重必須滿足：

若存在負權重邊，之後可能經由新的路徑使已確定的距離變得更短，導致 Dijkstra 的結果錯誤。

例如，若目前判定某頂點距離為 $5$，但稍後經過另一條路徑並使用負權重邊，可能得到距離 $3$，原本的貪心判定便不再可靠。

因此，Dijkstra 適用於邊權重非負的圖；若有負權重邊，通常使用 Bellman–Ford Algorithm。

(B) Kruskal's Algorithm guarantees finding a minimum spanning tree for both directed and undirected graphs.

錯誤。

Kruskal Algorithm 是用來求無向加權圖的最小生成樹。其主要步驟為：

1. 將所有邊依權重由小到大排序；
2. 依序選取目前最小的邊；
3. 若加入該邊不會形成環，則加入生成樹；
4. 使用 Union-Find 判斷兩個頂點是否已連通。

最小生成樹的定義本身是針對無向圖。一般有向圖不存在傳統意義下的 MST；有向圖若要尋找類似結構，通常討論的是最小成本有向生成樹，例如 directed minimum spanning arborescence，使用的演算法也不同。

因此，Kruskal 並不保證能對有向圖求得最小生成樹。

核心觀念

本題考查 Red-Black Tree（紅黑樹）的定義與平衡性質。紅黑樹是具有額外顏色標記的 Binary Search Tree，通常遵守以下規則：

1. 每個節點為紅色或黑色。
2. 根節點必須為黑色。
3. 所有外部葉節點（通常以 NIL 表示）為黑色。
4. 紅色節點的子節點必須為黑色，因此不能出現連續兩個紅色節點。
5. 從任一節點到其所有後代 NIL 葉節點的路徑，都包含相同數量的黑色節點，此數量稱為 black-height。

由於紅色節點不能連續，從根到葉的最長路徑至多為最短路徑的兩倍，因此紅黑樹高度為

其中 $n$ 為節點數量。

解題方法

逐一比對各敘述與紅黑樹的標準性質：

• 是否正確描述紅黑樹的平衡性？
• 是否符合紅黑樹的基本規則？
• 是否正確描述其資料結構與空間需求？

題目要求選出「錯誤」的敘述。

選項分析

(A) Red-Black Trees ensure a maximum height difference of 2 between any two leaf nodes.

錯誤。

紅黑樹並不是保證任意兩個葉節點的高度差最多為固定值 $2$。它真正保證的是：

• 任一路徑上的黑色節點數量相同。
• 最長根葉路徑長度不超過最短根葉路徑的兩倍。

若最短路徑長度為 $b$，最長路徑可能接近 $2b$，兩者的差距可隨樹高增加，並非固定不超過 $2$。

因此，紅黑樹提供的是對數高度保證，而不是「任意葉節點高度差最多為 2」的保證。

(B) They are a type of self-balancing binary search tree.

正確。

紅黑樹是一種自我平衡二元搜尋樹。插入或刪除節點後，透過重新著色與旋轉維持紅黑樹性質，使樹高維持在

核心觀念

主要群聚（primary clustering）是線性探測法中，連續已占用的表格位置逐漸形成長區塊的現象。區塊越長，新插入的元素越容易探測到並接在區塊末端，使群聚持續擴大。

解題方法

核心觀念

鏈結法（chaining）以每個雜湊表位置連接一條串列，發生碰撞的元素會存放在同一條串列中。負載因子定義為

其中 $n$ 是元素數量，$m$ 是雜湊表位置數量。假設雜湊函數能讓元素平均分散，每條串列的平均長度約為 $\alpha$。

解題方法

題目圖中第 2-(B) 題詢問：使用鏈結法處理碰撞，且假設雜湊函數良好時，搜尋操作的平均時間複雜度為何。搜尋時先計算雜湊位置，再檢查該位置的串列；

核心觀念

線性探測遇到碰撞時，會沿著雜湊表逐格往後找空位。負載因子 $\alpha$ 越接近 $1$，空格越少，連續佔用的區段越長，搜尋時需要探測的格數也越多；這種現象稱為主要群聚。

解題方法

圖中第 2-(C) 題問的是：使用線性探測的雜湊表中，當負載因子 $\alpha$ 趨近 $1$ 時，搜尋的平均時間複雜度如何變化。可用平均探測次數觀察其變化；在經典隨機假設下，成功與失敗搜尋的平均探測次數近似為：

核心觀念

這段程式實作的是 Prim 最小生成樹演算法。對一個連通、帶權重的無向圖，最小生成樹會連接所有頂點、沒有迴圈，且總邊權重最小。

Prim 演算法從一個起點開始，每次選擇一條連接「已加入生成樹的頂點」與「尚未加入的頂點」的最小權重邊，逐步擴展生成樹。

解題方法

圖中程式以 $V=5$ 表示圖有 5 個頂點，並以鄰接矩陣儲存邊權重；矩陣中的 $0$ 代表兩頂點之間沒有邊。程式從頂點 $0$ 開始，使用 key[] 記錄各未加入頂點目前可連接到生成樹的最小邊權重，並用 parent[] 記錄該邊連到的前一個頂點。

判斷依據如下：

• key[0] = 0：指定頂點 $0$ 為起點。
• minKey(key, mstSet)：從尚未加入生成樹的頂點中，找出 key 最小者。

核心觀念

程式以鄰接矩陣表示加權圖。矩陣中非零的 graph[i][j] 表示頂點 $i$ 與頂點 $j$ 之間有一條權重為該數值的邊；矩陣對稱，因此這是無向加權圖。對角線與其餘的 $0$ 表示沒有邊。

解題方法

從原卷程式讀到的矩陣是：

逐列整理非零項，並利用矩陣對稱性，每條無向邊只記一次：

• $0\text{--}1$，權重 $2$
• $0\text{--}3$，權重 $6$
• $1\text{--}2$，權重 $3$
• $1\text{--}3$，權重 $8$

核心觀念

這段程式實作 Prim 最小生成樹演算法。key[v] 記錄目前已納入生成樹的頂點到頂點 v 的最小邊權重；parent[v] 記錄這條最小邊連接的前一個頂點。mstSet[v] 表示頂點 v 是否已納入生成樹。

解題方法

圖中共有頂點 $0$ 到 $4$，由對稱的加權鄰接矩陣表示；矩陣中的 $0$ 代表沒有邊。程式從頂點 $0$ 開始，每輪選取 key 最小且尚未納入生成樹的頂點，再更新相鄰頂點的 key 與 parent。