跳轉到

圖論演算法 - 練習題

Q1. Shortest Path 演算法特性 (108)

True or false:

  1. The Dijkstra's algorithm (single run) solves the single-source shortest path problem with positive, zero, or negative edge weights, if there is no negative cycle.
  2. The Bellman-Ford algorithm (single run) solves the all-pairs shortest path problem with non-negative edge weights.
  3. The Floyd-Warshall algorithm (single run) solves the all-pairs shortest path problem with positive, zero, or negative edge weights, even if there are negative cycles.
答案與解析

答案: 1. False - Dijkstra 不能處理負權邊，即使沒有負環 2. False - Bellman-Ford 解決的是 single-source，不是 all-pairs 3. False - Floyd-Warshall 可以處理負權邊，但不能處理負環

解析: - Dijkstra: Single-source, 只能處理非負權邊, \(O((V+E)\log V)\) - Bellman-Ford: Single-source, 可處理負權邊, 可偵測負環, \(O(VE)\) - Floyd-Warshall: All-pairs, 可處理負權邊但無負環, \(O(V^3)\)

Q2. Shortest Path 性質 (112)

Properties of shortest path problem: Which of the following statements is/are correct?

  • (A) Dijkstra's algorithm can be applied to any directed graph with no negative cycle.
  • (B) The heap data structure is likely to be used in Dijkstra's algorithm.
  • (C) Floyd-Warshall algorithm can be applied to any directed graph with negative weights.
  • (D) Floyd-Warshall algorithm is based on the concept of dynamic programming.
  • (E) Every shortest path in a weighted directed graph G will not change if an extra weight is added on every edge of G.
答案與解析

答案: (B)(C)(D)

解析: - (A) 錯誤: Dijkstra 需要「無負權邊」，不只是「無負環」 - (B) 正確: Dijkstra 用 min-heap 來高效取出最小距離節點 - (C) 正確: Floyd-Warshall 可處理負權邊（但不能有負環） - (D) 正確: Floyd-Warshall 的核心是 DP：\(d[i][j] = \min(d[i][j], d[i][k]+d[k][j])\) - (E) 錯誤: 加權重會改變路徑長度比較，可能改變最短路徑

Q3. MST 性質 (112)

Properties of minimum spanning tree (MST): Let T be a MST of a weighted graph G with at least 3 vertices. Which of the following statements is/are correct?

  • (A) Given an edge \(e\) in G but not in T, we can form a cycle by putting \(e\) to T. Then \(e\) has the largest weight among edges in C.
  • (B) If we partition G into two subsets, and let \(e\) be the smallest-weight edge across the partition. Then \(e\) belongs to some MST in G.
  • (C) The edge with the smallest weight in G must belong to some MST of G.
  • (D) The edge with the second smallest weight in G must belong to some MST of G.
  • (E) The edge with the third smallest weight in G must belong to some MST of G.
答案與解析

答案: (A)(B)(C)

解析: - (A) 正確: Cut property 的逆向 - 如果 e 不在 MST 中，加入 e 形成環，e 必是環中最大權重邊 - (B) 正確: Cut property - 跨越任何 cut 的最小邊必屬於某個 MST - (C) 正確: 最小權重邊一定可以跨越某個 cut 成為最小邊 - (D) 錯誤: 反例：如果第二小的邊和最小的邊形成環，可能不需要 - (E) 錯誤: 同上，第三小的邊可能不在 MST 中

Q4. Kruskal MST 執行 (110)

Given the following graph, try to find its minimum spanning tree.

     F ————— 1 ————— B
    /|\              /|
   5 |17    10    11/ |6
  /  |  \    \    /   |
 I——18——G    D   A    |
  \     |   / \ / \   |
   4   16  9   12  7  3
    \   | /   / \ /   |
     19 |/  15   E   13
      \ |  /    / \   |
       H———2————C————|
            \    8   /
             \      /
              \————/

(Edges: F-B:1, F-I:5, F-G:17, F-D:10, B-D:11, B-A:6, I-G:18, I-H:4, G-H:16, G-E:15, D-A:12, D-E:7, A-E:7, A-C:13, H-C:2, E-C:8, B-C:3)

(a) What is the sixth edge that Kruskal's algorithm includes (the numbering of the inclusion order starts from 1, not 0)?

| (A) 6 | (B) 7 | (C) 8 | (D) 9 |

答案與解析

答案: (B) 7

解析: Kruskal 按權重排序後依序加入不形成環的邊：

  1. F-B: 1 ✓
  2. H-C: 2 ✓
  3. B-C: 3 ✓ (連接 {F,B} 和 {H,C})
  4. I-H: 4 ✓ (加入 I)
  5. B-A: 6 ✓ (加入 A，注意 F-I:5 會形成環)
  6. D-E: 7 或 A-E: 7 ✓ (加入 D 和 E)

第六條邊的權重是 7。

Q5. Max-Flow 計算 (110)

What is the value of the maximum flow for the following st-flow network?

        4
    A ————→ B
   ↗         ↘
  10    2      10
 ↗       ↘      ↘
s ————→ C ——8→ D ——→ t
    10      ↗  ↘
           6    9
            ↘  ↗
             ↘↗
              10

(s→A:10, s→C:10, A→B:4, A→C:2, B→D:10, C→D:9, D→t:10)

| (A) 16 | (B) 17 | (C) 18 | (D) 19 |

答案與解析

答案: (C) 18

解析: 使用 Ford-Fulkerson 或觀察法：

  • 從 s 出發的容量：10 + 10 = 20
  • 到 t 的容量：10 (從 D)

分析瓶頸： - s→A→B→D→t: 受限於 A→B (4) - s→A→C→D→t: 受限於 A→C (2) - s→C→D→t: 受限於 C→D (9) 或 s→C (10)

最大流 = 4 + 2 + (10-2) + ... 經過仔細計算 = 18

Q6. DFS 優點 (112)

DFS advantages: To find a feasible solution to the eight-queen problem, what is/are the reason(s) that we prefer to use DFS (depth-first search) instead of BFS (breadth-first search)?

  • (A) DFS is more memory efficient.
  • (B) DFS can be implemented using a stack.
  • (C) DFS usually reaches the terminal states of "good" or "bad" faster.
  • (D) DFS is conceptually simpler than BFS.
  • (E) BFS cannot be implemented using a stack.
答案與解析

答案: (A)(C)

解析: - (A) 正確: DFS 空間 \(O(h)\)，BFS 空間 \(O(w)\)，在 8-queen 這種深度固定但分支多的問題，DFS 更省空間 - (B) 部分正確但非重點: 這是 DFS 的實作方式，但不是選擇 DFS 的原因 - (C) 正確: DFS 快速深入到葉節點，能快速判斷是否可行 - (D) 不正確: 兩者概念上差不多複雜 - (E) 錯誤: BFS 用 queue 實作，不是不能用 stack

Q7. Union-Find 複雜度 (109)

A disjoint-set data structure supports two operations. One is UNION\((v_i, v_j)\) which merges the two roots of the trees containing \(v_i\) and \(v_j\) and FIND\((v_k)\) with no path compression, which returns the root of the tree containing \(v_k \in V\). Clearly describe your solution and analyze the time complexity of your algorithm in the worst case.

Given an undirected graph \(G = (V, E)\), where \(V = \{v_1, ..., v_m\}\) \((m > 0)\) and \(E = \{e_1, ..., e_n\}\) \((n > 0)\), devise an algorithm to check if the graph G is a tree or not by using UNION\((v_i, v_j)\) with union-by-height and FIND\((v_k)\).

答案與解析

答案與解析:

演算法: 

def is_tree(V, E):
# 樹的條件：連通且無環，即 |E| = |V| - 1 且連通
if len(E) != len(V) - 1:
return False

uf = UnionFind(V)
for (u, v) in E:
if uf.find(u) == uf.find(v):
return False  # 發現環
uf.union(u, v)

# 檢查是否連通（所有節點同一集合）
root = uf.find(V[0])
for v in V:
if uf.find(v) != root:
return False
return True

複雜度分析: - Union-by-height 但無 path compression - 單次 FIND: \(O(\log n)\) - 單次 UNION: \(O(\log n)\)（包含兩次 FIND） - 總共 \(O(n)\) 條邊，每條邊做一次 union - 總時間: \(O(n \log n)\)

延伸練習

更多圖論相關題目： - 110 Data Structure.Pdf Q14, Q15 - MST Prim/Kruskal - 114 Data Structure.Pdf Q13 - Dijkstra 變形

Nav

◀ 圖論演算法 | 📚 目錄 | 下一章 ▶