Hello 算法图解教程：图章节练习精讲——邻接表与邻接矩阵对比、BFS/DFS 手工推演与路径存在性判定

本篇基于《Hello 算法》图章节的练习文档 exercises.md 展开，覆盖该章全部四道练习题：用两种方式表示同一张图、手工推演 BFS 与 DFS 的访问顺序、判断单次 BFS 能否遍历整张图，以及一道基于邻接表 + BFS/DFS 的“无向图路径存在性判定”编程题。读完并对照仓库源码 graph_adjacency_list.py、graph_bfs.py 等实现后，你将能够独立完成图的两种表示选择、遍历序列手推验证，以及写出可运行、可判定的图搜索代码。

练习一：用两种方式表示同一张图

题目与参考答案

一个无向图有 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. 顶点很多但边很少时，邻接表只记录实际存在的边，通常比为每一对顶点都预留位置的邻接矩阵更节省空间。

仓库源码印证：两种表示的落地实现

《Hello 算法》在 graph.md 中给出了两种表示的理论对比：邻接矩阵的增删查改均为 $O(1)$ 但空间为 $O(n^2)$；邻接表只存储实际存在的边、更省空间，但查找边需要遍历链表。仓库中的 Python 实现把这两条结论体现得非常直白。

邻接矩阵实现（graph_adjacency_matrix.py）：内部维护 vertices（顶点值列表）与 adj_mat（二维矩阵）两个结构，行列索引对应顶点索引。添加边时的核心逻辑位于 graph_adjacency_matrix.py#L59-L67：

def add_edge(self, i: int, j: int):
    """添加边"""
    # 参数 i, j 对应 vertices 元素索引
    # 索引越界与相等处理
    if i < 0 or j < 0 or i >= self.size() or j >= self.size() or i == j:
        raise IndexError()
    # 在无向图中，邻接矩阵关于主对角线对称，即满足 (i, j) == (j, i)
    self.adj_mat[i][j] = 1
    self.adj_mat[j][i] = 1

这里有两处与练习题直接相关的细节：其一，无向图要求同时写 (i, j) 与 (j, i) 两个条目，这正是答案矩阵“关于主对角线对称”的由来；其二，i == j 会抛出 IndexError，对应 graph.md 中“简单图中顶点不能与自身相连，主对角线元素没有意义”的说明。

邻接表实现（graph_adjacency_list.py）：用哈希表存储“顶点 → 邻接顶点列表”，add_edge 的双向写入逻辑位于 graph_adjacency_list.py#L31-L37：

def add_edge(self, vet1: Vertex, vet2: Vertex):
    """添加边"""
    if vet1 not in self.adj_list or vet2 not in self.adj_list or vet1 == vet2:
        raise ValueError()
    # 添加边 vet1 - vet2
    self.adj_list[vet1].append(vet2)
    self.adj_list[vet2].append(vet1)

注意构造方法 graph_adjacency_list.py#L17-L25 会在处理每条边前调用 add_vertex，保证孤立顶点（如练习题中只有一条边的 D）也存在于邻接表中。顶点统一由 vertex.py 中的 Vertex 类封装，vals_to_vets / vets_to_vals 两个辅助函数负责整数列表与顶点列表之间的转换，驱动代码中 v = vals_to_vets([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]) 即来自该模块。

如何理解第 3、4 问的选择依据？ 结合 graph.md 的结论可以总结为一张对照表：

维度	邻接矩阵	邻接表
判断两点是否直接相连	$O(1)$，直接查 adj_mat[i][j]	需遍历该顶点的邻接链表，时间随度数增大
空间复杂度	$O(n^2)$，为每对顶点预留位置	只存实际存在的边，稀疏图下更省空间
适用场景	顶点少、边密集的稠密图	顶点多、边稀疏的稀疏图

此外 graph.md 还指出：邻接表结构与哈希表的“链式地址法”相似，链表较长时可转化为 AVL 树或红黑树，将边查询从 $O(n)$ 优化至 $O(\log n)$，或进一步用哈希表降到 $O(1)$——这是从源码结构看两种表示之间效率差异的进一步优化方向。

练习二：广度优先与深度优先的访问顺序

题目与参考答案

一个无向图的顶点为 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。 如果不记录已访问顶点，遍历可能反复沿环访问同一批顶点，无法正常结束。

逐步推演：为什么是这两个顺序

BFS 推演（队列模拟）： 起始队列 [A]。弹出 A，入队其未访问邻居 B、C，队列 [B, C]；弹出 B，A 已访问、D 未访问，入队 D，队列 [C, D]；弹出 C，其邻居 A、D 均已访问或已在队列中（D 已在 visited 中），队列 [D]；弹出 D，入队 E，队列 [E]；弹出 E。访问序列即 A, B, C, D, E，呈现“一层层由近及远”的扩张。

DFS 推演（递归模拟）： 从 A 出发，按字母序进入未访问邻居 B；B 的未访问邻居为 D（A 已访问），进入 D；D 的未访问邻居按字母序为 C（B 已访问、E 排在 C 后），进入 C；C 的邻居 A、D 全部已访问，递归返回 D，此时 E 成为 D 的首个未访问邻居，进入 E。序列为 A, B, D, C, E，呈现“优先走到底、无路可走再回头”的形态。

仓库源码印证：visited 集合是遍历终止的关键

第 3 问的答案——必须记录已访问顶点——在仓库的 BFS/DFS 实现中体现为同一套“哈希集合 visited + 跳过已访问”的模式。

BFS 实现（graph_bfs.py#L16-L36）：

def graph_bfs(graph: GraphAdjList, start_vet: Vertex) -> list[Vertex]:
    """广度优先遍历"""
    # 使用邻接表来表示图，以便获取指定顶点的所有邻接顶点
    # 顶点遍历序列
    res = []
    # 哈希集合，用于记录已被访问过的顶点
    visited = setVertex
    # 队列用于实现 BFS
    que = dequeVertex
    # 以顶点 vet 为起点，循环直至访问完所有顶点
    while len(que) > 0:
        vet = que.popleft()  # 队首顶点出队
        res.append(vet)  # 记录访问顶点
        # 遍历该顶点的所有邻接顶点
        for adj_vet in graph.adj_list[vet]:
            if adj_vet in visited:
                continue  # 跳过已被访问的顶点
            que.append(adj_vet)  # 只入队未访问的顶点
            visited.add(adj_vet)  # 标记该顶点已被访问
    # 返回顶点遍历序列
    return res

递归 DFS 实现（graph_dfs.py#L15-L35）：

def dfs(graph: GraphAdjList, visited: set[Vertex], res: list[Vertex], vet: Vertex):
    """深度优先遍历辅助函数"""
    res.append(vet)  # 记录访问顶点
    visited.add(vet)  # 标记该顶点已被访问
    # 遍历该顶点的所有邻接顶点
    for adjVet in graph.adj_list[vet]:
        if adjVet in visited:
            continue  # 跳过已被访问的顶点
        # 递归访问邻接顶点
        dfs(graph, visited, res, adjVet)

两个实现中 visited 的判定位置略有差异但效果一致：BFS 在入队时标记（防止同一顶点被多次入队），DFS 在递归进入时标记（防止沿环无限递归）。若去掉 visited，练习题二中的环 A-B-D-C-A 会让 A-B-D-C-A-B-... 永远走不完。复杂度方面，据 graph_traversal.md 的分析，BFS 与 DFS 的时间复杂度均为 $O(|V| + |E|)$（每个顶点入队/访问一次，无向图的每条边被访问 2 次），空间复杂度均为 $O(|V|)$（res、visited、队列或递归栈的规模上界）。

需要注意的一个细节是：遍历序列并不唯一。BFS 只要求“由近及远”，同层顶点顺序可任意打乱；DFS 只要求“优先走到底”，邻接顶点顺序也可任意打乱（见 graph_traversal.md）。练习题特意规定“按字母顺序选择”，正是为了把答案固定为 A, B, C, D, E 与 A, B, D, C, E，便于验证。

练习三：一次 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 个连通分量。

关键结论：单次遍历只对“连通图”覆盖全图

这道题揭示了 graph.md 中“连通图与非连通图”区分的工程含义：对于连通图，从任意一个顶点出发的一次 BFS/DFS 即可访问全部顶点；对于非连通图，单次遍历只能覆盖起点所在的连通分量。仓库中 graph_bfs.py 的单次 graph_bfs 调用也只返回从 start_vet 可达的顶点序列——它并不保证覆盖整图。

要统计全部连通分量，标准做法正是第 3 问描述的外层循环：按固定顺序扫描顶点，每遇到一个 visited 中不存在的顶点，就以它为起点再跑一次 BFS（或 DFS），每跑一次就发现一个连通分量，并把该次访问到的顶点全部标记为已访问。按字母顺序扫描 A、B、C、D、E、F 时：A 未访问，跑 BFS 得到 {A, B, C}；B、C 已跳过；D 未访问，跑 BFS 得到 {D, E}；F 未访问，跑 BFS 得到 {F}，共 3 个连通分量。这个“多源重复遍历”模式是后续求弱连通分量、岛数量一类问题的通用骨架。

编程练习：判断无向图中是否存在路径

题目

给定一个含有 $n$ 个顶点的无向图，顶点编号为 $0$ 到 $n-1$。数组 edges 中的每一项 [u, v] 表示顶点 u 和 v 之间有一条无向边。再给定起点 source 和终点 destination。请先根据 edges 建立邻接表，再使用 BFS 或 DFS 判断是否存在一条从 source 到 destination 的路径：存在则返回 true，否则返回 false。图中可能有环，也可能不连通。（该题即 LeetCode 上的“图中是否存在路径”Find if Path Exists in Graph。）

练习文档给出的三条解题提示：

1. 每条无向边需要同时加入两个方向；
2. 图中可能有环，必须记录已经访问过的节点；
3. 从 source 出发，遇到 destination 返回 true，遍历结束仍未遇到则返回 false。

完整实现（BFS 版）

from collections import deque


def valid_path(n: int, edges: list[list[int]], source: int, destination: int) -> bool:
    """判断是否存在从 source 到 destination 的路径（BFS 实现）"""
    # 1. 建立邻接表：每条无向边同时加入两个方向
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    # 2. 特判：起点即终点
    if source == destination:
        return True

    # 3. BFS：哈希集合记录已访问顶点，防止沿环重复访问
    visited = {source}
    que = deque([source])
    while len(que) > 0:
        vet = que.popleft()  # 队首顶点出队
        for adj_vet in adj[vet]:
            if adj_vet in visited:
                continue  # 跳过已访问顶点
            if adj_vet == destination:
                return True  # 遇到 destination，路径存在
            visited.add(adj_vet)
            que.append(adj_vet)
    return False  # 遍历结束仍未遇到 destination

代码结构与仓库 graph_bfs.py 的 graph_bfs 函数一一对应：deque 队列保证“由近及远”，visited 集合保证每个顶点最多入队一次，区别仅在于这里把“完整收集序列”替换成了“命中 destination 立即返回”的提前终止。提前返回是正确的，因为 BFS 的可达性不依赖是否继续遍历完剩余顶点——能出队/入队 destination 本身就等价于存在一条 source → destination 路径。

完整实现（DFS 版）

def valid_path_dfs(n: int, edges: list[list[int]], source: int, destination: int) -> bool:
    """判断是否存在从 source 到 destination 的路径（DFS 实现）"""
    # 1. 建立邻接表（同 BFS 版）
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    def dfs(vet: int, visited: set[int]) -> bool:
        """深度优先搜索辅助函数"""
        visited.add(vet)  # 标记已访问，防止沿环无限递归
        for adj_vet in adj[vet]:
            if adj_vet in visited:
                continue
            if adj_vet == destination:
                return True  # 找到路径
            if dfs(adj_vet, visited):
                return True  # 向上逐层返回命中信号
        return False

    return dfs(source, set())

该实现沿用了仓库 graph_dfs.py 的递归骨架（visited 集合 + 递归深入 + 跳过已访问），区别是每层递归把“命中 destination”的布尔结果逐层上抛，实现提前终止。

用练习题数据验证

用本文两道知识巩固题的图可以直接验证两个分支：

# 来自练习二：A-B, A-C, B-D, C-D, D-E（映射为 0-4 编号）
edges1 = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4]]
print(valid_path(5, edges1, 0, 4))   # True，路径 0-1-3-4 存在

# 来自练习三：A-B, B-C, D-E（6 个顶点，F 为孤立点）
edges2 = [[0, 1], [1, 2], [3, 4]]
print(valid_path(6, edges2, 0, 4))   # False，0 与 4 处于不同连通分量

第二个用例正好复现了练习三的核心结论：source 与 destination 分属不同连通分量时，BFS 遍历完 {0, 1, 2} 后队列清空，返回 False。

复杂度与实现要点

• 时间复杂度：$O(\mathrm{\mid }V\mathrm{\mid }+\mathrm{\mid }E\mathrm{\mid })$。最坏情况下每个顶点入队/递归访问一次，无向图的每条边在邻接表中出现 2 次被扫描，与 graph_traversal.md 对 BFS/DFS 的复杂度结论一致。
• 空间复杂度：$O(|V|)$，来自 visited 集合与队列（BFS）或递归调用栈（DFS）。
• 三个易错点：① 无向边漏加反向边会导致单向判定失败（提示 1）；② 忘记 visited 会在有环图上死循环（提示 2，对应仓库实现中 if adj_vet in visited: continue 一行）；③ 非连通图下未命中即应返回 False，而不是报错（提示 3）。

相关仓库文件导航

文件	内容
docs/chapter_graph/exercises.md	本篇对应的练习原文
docs/chapter_graph/graph.md	图的表示理论：邻接矩阵 / 邻接表的复杂度对比
docs/chapter_graph/graph_traversal.md	BFS / DFS 的分步图解与复杂度分析
codes/python/chapter_graph/graph_adjacency_list.py	邻接表无向图类（增删顶点/边）
codes/python/chapter_graph/graph_adjacency_matrix.py	邻接矩阵无向图类（增删顶点/边）
codes/python/chapter_graph/graph_bfs.py	广度优先遍历实现
codes/python/chapter_graph/graph_dfs.py	深度优先遍历实现
codes/python/modules/vertex.py	Vertex 顶点类及列表转换辅助函数

上述图章节代码在仓库中另有多语言实现（如 codes/java、codes/cpp、codes/go、codes/rust 等目录下的同名 chapter_graph 模块），可按熟悉的语言对照阅读；Python 版本可直接在 codes/python 目录下运行各模块文件查看运行输出，用于验证本文手推的遍历序列与路径判定结果。