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

核心觀念
本題測試的是「費波那契數列的遞迴定義」與「由定義逐步推導出第 $n$ 項的能力」。掌握遞迴關係 $F(i+2)=F(i)+F(i+1)$，即可以簡單的迭代方式依序求出目標值。

---

解題過程

1. 確認已給出的前幾項

$F(0)=0,\quad F(1)=1,\quad F(2)=1,\quad F(3)=2,\quad F(4)=3$

2. 套用遞迴公式
   依題目遞迴式 $F(i+2)=F(i)+F(i+1)$，從已知的 $F(4)$ 開始往後算：

   • $i=3$ 時

$F(5)=F(3)+F(4)=2+3=5$

• $i=4$ 時

$F(6)=F(4)+F(5)=3+5=8$

核心觀念

本題考查最大堆積（max-heap）的插入與上濾（heapify-up）操作。

最大堆積必須符合：

$$\text{父節點} \geq \text{子節點}$$

以陣列儲存堆積時，若採用從 $0$ 開始的索引：

• 父節點索引：$\left\lfloor \dfrac{i-1}{2} \right\rfloor$
• 左子節點索引：$2i+1$
• 右子節點索引：$2i+2$

插入新元素時，先將元素放在陣列最後，再依序與父節點比較；若新元素較大，就向上交換，直到恢復最大堆積性質。

解題方法

原最大堆積為：

$$[16,14,10,8,7,9,3,2,4,1]$$

將 $13$ 放到陣列最後：

$$[16,14,10,8,7,9,3,2,4,1,13]$$

新元素 $13$ 位於索引 $10$，其父節點索引為：

$$\left\lfloor \frac{10-1}{2} \right\rfloor = \left\lfloor \frac{9}{2} \right\rfloor =4$$

索引 $4$ 的元素為 $7$。因為：

$$13>7$$

因此交換 $13$ 與 $7$：

$$[16,14,10,8,13,9,3,2,4,1,7]$$

此時 $13$ 位於索引 $4$，其父節點索引為：

核心觀念

本題考查 Quicksort 的：

• Partition 分割方式與排序方向
• 穩定排序（stable sort）的定義
• 最差時間複雜度分析

此程式選取最後一個元素 $A[r]$ 作為 pivot，並將所有小於等於 pivot 的元素移到左側，因此完成分割後：

$$A[p \ldots q-1] \le A[q] \le A[q+1 \ldots r]$$

其中 $q$ 是 pivot 最終所在的位置。遞迴處理左右兩個子陣列後，整體結果為非遞減排序。

解題方法

判斷各選項是否符合此 Quicksort 的性質：

1. 觀察 Partition 使用的比較運算，判斷排序方向。
2. 檢查交換操作是否保證相等元素的相對順序。
3. 分析 pivot 每次都落在極端位置時的遞迴時間。

當輸入已接近排序完成，且每次選到的 pivot 都是最小值或最大值時，分割結果會極度不平衡：

$$T(n)=T(n-1)+\Theta(n)$$

因此：

$$T(n)=\Theta(n+n-1+\cdots+1)=\Theta(n^2)$$

選項分析

(A) The output of Quicksort() is a non-increasing sorted sequence.

錯誤。

程式在第 4 行使用：

if A[j] <= x

小於等於 pivot 的元素被放到左側，大於 pivot 的元素位於右側，所以結果是非遞減排序：

$$A[1]\le A[2]\le \cdots \le A[n]$$

在 Partition 的 Lomuto 實作中，最後一次交換會把基準值 $pivot=A[r]$ 放到最終位置 $q=i+1$。
於第 8 行列印的子陣列 $A[p:r]$（含基準值）必須滿足：

• 所有 $\le pivot$ 的元素出現在基準值左側，
• 所有 $>pivot$ 的元素出現在基準值右側。

以題目給出的元素集合 $\{11,12,19,6,13\}$ 而 $pivot$ 為最後的 $13$，唯一會違反上述順序的是把 $19$（唯一大於 $13$ 的元素）置於任何小於等於 $13$ 的元素之前。

核心觀念

本題考查以均勻分布產生隨機排列（uniform random permutation），以及陣列索引範圍的推導。

在第 $i$ 次迴圈中，題目要求：

$$i \leq j < n$$

程式設定：

$$j=i+\text{Uniform}(m)$$

其中 Uniform(m) 會均勻產生：

$$0,1,2,\ldots,m-1$$

解題方法

為使 $j$ 的可能範圍涵蓋 $i$ 到 $n-1$，令：

$$m=n-i$$

則：

$$\text{Uniform}(n-i)\in\{0,1,\ldots,n-i-1\}$$

因此：

$$j=i+\text{Uniform}(n-i)$$

其範圍為：

• 最小值：$j=i+0=i$
• 最大值：$j=i+(n-i-1)=n-1$

完全符合 $i\leq j<n$，且每個合法索引都有相同機率被選到。

關鍵程式碼

核心觀念

本題考查陣列的隨機排列（random permutation），採用 Fisher–Yates shuffle 的交換方式：

for i = 0 to n-2
    j = 隨機選取的索引，且 i ≤ j < n
    swap(A[i], A[j])

每一輪固定目前位置 $i$，再將 $A[i]$ 與指定位置 $A[j]$ 交換。

---

解題方法

初始陣列為：

$$A=[1,2,3,4,5,6]$$

依序套用題目給定的 $(i,j)$：

步驟	交換內容	陣列結果
初始	—	$[1,2,3,4,5,6]$
$i=0,\ j=4$	交換 $A[0]$ 與 $A[4]$	$[5,2,3,4,1,6]$
$i=1,\ j=3$	交換 $A[1]$ 與 $A[3]$	$[5,4,3,2,1,6]$
$i=2,\ j=2$	自己與自己交換	$[5,4,3,2,1,6]$
$i=3,\ j=5$	交換 $A[3]$ 與 $A[5]$	$[5,4,3,6,1,2]$

核心觀念

本題考查以陣列實作堆疊（stack）時，push 操作的時間複雜度。

堆疊遵守「後進先出」（LIFO, Last In First Out），新增元素時一律放在堆疊頂端。陣列式堆疊通常以變數 top 記錄目前頂端位置，因此新增元素只需：

1. 將元素放入 top 的下一個位置。
2. 更新 top。

這些操作都只執行固定次數，與堆疊中元素數量 $n$ 無關。

解題方法

假設陣列尚有可用空間，push 的概念程式碼如下：

push(x):
    top = top + 1
    stack[top] = x

每個步驟皆為固定時間：

$$T(n)=c_1+c_2=O(1)$$

因此，將新元素推入具有 $n$ 個元素的陣列式堆疊，時間複雜度為：

$$\boxed{O(1)}$$

選項分析

• (A) $O(1)$：正確

核心觀念

最小生成樹會連接圖中的所有頂點，且不形成環；若圖有 $n$ 個頂點，生成樹恰有 $n-1$ 條邊。Prim 演算法從指定頂點開始，每一步都選擇「已加入頂點集合」與「尚未加入頂點」之間權重最小的邊。

解題方法

從頂點 $a$ 開始。圖中的邊權重為：$a-b=10$、$a-c=11$、$a-d=21$、$b-d=11$、$c-d=6$。

1. 目前只有 $a$，可選邊中最小的是 $a-b$，權重為 $10$。
2. 已加入 $\{a,b\}$，連往未加入頂點的邊中，最小權重為 $11$。可選 $a-c$ 或 $b-d$，兩者同權。
3. 加入其中一條權重 $11$ 的邊後，剩下的頂點可用 $c-d$ 連接，權重為 $6$。

因此最小生成樹的總權重為

核心觀念

完全圖 $K_n$ 是任意兩個不同頂點之間皆有一條邊的圖。

生成樹（spanning tree）必須同時符合：

• 包含原圖的全部頂點；
• 連通；
• 不含任何 cycle；
• 若有 $n$ 個頂點，必定有 $n-1$ 條邊。

本題的圖為完全圖 $K_4$，可使用凱萊公式（Cayley’s formula）：

$$K_n\text{ 的生成樹數量}=n^{n-2}$$

解題方法

令 $n=4$，代入凱萊公式：

$$4^{4-2}=4^2=16$$

因此，具有 $4$ 個頂點的完全圖共有 $16$ 棵生成樹。

選項分析

核心觀念

函式名稱後面有沒有括號，會決定程式是呼叫函式，還是只提到函式本身：

• do_job(); 會呼叫 do_job。
• do_job; 是一個沒有實際作用的運算式敘述，不會呼叫函式。

此外，return 0; 是讓 main 回傳狀態碼 $0$，不會把字元 0 印到螢幕上。要輸出文字，必須使用輸出函式。

解題方法

逐行檢查 main：

int main()
{
    do_job;
    return 0;
}

第 7 行沒有呼叫括號，因此不會進入 do_job。雖然 do_job 函式本身包含遞迴呼叫，但只有執行 do_job() 時才會開始遞迴。

核心觀念

最大二元堆積（max binary heap）必須同時滿足：

1. 結構為完全二元樹。
2. 每個節點的鍵值都不小於其子節點：

$$\text{parent} \geq \text{left child},\qquad \text{parent} \geq \text{right child}$$

以陣列採 1-based indexing 表示時：

• 第 $i$ 個節點的父節點位置為：

$$\left\lfloor \frac{i}{2} \right\rfloor$$

• 左子節點位置為 $2i$
• 右子節點位置為 $2i+1$

因此，只要逐一檢查每個父節點與其子節點的大小關係即可。陣列長度皆為 $9$，其對應的完全二元樹如下：

             a[1]
          /         \
       a[2]         a[3]
      /    \        /    \
   a[4]  a[5]    a[6]  a[7]
   /  \
a[8] a[9]

實際上只需檢查位置 $1$ 到 $\left\lfloor 9/2 \right\rfloor=4$ 的節點。

---

選項分析

（A）$\{9,16,3,2,4,8,5,14,12\}$

根節點為 $9$，其左子節點為 $16$：

$$9<16$$

父節點小於子節點，違反最大堆積的條件，因此不是 max binary heap。

（A）錯誤。

---

（B）$\{16,9,14,8,5,12,2,4,3\}$

逐一檢查父節點：

• 位置 $1$：$16\geq 9,14$
• 位置 $2$：$9\geq 8,5$
• 位置 $3$：$14\geq 12,2$

使用堆疊只能產生 stack‑sortable 的排列，等價於避免模式 $231$。
依序模擬 push A、B、C、D 的過程：

• ACBD：A 立即 pop，接著 push B、C、pop C，再 pop B，最後 push D、pop D → 可行
• CDBA：push A、B、C，pop C → C；push D，pop D → D；此時堆疊為 A、B，依序 pop B、A → 可行

搜尋二元搜尋樹的過程必須遵守：

• 若欲找之鍵 $k$ 小於目前節點值 $v$，則必須往左子樹走，下一個被檢查的節點必須 $<v$
• 若 $k>v$，則往右子樹走，下一個節點必須 $>v$

以 $k=101$ 為例，逐筆檢查每個序列：

序列	判斷	是否違背規則
A 20 → 252 → 41 → 49 → 130 → 120 → 131 → 101	在節點 120 時 $101<120$，應往左走，卻出現 $131>120$（右子節點）	違背

核心觀念

本題考查不同資料結構的「資料元素存取時間複雜度」。

若能直接根據索引、雜湊值或固定位置取得資料，所需步驟與資料量 $n$ 無關，時間複雜度為：

$$O(1)$$

各資料結構的典型存取複雜度如下：

資料結構	典型存取方式	時間複雜度
Stack	存取頂端元素（top）	$O(1)$
Linked list	依序尋找第 $i$ 個元素	$O(n)$
Array	依索引直接存取	$O(1)$
Hash table	依 key 查找，平均情況	$O(1)$
AVL tree	依鍵值搜尋	$O(\log n)$

其中，Hash table 的 $O(1)$ 是平均時間；若發生大量碰撞，最壞情況可能退化為 $O(n)$。

解題方法

判斷每個選項是否具有 $O(1)$ 存取時間，關鍵在於：

1. 是否能直接定位資料元素。
2. 是否需要從頭逐一尋找。
3. 若為樹結構，搜尋高度是否會隨 $n$ 增加。

能直接定位或存取固定位置者，通常為 $O(1)$；必須沿著鏈結或樹的路徑尋找者，通常至少為 $O(\log n)$ 或 $O(n)$。

選項分析

(A) Stack

Stack 遵守後進先出（LIFO, Last In First Out）原則，資料的標準存取位置是頂端：

• push：將元素放入頂端。
• pop：移除頂端元素。
• top 或 peek：查看頂端元素。

只要維護一個 top 指標，這些操作都只需固定次數的指標移動或陣列存取，因此時間複雜度為：

$$O(1)$$

所以在資料結構的標準操作定義下，(A) 正確。

補充而言，若題目要求任意存取 Stack 中間的元素，則必須先移除或逐層經過上方元素，不能視為 $O(1)$。本題採用 Stack 的標準頂端存取定義。

(B) Linked list

Linked list 的節點通常只知道下一個節點的位置。若要取得第 $i$ 個元素，必須從頭節點開始逐一走訪：

判斷要點

• 從左至右讀取；遇到運算子時必須先有足夠的運算元在堆疊中。
• 完全讀完後堆疊只能剩一個值，才是合法的 postfix 表達式。

各選項檢驗

選項	步驟概述	結果
(A) ABC*+	推入 A,B,C → * 消費 B,C → + 消費 A 與 B*C	合法

先列出所有有向邊

$A\to B,\;A\to D,\;C\to A,\;C\to E,\;C\to F,\;D\to C,\;F\to D$

檢查每個選項是否能形成有向環（循環）：

• ABC：需 $A\to B$, $B\to C$, $C\to A$
  $B\to C$ 不存在 → 不是環。

• ABD：需 $A\to B$, $B\to D$, $D\to A$
  $B\to D$、$D\to A$ 均不存在 → 不是環。

核心觀念

線性資料結構（linear data structure）是指資料元素依序排列，除了第一個與最後一個元素外，每個元素都具有唯一的前驅與唯一的後繼。其邏輯關係可表示為：

$$a_1 \rightarrow a_2 \rightarrow a_3 \rightarrow \cdots \rightarrow a_n$$

常見的線性資料結構包括：

• Array（陣列）
• Linked list（鏈結串列）
• Stack（堆疊）
• Queue（佇列）

Binary tree（二元樹）則屬於非線性資料結構，因為一個節點可能同時連接到兩個子節點，資料關係呈現階層狀，而非單一路徑。

解題方法

判斷每個選項的資料元素是否形成「單一路徑的先後關係」：

1. 若每個元素最多只有一個直接前驅與一個直接後繼，屬於線性資料結構。
2. 若資料具有分支、階層或一對多的關係，屬於非線性資料結構。

選項分析

(A) Stack

Stack（堆疊）是線性資料結構，遵循後進先出（Last In, First Out, LIFO）原則。

元素雖然只能從堆疊頂端加入或移除，但所有元素仍排列在單一序列中：

$$a_1 \rightarrow a_2 \rightarrow \cdots \rightarrow a_n$$

因此正確。

(B) Queue

Queue（佇列）是線性資料結構，遵循先進先出（First In, First Out, FIFO）原則。

元素從尾端加入、從前端移除，但資料元素仍維持單一線性順序，因此正確。

(C) Linked list

核心觀念

單向鏈結串列（singly linked list）的每個節點通常包含：

1. 資料欄位 data
2. 指向下一個節點的指標 next

節點結構可表示為：

$$\text{Node} = (\text{data},\ \text{next})$$

雙向鏈結串列（doubly linked list）則多一個指向前一個節點的指標 prev：

$$\text{Node} = (\text{data},\ \text{prev},\ \text{next})$$

因此，單向鏈結串列的主要特性是：

• 每個節點只需儲存一個連結指標，記憶體使用量較少。
• 只能沿著 next 指標由前往後走訪。
• 不支援以索引直接存取第 $i$ 個元素。
• 插入與刪除的效率取決於是否已知適當的前置節點或位置指標，不能一概而論為比雙向鏈結串列更快。

解題方法

逐一檢查各選項是否符合單向鏈結串列的定義與操作特性：

• 比較節點需要儲存的指標數量，可判斷記憶體使用量。
• 觀察是否具有 prev 指標，可判斷能否反向走訪。
• 比較插入、刪除時尋找前置節點的成本，可判斷時間效率。
• 判斷是否能透過索引直接定位節點，可判斷是否支援隨機存取。

選項分析

(A) They use less memory than doubly linked lists

正確。

單向鏈結串列每個節點只需要一個 next 指標；雙向鏈結串列每個節點需要 prev 與 next 兩個指標。

若有 $n$ 個節點，單向鏈結串列額外使用約 $n$ 個指標空間，雙向鏈結串列則約使用 $2n$ 個指標空間。因此，單向鏈結串列通常比雙向鏈結串列節省記憶體。

其空間複雜度皆為 $O(n)$，但單向鏈結串列的常數較小。

(B) They allow traversal in both directions

錯誤。

單向鏈結串列只有 next 指標，能從目前節點前往下一個節點：

$$v_i \rightarrow v_{i+1}$$

節點沒有指向前一個節點的 prev 指標，因此無法直接由目前節點回到前一個節點，也不能由尾端向前走訪。

能雙向走訪是雙向鏈結串列的特性。

解說

• A：雜湊表使用雜湊函數把鍵映射到陣列索引 → 正確。
• B：不同鍵可能得到相同雜湊值，稱為collision → 正確。

核心觀念

本題考查深度優先搜尋（Depth-First Search, DFS）的基本性質、應用範圍，以及與最短路徑、拓撲排序、旅行推銷員問題的關係。

DFS 的基本作法是：

1. 從一個起點出發。
2. 優先沿著尚未拜訪的鄰接節點深入。
3. 無法繼續深入時回溯。
4. 使用遞迴或堆疊記錄搜尋路徑。

若圖有 $V$ 個節點、$E$ 條邊，使用鄰接串列實作時，DFS 的時間複雜度為

$$O(V+E)$$

空間複雜度通常為

$$O(V)$$

其中包含拜訪標記、遞迴堆疊或明確使用的堆疊。

---

解題方法

判斷本題各選項時，依序檢查：

• 是否符合 DFS 的正式定義。
• DFS 是否保證該性質。
• 該問題是否確實能由 DFS 在指定複雜度內解決。
• 全部選項都正確時，選項 E 才會成立。

DFS 的核心特徵是「盡可能深入後再回溯」，但它並不根據邊數或路徑權重尋找最短路徑，也不具備解決所有最佳化問題的多項式時間能力。

---

選項分析

(A) DFS is a searching algorithm that visits all the nodes of a graph in a depth-first manner

正確。

DFS 是一種圖搜尋與圖走訪演算法，會以深度優先的方式拜訪節點：先沿著目前路徑不斷深入，直到沒有未拜訪的鄰接節點，再逐層回溯。

若圖為非連通圖，從單一起點執行 DFS 只能拜訪該起點所在的連通分量；完整的圖走訪會在 DFS 結束後，從其他尚未拜訪的節點重新啟動 DFS，形成 DFS forest。因此在圖搜尋的標準定義下，DFS 能拜訪圖中的所有節點。

---

(B) DFS always finds the shortest path between two nodes in a graph

錯誤。

DFS 不保證找到兩個節點之間的最短路徑。它只按照某一條路徑深入到底，再進行回溯；第一次找到目標節點時，該路徑可能不是最短路徑。

例如，圖中從起點 $S$ 到終點 $T$ 有兩條路徑：

• $S \to A \to B \to T$，長度為 $3$
• $S \to C \to T$，長度為 $2$

若 DFS 先探索 $A$，可能先找到長度為 $3$ 的路徑，卻沒有找到最短路徑。

在無權圖中，保證邊數最少路徑的演算法是廣度優先搜尋（BFS）；在帶有非負權重的圖中，通常使用 Dijkstra 演算法。DFS 本身沒有最短路徑保證。

---

核心觀念

本題比較兩種排序法：

• Insertion Sort（插入排序）：逐一取出元素，將其插入前方已排序區間。
• Merge Sort（合併排序）：採用分治法，先將陣列遞迴切半排序，再利用 Merge 合併兩個已排序子陣列。

相關定義：

• In-place sorting：主要在原陣列內 rearrange 元素，只使用 $O(1)$ 額外儲存空間。
• Merge Sort 的合併階段通常需要額外陣列暫存元素。
• Big-O 用來表示輸入規模增加時，時間或記憶體需求的漸近上界。

解題方法

(A) 哪一個是 in-place sorting algorithm？

Insertion Sort 將元素直接在原陣列中向右移動，再插入正確位置，只需使用少量暫存變數，因此屬於 in-place sorting algorithm。

標準 Merge Sort 在合併兩個已排序子陣列時，通常需要建立暫存陣列，將合併結果寫回原陣列，因此不屬於標準的 in-place sorting algorithm。

答案：Insertion Sort。

補充：

• Insertion Sort 額外空間：$O(1)$
• Merge Sort 額外空間：$O(n)$

題目採用一般教科書的 Merge Sort 定義；雖然存在特殊的原地合併技術，但不屬於標準實作。

(B) Merge Sort 的記憶體成本

令輸入陣列大小為 $n$。

Merge Sort 的合併階段需要額外配置暫存陣列，最多須暫存與目前處理區間同等數量的元素，因此額外陣列需要：

$$O(n)$$

遞迴呼叫堆疊深度為：

$$O(\log n)$$

合併陣列的空間成本會主導遞迴堆疊成本，因此總記憶體成本為：

$$O(n)+O(\log n)=O(n)$$

答案：$O(n)$。

(C) Merge(A,p,q,r) 虛擬碼

已知：

• $A[p:q]$ 已由小到大排序
• $A[q+1:r]$ 已由小到大排序
• 目標是將兩者合併，使 $A[p:r]$ 由小到大排序

設：

$$n_1=q-p+1$$ $$n_2=r-q$$

建立兩個暫存陣列：

• $L[1:n_1]$ 儲存左半部
• $R[1:n_2]$ 儲存右半部

接著使用兩個索引分別指向 $L$ 與 $R$ 尚未取出的最小元素。每次比較兩者，將較小者寫回 $A$。

核心觀念

本題考查：

1. 在已排序的子陣列中使用二分搜尋尋找插入位置。
2. 穩定性（stable）：相同鍵值的新元素必須插在原有相同元素的後方。
3. 二分搜尋的時間複雜度為 $O(\log n)$。
4. 陣列索引從 $1$ 開始。

對於已排序的 $A[p:q]$，插入 key 時，應尋找第一個滿足

$$A[i] > key$$

的位置。若所有元素都小於或等於 key，則插入位置為 $q+1$。

不能尋找第一個 $A[i] \ge key$ 的位置，因為那會將新元素插在相同元素之前，破壞穩定性。

解題方法

使用「找第一個大於 key 的位置」的二分搜尋，即 upper_bound。

設定：

• left = p
• right = q+1

其中 q+1 是可能的插入位置，不必真的存取 $A[q+1]$。

每次取中間位置：

• 若 $A[mid] \le key$，表示 mid 的元素可以放在 key 前面，因此插入位置應在右側，令 left = mid+1。
• 若 $A[mid] > key$，表示 mid 可能是插入位置，令 right = mid。

當 left == right 時，即找到第一個大於 key 的位置。

二分搜尋虛擬碼

Binary-search(A, p, q, key)
    left  = p
    right = q + 1

    while left < right
        mid = floor((left + right) / 2)

        if A[mid] <= key
            left = mid + 1
        else
            right = mid

    return left

回傳值 left 即為插入位置 i。

配合題目中的 Insertion-sort2：

核心觀念

本題考查 Dijkstra 單源最短路徑演算法的正確流程。其核心定義如下：

• distance[v]：目前已知的 source 到頂點 $v$ 的最短距離估計值。
• previous[v]：最短路徑上，頂點 $v$ 的前一個頂點。
• $Q$：尚未確定最短距離的頂點集合。
• 每次從 $Q$ 中取出目前 distance 最小的頂點 $u$，將其視為已確定。
• 對 $u$ 的每個鄰居 $v$ 進行鬆弛（relaxation）：

$$\text{alternative} = \text{distance}[u]+w(u,v)$$

若

$$\text{alternative}<\text{distance}[v]$$

則更新：

$$\text{distance}[v]\leftarrow\text{alternative}$$

並令

$$\text{previous}[v]\leftarrow u$$

Dijkstra 演算法要求圖上的邊權重皆為非負數，即：

$$w(u,v)\geq 0$$

---

錯誤一：第 10 行應選擇最小距離，而非最大距離

原始程式：

u ← vertex in Q with max_distance[u]

錯誤原因：Dijkstra 的貪婪策略是每次選擇目前距離估計值最小的未處理頂點。因此應改為：

u ← vertex in Q with min_distance[u]

也就是選擇滿足下式的頂點：

$$u=\arg\min_{x\in Q}\text{distance}[x]$$

若選擇最大距離頂點，無法保證先確定的頂點已經是最短距離，演算法的正確性會失效。

---

錯誤二：第 13 行應使用加法，而非減法

原始程式：

alternative ← distance[u] - length(u, v)

錯誤原因：從 source 經由 $u$ 到達 $v$ 的路徑長度，應為目前到 $u$ 的距離加上邊 $(u,v)$ 的長度：

$$\text{alternative} = \text{distance}[u]+ \text{length}(u,v)$$

因此正確程式為：

alternative ← distance[u] + length(u, v)

使用減法會使邊長越大，計算出的路徑距離反而越小，與最短路徑的定義矛盾。

---

錯誤三：第 16 行的指定方向相反

原始程式：

u ← previous[v]

錯誤原因：當經由 $u$ 到達 $v$ 的路徑較短時，應記錄「$v$ 的前驅是 $u$」，而不是修改目前處理的頂點 $u$。

正確程式為：

previous[v] ← u

其意義為：

$$\text{previous}[v]=u$$

如此才能在演算法結束後，從目標頂點沿著 previous 陣列反向回溯出完整最短路徑。

---

其他程式行的判斷

第 6～7 行

if source!=v:
  add v to Q

此段邏輯正確，因為 source 的最短距離已知為 $0$，不需要先放入未處理集合 $Q$。其效果等同於：

Q ← all vertices in Graph except source

第 4～5 行

distance[v] ← INFINITY
previous[v] ← UNDEFINED

本題要求使用 Kruskal 演算法構建最小生成樹 (MST)，並計算其權重。

給定的圖如下：
頂點: {a, b, c, d, f, g} (共 6 個頂點)
邊及其權重:

• (a, f): 7
• (a, b): 23
• (b, d): 20
• (b, c): 19
• (d, f): 11
• (d, c): 15
• (f, g): 13
• (c, g): 9

Kruskal 演算法的步驟：

1. 將圖中所有的邊按權重從小到大排序。
2. 初始化一個空的 MST 集合，其中包含所有頂點但沒有邊。
3. 依序考慮排序後的邊：如果加入一條邊不會在 MST 中形成環，則將該邊加入 MST。
4. 重複步驟 3，直到 MST 包含 V-1 條邊（其中 V 是頂點數量）。

步驟 1: 邊按權重排序

1. (a, f): 7
2. (c, g): 9
3. (d, f): 11
4. (f, g): 13
5. (d, c): 15
6. (b, c): 19
7. (b, d): 20
8. (a, b): 23

步驟 2: 初始化 MST

• 頂點集合 V = {a, b, c, d, f, g}
• MST 邊集合 E' = {}
• 當前權重 W = 0
• 使用 Disjoint Set Union (DSU) 結構來檢查環。初始時，每個頂點都在自己的集合中。

步驟 3: 依序加入邊

1. 考慮邊 (a, f) 權重 7:

   • 頂點 a 和 f 不在同一個集合。
   • 加入邊 (a, f) 到 E'。
   • 合併 a 和 f 的集合。
   • E' = {(a, f)}, W = 7
   • 集合: {a, f}, {b}, {c}, {d}, {g}

2. 考慮邊 (c, g) 權重 9:

   • 頂點 c 和 g 不在同一個集合。
   • 加入邊 (c, g) 到 E'。
   • 合併 c 和 g 的集合。
   • E' = {(a, f), (c, g)}, W = 7 + 9 = 16
   • 集合: {a, f}, {b}, {c, g}, {d}

3. 考慮邊 (d, f) 權重 11:

   • 頂點 d 和 f 不在同一個集合（d 在 {d}，f 在 {a, f}）。