跳轉至
紙質書（簡體中文版）已發行，詳情請見這裡

# 9.5 練習

## 9.5.1 知識鞏固

### 1. 用兩種方式表示同一張圖

一個無向圖有 4 個頂點 `A、B、C、D`，邊為 `A-B、A-C、B-C、C-D`。

1. 寫出它的鄰接表；
2. 填寫只含 0 和 1 的鄰接矩陣；
3. 如果要判斷 `A` 和 `D` 是否直接相連，哪種圖的表示方法只需檢視一個儲存條目？
4. 如果圖的頂點很多但邊很少，哪種表示通常更節省空間？

參考答案

1. 鄰接表為：

       A: B, C
       B: A, C
       C: A, B, D
       D: C

2. 鄰接矩陣為：

   | A | B | C | D
   --- | --- | --- | --- | ---
   A | 0 | 1 | 1 | 0
   B | 1 | 0 | 1 | 0
   C | 1 | 1 | 0 | 1
   D | 0 | 0 | 1 | 0

3. 鄰接矩陣可直接檢視第 `A` 行、第 `D` 列，因此很適合判斷任意兩點是否直接相連。

4. 頂點很多但邊很少時，鄰接表只記錄實際存在的邊，通常比為每一對頂點都預留位置的鄰接矩陣更節省空間。

### 2. 廣度優先與深度優先訪問順序

一個無向圖的頂點為 `A、B、C、D、E`，邊為 `A-B、A-C、B-D、C-D、D-E`。

從 A 出發，並規定遇到多個未訪問鄰接頂點時按字母順序選擇：

1. 寫出廣度優先走訪（BFS）的訪問順序；
2. 寫出遞迴深度優先走訪（DFS）的訪問順序；
3. 為什麼兩種走訪都需要記錄已經訪問過的頂點？

參考答案

1. BFS 的訪問順序為 `A, B, C, D, E`。它先訪問離 A 一條邊的 B、C， 再訪問更遠的 D、E。

2. DFS 的訪問順序為 `A, B, D, C, E`。它依次進入當前頂點的未訪問鄰接頂點， 因此先走過 `A → B → D → C`；C 沒有新的鄰接頂點時回到 D，再訪問 E。

3. 圖中存在環，例如 `A-B-D-C-A`。如果不記錄已訪問頂點， 走訪可能反覆沿環訪問同一批頂點，無法正常結束。

### 3. 一次 BFS 能訪問整張圖嗎

一個無向圖有頂點 `A、B、C、D、E、F`，邊只有 `A-B、B-C、D-E`。

1. 從 A 開始進行一次 BFS，可以訪問哪些頂點？
2. 根據第 1 問，這一次 BFS 是否已經訪問圖中的所有頂點？為什麼？
3. 若按字母順序掃描所有頂點，每遇到一個未訪問頂點就重新開始 BFS， 各次 BFS 的起點是什麼？這個圖被分成幾個互不連通的部分（連通分量）？

參考答案

1. 從 A 出發只能訪問 `A、B、C`。

2. 沒有訪問所有頂點。`D、E` 組成另一個互相連通的部分，F 是單獨的頂點； 它們與 A 之間都沒有路徑，因此從 A 出發無法到達。

3. 三次 BFS 的起點依次為 `A、D、F`，分別訪問 `{A, B, C}`、`{D, E}` 和 `{F}`。因此這個圖有 3 個連通分量。

## 9.5.2 程式設計練習

### 1. 判斷無向圖中是否存在路徑

給定一個含有 \(n\) 個頂點的無向圖，頂點編號為 \(0\) 到 \(n-1\)。陣列 `edges` 中的每一項 `[u, v]` 表示頂點 `u` 和 `v` 之間有一條無向邊。

再給定起點 `source` 和終點 `destination`。請先根據 `edges` 建立鄰接表，再使用 BFS 或 DFS 判斷是否存在一條從 `source` 到 `destination` 的路徑：存在則返回 `true`，否則返回 `false`。 圖中可能有環，也可能不連通。

解題提示

1. 每條無向邊需要同時加入兩個方向
2. 圖中可能有環，必須記錄已經訪問過的節點
3. 從 source 出發，遇到 destination 返回 true，走訪結束仍未遇到則返回 false

LeetCode

##### 歡迎在評論區留下你的見解、問題或建議