Hello Algo 图论练习题全解图的两种表示、BFS/DFS 遍历序与路径可达性判断【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo本篇文章以《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$ 之间有边。本题填表如下ABCDA0110B1010C1101D0010两点值得注意也与正文 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出发访问A入队其邻居B, C字母序出队BB的邻居D未访问入队出队CC的邻居D已入队/已访问跳过出队DD的邻居E未访问入队出队E结束。最终 BFS 顺序为A, B, C, D, E——先访问距 A 一跳的B, C再访问更远的D, E。需要提醒的是同一距离内的顶点顺序可以任意打乱。正文 graph_traversal.md 明确指出 BFS 序列不唯一即使没有字母序约束B与C、后续不同分支的顶点之间也完全可以互换访问次序。3.2 递归深度优先遍历DFS的访问顺序DFS 的核心理念是一头扎到底走投无路再回头。结合选未访问邻居时按字母序从A出发优先字母序最小的邻居访问A→ 进入B访问B→B的邻居中D未访问进入D访问D→D的邻居E未访问进入E访问E→E无未访问邻居回溯到DD的邻居中C未访问进入C访问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.pygraph_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.py4. 概念题三一次 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的邻居加vv的邻居加u图可能含环必须用visited记录已访问顶点防止绕环死循环图可能不连通只要source与destination属于同一连通分量即可达否则false特例若source destination直接返回true空路径也构成路径5.2 题目给出的三条提示逐条解读把每条无向边在两个方向上都加入邻接表——这是无向边对建图的要求同仓库GraphAdjList.add_edge的双向追加写法图可能含环必须记录已访问顶点——对应 3.3 节的分析环使朴素遍历无法终止从 source 出发遇到 destination 即返回true遍历结束仍未遇到则返回false——利用可达即同连通分量的性质做提前终止无需遍历完整张图。5.3 参考实现PythonBFS 版先按邻接表建图再用队列做 BFSfrom 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 参考实现PythonDFS 版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 FalseBFS 与 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. 自查清单做完练习后你应该能确认做完本章练习后可用以下清单自测掌握程度给定一张无权无向图能否互不依赖地写出它的邻接表与邻接矩阵并注意到矩阵的主对角线全 0 与关于主对角线对称能否在给定邻居选择规则下手推出 BFS 与 DFS 的访问序列并解释序列为何不唯一能否解释visited记录在含环图中为何是遍历正确终止的必要条件能否解释单次遍历的覆盖范围一个连通分量并写出扫描全体顶点数连通分量的算法能否独立实现判断路径是否存在正确处理无向边双向建表、环与不连通图、以及source destination的边界情况。如需回顾正文以加深理解可回到 图基础概念、图的基本操作与复杂度对比 和 图的 BFS/DFS 遍历若想研究多语言实现细节仓库每种语言的chapter_graph目录如 codes/python/chapter_graph、codes/java/chapter_graph均提供邻接表、邻接矩阵、BFS、DFS 四个可运行的示例程序。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 Hello Algo 图论练习题全解：图的两种表示、BFS/DFS 遍历序与路径可达性判断
Hello Algo 图论练习题全解图的两种表示、BFS/DFS 遍历序与路径可达性判断【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo本篇文章以《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$ 之间有边。本题填表如下ABCDA0110B1010C1101D0010两点值得注意也与正文 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出发访问A入队其邻居B, C字母序出队BB的邻居D未访问入队出队CC的邻居D已入队/已访问跳过出队DD的邻居E未访问入队出队E结束。最终 BFS 顺序为A, B, C, D, E——先访问距 A 一跳的B, C再访问更远的D, E。需要提醒的是同一距离内的顶点顺序可以任意打乱。正文 graph_traversal.md 明确指出 BFS 序列不唯一即使没有字母序约束B与C、后续不同分支的顶点之间也完全可以互换访问次序。3.2 递归深度优先遍历DFS的访问顺序DFS 的核心理念是一头扎到底走投无路再回头。结合选未访问邻居时按字母序从A出发优先字母序最小的邻居访问A→ 进入B访问B→B的邻居中D未访问进入D访问D→D的邻居E未访问进入E访问E→E无未访问邻居回溯到DD的邻居中C未访问进入C访问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.pygraph_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.py4. 概念题三一次 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的邻居加vv的邻居加u图可能含环必须用visited记录已访问顶点防止绕环死循环图可能不连通只要source与destination属于同一连通分量即可达否则false特例若source destination直接返回true空路径也构成路径5.2 题目给出的三条提示逐条解读把每条无向边在两个方向上都加入邻接表——这是无向边对建图的要求同仓库GraphAdjList.add_edge的双向追加写法图可能含环必须记录已访问顶点——对应 3.3 节的分析环使朴素遍历无法终止从 source 出发遇到 destination 即返回true遍历结束仍未遇到则返回false——利用可达即同连通分量的性质做提前终止无需遍历完整张图。5.3 参考实现PythonBFS 版先按邻接表建图再用队列做 BFSfrom 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 参考实现PythonDFS 版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 FalseBFS 与 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. 自查清单做完练习后你应该能确认做完本章练习后可用以下清单自测掌握程度给定一张无权无向图能否互不依赖地写出它的邻接表与邻接矩阵并注意到矩阵的主对角线全 0 与关于主对角线对称能否在给定邻居选择规则下手推出 BFS 与 DFS 的访问序列并解释序列为何不唯一能否解释visited记录在含环图中为何是遍历正确终止的必要条件能否解释单次遍历的覆盖范围一个连通分量并写出扫描全体顶点数连通分量的算法能否独立实现判断路径是否存在正确处理无向边双向建表、环与不连通图、以及source destination的边界情况。如需回顾正文以加深理解可回到 图基础概念、图的基本操作与复杂度对比 和 图的 BFS/DFS 遍历若想研究多语言实现细节仓库每种语言的chapter_graph目录如 codes/python/chapter_graph、codes/java/chapter_graph均提供邻接表、邻接矩阵、BFS、DFS 四个可运行的示例程序。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考