圖演算法與設計策略：從相依關係到可證明步驟
本頁為依教材與考古題整理的原創摘要；考古題答案經技術覆核，但不是官方答案。
考古題證據邊界： im-it-ds-algorithm-design 在 canonical question metadata 中沒有 direct primary past-paper refs；im-it-ds-graphs 本課也只有 1 題內容完整且可直接使用的 topological-sort ref。112-26 題面破碎，已排除。其餘 graph 與 algorithm-design 內容是 reviewed MIT algorithms source 支撐的 foundational coverage，不宣稱歷屆高頻。
第一次接觸也沒關係
這堂先懂這些詞
先記住白話意思，不必急著背英文。看到正文時，再把正式名稱接回來。
演算法設計策略
也會看到：greedy、divide-and-conquer、dynamic programming、invariantGreedy 每步選眼前最佳，分治拆成獨立子題，動態規劃重用重疊子題答案。
- 生活例子：
- 像每次拿最大硬幣、分組各自整理、把算過的小問題寫在備忘錄。
- 別搞混：
- 看到最佳化問題不能直接套 greedy；必須證明局部選擇能導向全域答案。
大 O 複雜度
也會看到：Big O、time complexity、O(n)、時間複雜度描述輸入變大時，演算法所需時間或空間的成長速度。
- 生活例子：
- 排 10 人與排 1 萬人時，工作量增加多快比小規模快幾秒更重要。
- 別搞混：
- Big O 不是精確秒數，也不能忽略資料規模與常數成本。
拓樸排序、最短路徑與生成樹
也會看到：topological sort、shortest path、spanning tree、MST拓樸排序安排相依先後；最短路徑找兩點間最低成本；最小生成樹用最低總成本連通所有點。
- 生活例子：
- 排課先後、導航最快路線與最低成本鋪設全區網路，是三種不同問題。
- 別搞混：
- MST 不保證任意兩點間的路徑都是最短路徑。
圖的走訪
也會看到：BFS、DFS、breadth-first search、depth-first search、廣度優先、深度優先BFS 逐層探索，DFS 則沿一條路深入後再回頭。
- 生活例子：
- 找最近的朋友關係像 BFS，探索迷宮一條路到底像 DFS。
- 別搞混：
- 兩者走訪順序不同，適用問題與記憶體成本也不同。
用 BFS、DFS、topological sort、MST 與最短路徑建立圖問題辨識框架，再比較 greedy、divide-and-conquer 與 dynamic programming 的前提及正確性論證。
先抓住這幾件事
- 依目標選擇 BFS、DFS 或 topological sort
- 說明 spanning tree、MST 與 shortest path 的差異
- 區分 greedy、divide-and-conquer 與 dynamic programming
- 用 invariant、exchange argument 或 induction 描述正確性證據
先想像這個場景
校園活動排程與網路佈線
學生會要排有先修關係的活動、找校園各點的最低總佈線成本，還要設計在尖峰前完成的演算法。三個問題都畫成圖，卻不能用同一個答案。
先別急著往下看，花十秒想一想：
若活動相依圖出現 A 等 B、B 又等 A，排程表能否靠換順序解決？最低總佈線是否等於入口到禮堂的最短路？
把故事換成電腦語言
| 生活中的角色 | 對應到 | 技術概念 |
|---|---|---|
| 活動必須在其前置工作完成後開始 | DAG 與 topological order | |
| 從入口逐層找最少轉乘站數 | BFS 與無權 shortest path | |
| 讓所有校園據點連通且總線材最少 | Minimum spanning tree | |
| 把大型活動拆成獨立小組後合併結果 | Divide-and-conquer | |
| 記錄重複子排程的最佳成本避免重算 | Dynamic programming |
題目出現這些字，先想到
- 看到 prerequisite/order：先檢查 directed acyclic，cycle 使 topological sort 不存在。
- 看到 unweighted minimum edges：BFS；要深入探索 cycle/連通性常用 DFS。
- 看到 connect all vertices with minimum total weight：MST，不是 single-source shortest path。
- 看到 greedy/DP：要求局部選擇證明或 overlapping subproblems，並補 correctness 論證。
1.Graph 把物件與關係分開
Graph G=(V,E) 以 vertices 表示物件、edges 表示關係；邊可有方向與權重。BFS 逐層展開，適合無權圖最少邊數距離；DFS 沿一路深入後回溯，適合連通性、cycle 與結構探索。
- Directed edge 有方向
- Weighted edge 帶成本
- BFS 使用 queue
- DFS 常用 stack 或 recursion
2.Topological sort 只屬於 DAG
Topological order 讓每條 u→v 都滿足 u 出現在 v 前面。若有 directed cycle，環上每個工作都要求另一個先完成，無法形成線性順序。Kahn 方法反覆取 indegree 0 節點；DFS 方法依完成時間反向排列並偵測 back edge。
- 不是所有 directed graph 都可排序
- 答案可能不唯一
- 若輸出節點少於 |V| 表示存在 cycle
- 不要求圖 fully connected
3.MST 與 shortest path 回答不同問題
Spanning tree 連接全部 vertices 且無 cycle，n 個 vertices 有 n−1 條邊；MST 最小化整棵樹總權重。Shortest path 則最小化特定起終點路徑成本，不要求連接所有 vertices。Prim 依 cut property 安全加入跨 cut 的最輕邊。
- MST 需要 connected undirected graph
- 最短路徑樹不一定是 MST
- 權重相同時 MST 可能不唯一
- Dijkstra 不適用負權邊
4.先辨認子問題關係再選設計策略
Greedy 每步作局部安全選擇，需證明 greedy-choice property；divide-and-conquer 把問題拆成大致獨立子問題後合併；dynamic programming 適用 overlapping subproblems 與 optimal substructure，儲存狀態避免重算。
- 看到最優問題不代表 greedy 一定正確
- Memoization 是 top-down DP
- Tabulation 是 bottom-up DP
- Merge sort 是典型 divide-and-conquer
5.複雜度之外還要證明答案正確
演算法答案至少說清楚 input、output、步驟、終止與 complexity。Loop invariant 可描述每輪前後維持的真命題；exchange argument 常證明 greedy 解可轉換成含某個 greedy choice 的最優解；induction 可沿輸入規模或 DP 狀態證明。
- 測過範例不是 correctness proof
- Invariant 要有初始化、維持、終止
- Complexity 不等於 correctness
- 反例可推翻不成立的 greedy rule
一起拆題目
範例 1：課程相依 A→C、B→C、C→D，給一個 topological order。
- A、B indegree 為 0，可先任選
- 取 A、B 後 C indegree 變 0
- 最後取 D
所以答案是：A,B,C,D 或 B,A,C,D 均合法。
範例 2：找零問題硬幣 {1,3,4}、金額 6，永遠先取最大硬幣的 greedy 是否最佳？
- Greedy 取 4+1+1，共 3 枚
- 另一解為 3+3，共 2 枚
- 出現反例，故此幣制下 greedy rule 不正確
所以答案是：不正確；可用 DP 求每個金額的最少硬幣數。
這裡最容易選錯
- 在有 cycle 的 directed graph 上要求 topological order
- 把 BFS 與 DFS 的 queue/stack 對調
- 把 MST 當成任意兩點 shortest path
- 看到 optimal 就直接套 greedy
- 只分析 Big-O、不說明演算法為何正確
換你快速判斷
先在心中作答，再展開答案。答不出來時，回頭找本課的對照關係。
1Topological sort 的必要圖形條件是什麼？
必須是 directed acyclic graph（DAG）。有 directed cycle 就不存在能滿足所有先後關係的線性順序。
圖不必 fully connected，合法 order 也可能不唯一。
2Minimum spanning tree 與 shortest path 的目標有何不同？
MST 以最小總邊權連通全部 vertices；shortest path 最小化特定起終點的路徑成本。
Connected graph 的 spanning tree 有 n−1 edges；最短路徑樹不必是 MST。
3如何區分 greedy、divide-and-conquer 與 dynamic programming？
Greedy 逐步做可證安全的局部選擇；divide-and-conquer 合併大致獨立子問題；DP 儲存重疊子問題的狀態。
DP 通常還需要 optimal substructure；最優化問題不代表 greedy 一定成立。
4分析出 Big-O 之後，為何仍需要 correctness proof？
Big-O 只描述資源成長，不證明演算法輸出符合規格；還需 invariant、induction、exchange argument 等證據。
測試數個 examples 也不能取代對所有合法 inputs 的正確性論證。
最後用考古題驗證
本課連結的題目都已通過可重現的技術覆核，可逐題練習與判分。
開始本課考古題練習參考來源
- Introduction to Algorithms (6.006) — Erik Demaine and Srini Devadas