mirror of
https://github.com/krahets/hello-algo.git
synced 2026-11-05 15:07:40 +08:00
104 lines
3.8 KiB
Markdown
104 lines
3.8 KiB
Markdown
# 練習
|
||
|
||
## 知識鞏固
|
||
|
||
### 用兩種方式表示同一張圖
|
||
|
||
一個無向圖有 4 個頂點 `A、B、C、D`，邊為
|
||
`A-B、A-C、B-C、C-D`。
|
||
|
||
<!-- numbered-subquestions -->
|
||
|
||
1. 寫出它的鄰接表；
|
||
2. 填寫只含 0 和 1 的鄰接矩陣；
|
||
3. 如果要判斷 `A` 和 `D` 是否直接相連，哪種圖的表示方法只需檢視一個儲存條目？
|
||
4. 如果圖的頂點很多但邊很少，哪種表示通常更節省空間？
|
||
|
||
??? success "參考答案"
|
||
|
||
1. 鄰接表為：
|
||
|
||
```text
|
||
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. 頂點很多但邊很少時，鄰接表只記錄實際存在的邊，通常比為每一對頂點都預留位置的鄰接矩陣更節省空間。
|
||
|
||
### 廣度優先與深度優先訪問順序
|
||
|
||
一個無向圖的頂點為 `A、B、C、D、E`，邊為
|
||
`A-B、A-C、B-D、C-D、D-E`。
|
||
|
||
從 A 出發，並規定遇到多個未訪問鄰接頂點時按字母順序選擇：
|
||
|
||
<!-- numbered-subquestions -->
|
||
|
||
1. 寫出廣度優先走訪（BFS）的訪問順序；
|
||
2. 寫出遞迴深度優先走訪（DFS）的訪問順序；
|
||
3. 為什麼兩種走訪都需要記錄已經訪問過的頂點？
|
||
|
||
??? success "參考答案"
|
||
|
||
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`。如果不記錄已訪問頂點，
|
||
走訪可能反覆沿環訪問同一批頂點，無法正常結束。
|
||
|
||
### 一次 BFS 能訪問整張圖嗎
|
||
|
||
一個無向圖有頂點 `A、B、C、D、E、F`，邊只有
|
||
`A-B、B-C、D-E`。
|
||
|
||
<!-- numbered-subquestions -->
|
||
|
||
1. 從 A 開始進行一次 BFS，可以訪問哪些頂點？
|
||
2. 根據第 1 問，這一次 BFS 是否已經訪問圖中的所有頂點？為什麼？
|
||
3. 若按字母順序掃描所有頂點，每遇到一個未訪問頂點就重新開始 BFS，
|
||
各次 BFS 的起點是什麼？這個圖被分成幾個互不連通的部分（連通分量）？
|
||
|
||
??? success "參考答案"
|
||
|
||
1. 從 A 出發只能訪問 `A、B、C`。
|
||
|
||
2. 沒有訪問所有頂點。`D、E` 組成另一個互相連通的部分，F 是單獨的頂點；
|
||
它們與 A 之間都沒有路徑，因此從 A 出發無法到達。
|
||
|
||
3. 三次 BFS 的起點依次為 `A、D、F`，分別訪問
|
||
`{A, B, C}`、`{D, E}` 和 `{F}`。因此這個圖有 3 個連通分量。
|
||
|
||
## 程式設計練習
|
||
|
||
### 判斷無向圖中是否存在路徑
|
||
|
||
給定一個含有 $n$ 個頂點的無向圖，頂點編號為 $0$ 到 $n-1$。陣列 `edges` 中的每一項 `[u, v]` 表示頂點 `u` 和 `v` 之間有一條無向邊。
|
||
|
||
再給定起點 `source` 和終點 `destination`。請先根據 `edges` 建立鄰接表，再使用 BFS 或 DFS
|
||
判斷是否存在一條從 `source` 到 `destination` 的路徑：存在則返回 `true`，否則返回 `false`。
|
||
圖中可能有環，也可能不連通。
|
||
|
||
??? tip "解題提示"
|
||
|
||
1. 每條無向邊需要同時加入兩個方向
|
||
2. 圖中可能有環，必須記錄已經訪問過的節點
|
||
3. 從 source 出發，遇到 destination 返回 true，走訪結束仍未遇到則返回 false
|
||
|
||
[LeetCode](https://leetcode.cn/problems/find-if-path-exists-in-graph/){ .rounded-button .exercise-button target="_blank" rel="noopener noreferrer" }
|