跳转至

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

欢迎在评论区留下你的见解、问题或建议