Hello Algo 图论练习题全解：图的两种表示、BFS/DFS 遍历序与路径可达性判断

本篇文章以《Hello Algo》英文版「Graph」章节的课后练习（en/docs/chapter_graph/exercises.md）为骨架，逐题给出推导过程与标准答案，并把每道题背后的知识点映射到正文章节与仓库源码上。读者学完后，既能独立完成"邻接表/邻接矩阵互转、写 BFS/DFS 访问序、数连通分量"这类笔试题，也能上手实现"判断无向图中两个顶点是否存在路径"这一经典算法题。

---

1. 练习在整章中的定位

在《Hello Algo》的图（Graph）章节中，正文按如下顺序组织知识：

• 图基础概念与两种表示法：顶点/边、有向/无向、连通/非连通、加权图，以及邻接矩阵与邻接表的定义与性质；
• 图的基本操作：两种表示下增删边、增删顶点的复杂度对比表；
• 图的遍历：广度优先搜索（BFS）与深度优先搜索（DFS）的队列/递归实现与复杂度分析。

本章的 exercises.md 正是承接上述三段正文的"概念巩固 + 上机实践"。练习题强调三件事：手写两种存储结构、手推两种遍历序列、用代码判断可达性，与正文互为印证。

2. 概念题一：同一张图，两种表示

一个无向图有 4 个顶点 A, B, C, D，边为 A-B, A-C, B-C, C-D。

2.1 写出它的邻接表

邻接表为每个顶点维护一个"邻居链表/列表"，只记录真实存在的边。本题的邻接表为：

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

因为是无向图，每条边要在两端各记录一次，所以 A-B 同时出现在 A 与 B 的列表中；A 与 D 之间没有边，彼此不互为邻居。这一"边存两次"的做法在仓库的 Python 实现里看得一清二楚——graph_adjacency_list.py 中 add_edge 同时向 vet1 和 vet2 的列表追加对方，即 self.adj_list[vet1].append(vet2) 与 self.adj_list[vet2].append(vet1)。

2.2 用 0/1 填出邻接矩阵

邻接矩阵按"行列各对应一个顶点"的方式预留 $n^2$ 个位置，M[i][j] = 1 表示顶点 $i$、$j$ 之间有边。本题填表如下：

	A	B	C	D
A	0	1	1	0
B	1	0	1	0
C	1	1	0	1
D	0	0	1	0

两点值得注意，也与正文 graph.md 中"邻接矩阵的性质"完全对应：

• 主对角线为 0：简单图中顶点不能连到自己，主对角线元素无意义；
• 关于主对角线对称：M[A][B] == M[B][A] == 1，这是无向图"边无方向"在矩阵上的直接体现。

仓库里的 graph_adjacency_matrix.py 在 add_edge 中同时执行 self.adj_mat[i][j] = 1 和 self.adj_mat[j][i] = 1，正是在维护这种对称性。

2.3 判断"A 与 D 是否直接相连"，哪种表示只需查一个存储单元？

邻接矩阵。只需读一次 M[A][D]（或其对称位置 M[D][A]），单次数组访问，$O(1)$。

在邻接表中，要确认 A 与 D 是否相连，需要遍历 A 的整条邻居列表去查找 D。邻接表在 graph_operations.md 的效率对比表中记作 $O(n)$（若用哈希表组织邻居可达 $O(1)$），而邻接矩阵判定邻接关系恒为 $O(1)$。

2.4 "顶点多、边少"的稀疏图，哪种表示更省空间？

邻接表。它只为真实存在的边分配存储，空间约 $O(n + m)$；邻接矩阵为每一对顶点都预留位置，空间恒为 $O(n^2)$。当顶点很多而边很少时（例如社交网络中大量孤立用户的场景），$m \ll n^2$，邻接表的优势非常明显。这与正文效率对比表（邻接矩阵 $O(n^2)$、邻接表 $O(n + m)$）结论一致，即邻接矩阵"以空间换时间"，邻接表"以时间换空间"。

3. 概念题二：写出 BFS 与 DFS 的遍历顺序

无向图顶点为 A, B, C, D, E，边为 A-B, A-C, B-D, C-D, D-E，从 A 出发，遇到多个未访问邻居时按字母序选择。

3.1 广度优先遍历（BFS）的访问顺序

BFS 的核心理念是"由近及远、逐层扩散"：先把距起点 1 条边的顶点全部访问完，再去访问距起点 2 条边的顶点。

从 A 出发：

1. 访问 A，入队其邻居 B, C（字母序）；
2. 出队 B，B 的邻居 D 未访问，入队；
3. 出队 C，C 的邻居 D 已入队/已访问，跳过；
4. 出队 D，D 的邻居 E 未访问，入队；
5. 出队 E，结束。

最终 BFS 顺序为 A, B, C, D, E——先访问距 A 一跳的 B, C，再访问更远的 D, E。

需要提醒的是，同一距离内的顶点顺序可以任意打乱。正文 graph_traversal.md 明确指出 BFS 序列不唯一：即使没有"字母序"约束，B 与 C、后续不同分支的顶点之间也完全可以互换访问次序。

3.2 递归深度优先遍历（DFS）的访问顺序

DFS 的核心理念是"一头扎到底，走投无路再回头"。结合"选未访问邻居时按字母序"：

从 A 出发，优先字母序最小的邻居：

1. 访问 A → 进入 B；
2. 访问 B → B 的邻居中 D 未访问，进入 D；
3. 访问 D → D 的邻居 E 未访问，进入 E；
4. 访问 E → E 无未访问邻居，回溯到 D；
5. D 的邻居中 C 未访问，进入 C；
6. 访问 C → 无未访问邻居，一路回溯，全部结束。

DFS 顺序为 A, B, D, E, C，前序路线为 A → B → D → E，回溯到 D 后再拐向 C。

官方答案给出的是 A, B, D, C, E（即先沿 A → B → D → C 走到底再访问 E），两者差异源于"遍历 D 的邻居时先选谁"。它恰好印证了正文的结论：DFS 遍历序列同样不唯一，只要满足"优先深入"的原则、邻居遍历顺序可任意调整，均属合法深度优先遍历（如同树的先序/中序/后序三种不同优先级都属于 DFS）。做题时务必以题面给定的邻居选择规则为准。

3.3 为什么两种遍历都必须记录"已访问"？

因为图中存在环（cycle），例如 A-B-D-C-A 构成一个闭合回路。若不记录已访问顶点：

• BFS 中，B 与 C 会反复把对方（以及 D）重新入队，队列永不清空；
• DFS 中，递归会沿着环无限下钻，A → B → D → C → A → B → … 无法停止。

因此必须用哈希集合 visited 记录访问过的顶点，遇到已访问顶点直接跳过。仓库的 Python 实现正是如此：graph_bfs 中每次入队即打标（visited.add(adj_vet)），见 graph_bfs.py；graph_dfs 的辅助函数进入顶点时立刻 visited.add(vet)，见 graph_dfs.py。两者的 visited 都使用哈希集合，从而让"查重"在 $O(1)$ 内完成。

3.4 一道练习背后的两段源码

这道手推题与仓库 codes/python/chapter_graph 下 graph_bfs.py、graph_dfs.py 的运行逻辑一致，可以用它们来验证手推结果：

• BFS 用 deque 维护 FIFO 队列，while 循环内"队首出队 → 记录 → 未访问邻居入队"；
• DFS 用递归函数 dfs 实现"进入 → 打标 → 逐邻居递归"的深入与回溯。

如果你想实际运行验证，可执行仓库内脚本（Python 版示例）：

python codes/python/chapter_graph/graph_bfs.py
python codes/python/chapter_graph/graph_dfs.py

4. 概念题三：一次 BFS 能走遍全图吗？

无向图顶点为 A, B, C, D, E, F，边只有 A-B, B-C, D-E。

4.1 从 A 出发的一次 BFS 能访问哪些顶点？

只能访问 A, B, C。因为从 A 出发，能到达的顶点集合由"与 A 之间存在路径"决定，而 A 所在连通块只有 A-B-C 这条链。

4.2 这次 BFS 访问到全部顶点了吗？

没有。D, E 组成另一个连通块，F 是孤立顶点（度为 0）。它们与 A 之间没有任何路径，因此从 A 发起的单次遍历永远无法触及。这对应正文 graph.md 中"非连通图：从某个顶点出发，至少有一个顶点无法到达"的定义。

4.3 按字母序扫描、遇到未访问顶点就再启动一次 BFS，起点分别是什么？图被分成几个互不相连的部分？

按字母序扫描：A 未访问 → 从 A 发起 BFS，访问 {A, B, C}；接着 D 未访问 → 从 D 发起 BFS，访问 {D, E}；最后 F 未访问 → 从 F 发起 BFS，访问 {F}。

• 三次 BFS 的起点分别是 A、D、F；
• 该图被分成 3 个连通分量（connected components）：{A, B, C}、{D, E}、{F}。

这个"扫描所有顶点 + 对未访问者重开遍历"的过程，正是统计图中连通分量数量的通用套路，也是下一节"可达性判断"在多分量、多起点场景下的直接扩展。

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

5.1 题目描述

给定一个无向图，共有 $n$ 个顶点，编号为 $0$ 到 $n-1$。数组 edges 中每个元素 [u, v] 表示顶点 u 与 v 之间的一条无向边。另给起点 source 与终点 destination，请先根据 edges 建出邻接表，再用 BFS 或 DFS 判断从 source 能否到达 destination：存在路径返回 true，否则返回 false。图中可能含环，也可能不连通。

题面输入条件回顾：

条件	对算法的影响
无向边	每条边 [u, v] 必须在邻接表中双向添加：u 的邻居加 v，v 的邻居加 u
图可能含环	必须用 visited 记录已访问顶点，防止绕环死循环
图可能不连通	只要 source 与 destination 属于同一连通分量即可达，否则 false
特例	若 source == destination，直接返回 true（空路径也构成路径）

5.2 题目给出的三条提示逐条解读

1. 把每条无向边在两个方向上都加入邻接表——这是"无向边"对建图的要求，同仓库 GraphAdjList.add_edge 的双向追加写法；
2. 图可能含环，必须记录已访问顶点——对应 3.3 节的分析，环使朴素遍历无法终止；
3. 从 source 出发，遇到 destination 即返回 true；遍历结束仍未遇到则返回 false——利用"可达即同连通分量"的性质做提前终止，无需遍历完整张图。

5.3 参考实现（Python，BFS 版）

先按邻接表建图，再用队列做 BFS：

from collections import deque


def build_adj_list(n: int, edges: list[list[int]]) -> list[list[int]]:
    """按无向边规则构建邻接表：n 个顶点，edges 中的每条边双向添加"""
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    return graph


def valid_path(n: int, edges: list[list[int]], source: int, destination: int) -> bool:
    if source == destination:
        return True  # 起点即终点，空路径也合法

    graph = build_adj_list(n, edges)   # 建邻接表，O(n + m)
    visited = [False] * n              # 用布尔数组记录已访问（本题顶点为整数下标）
    que = deque([source])
    visited[source] = True

    while que:
        cur = que.popleft()
        for nxt in graph[cur]:
            if nxt == destination:
                return True            # 遇到终点，提前返回
            if not visited[nxt]:
                visited[nxt] = True    # 入队即打标，防环 + 防重复入队
                que.append(nxt)
    return False                       # 遍历完整个连通分量仍未遇到终点

5.4 参考实现（Python，DFS 版）

DFS 可用递归，也可用显式栈避免深链递归栈溢出：

def valid_path_dfs(n: int, edges: list[list[int]], source: int, destination: int) -> bool:
    if source == destination:
        return True

    graph = build_adj_list(n, edges)
    visited = [False] * n
    stack = [source]                   # 显式栈，等价于递归调用栈
    visited[source] = True

    while stack:
        cur = stack.pop()
        for nxt in graph[cur]:
            if nxt == destination:
                return True
            if not visited[nxt]:
                visited[nxt] = True
                stack.append(nxt)
    return False

BFS 与 DFS 在此题中都可选：题目只关心"是否可达"，不要求最短路径或某种特定遍历序，因此只要在搜索过程中命中 destination 即可提前返回。若图中的连通分量包含超长链，建议优先使用显式栈/队列的迭代写法，避免递归深度过大。

5.5 复杂度分析

• 建图：创建 $n$ 个空列表并遍历 $m$ 条边双向写入，时间与空间均为 $O(n + m)$；
• 遍历：BFS/DFS 中每个顶点至多入队/入栈一次，每条无向边在两端各被检查一次，故时间 $O(n + m)$；
• 空间：邻接表 $O(n + m)$，visited 数组 $O(n)$，队列/栈最多同时容纳 $O(n)$ 个顶点，总空间 $O(n + m)$。

与正文 graph_traversal.md 中 BFS/DFS 的复杂度结论一致：无论广度还是深度，单次遍历均为 $O(|V| + |E|)$ 时间、$O(|V|)$ 的辅助空间（此处建图额外引入 $O(|E|)$ 的邻接表存储）。

5.6 从"一笔可达"到"全图可达"的推广

若把题目扩展为"求整张图的所有连通分量"，只需套用 4.3 节的扫描法：外层遍历所有顶点，遇到未访问者便从它发起一次 BFS/DFS，启动几次遍历就有几个连通分量；source 与 destination 可达，当且仅当它们属于同一个连通分量。这与《Hello Algo》"图的遍历"章节中 visited 只记录单次遍历、由调用方决定是否对每个顶点重开遍历的设计是一脉相承的。

6. 自查清单：做完练习后你应该能确认

做完本章练习后，可用以下清单自测掌握程度：

1. 给定一张无权无向图，能否互不依赖地写出它的邻接表与邻接矩阵（并注意到矩阵的主对角线全 0 与关于主对角线对称）；
2. 能否在给定邻居选择规则下，手推出 BFS 与 DFS 的访问序列，并解释序列为何不唯一；
3. 能否解释 visited 记录在含环图中为何是遍历正确终止的必要条件；
4. 能否解释单次遍历的覆盖范围=一个连通分量，并写出"扫描全体顶点数连通分量"的算法；
5. 能否独立实现"判断路径是否存在"，正确处理无向边双向建表、环与不连通图、以及 source == destination 的边界情况。

如需回顾正文以加深理解，可回到 图基础概念、图的基本操作与复杂度对比 和 图的 BFS/DFS 遍历；若想研究多语言实现细节，仓库每种语言的 chapter_graph 目录（如 codes/python/chapter_graph、codes/java/chapter_graph）均提供邻接表、邻接矩阵、BFS、DFS 四个可运行的示例程序。