跳轉至

9.5 練習¶

9.5.1 知識鞏固¶

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

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

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

參考答案

鄰接表為：
```
A: B, C
B: A, C
C: A, B, D
D: C
```
鄰接矩陣為：

A B C D

A 0 1 1 0

B 1 0 1 0

C 1 1 0 1

D 0 0 1 0
鄰接矩陣可直接檢視第 A 行、第 D 列，因此很適合判斷任意兩點是否直接相連。
頂點很多但邊很少時，鄰接表只記錄實際存在的邊，通常比為每一對頂點都預留位置的鄰接矩陣更節省空間。

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

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

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

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

參考答案

BFS 的訪問順序為 A, B, C, D, E。它先訪問離 A 一條邊的 B、C，再訪問更遠的 D、E。
DFS 的訪問順序為 A, B, D, C, E。它依次進入當前頂點的未訪問鄰接頂點，因此先走過 A → B → D → C；C 沒有新的鄰接頂點時回到 D，再訪問 E。
圖中存在環，例如 A-B-D-C-A。如果不記錄已訪問頂點，走訪可能反覆沿環訪問同一批頂點，無法正常結束。

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

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

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

參考答案

從 A 出發只能訪問 A、B、C。
沒有訪問所有頂點。D、E 組成另一個互相連通的部分，F 是單獨的頂點；它們與 A 之間都沒有路徑，因此從 A 出發無法到達。
三次 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。圖中可能有環，也可能不連通。

解題提示

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

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