《Hello 算法》图的遍历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 算法》hello-algo仓库的图论章节文档与配套源码系统讲解图的两种基本遍历方式——广度优先遍历BFS与深度优先遍历DFS从核心思想、算法步骤到可运行的多语言参考实现并给出时间/空间复杂度推导与遍历序列不唯一性的讨论。读完后你能够独立写出并验证一个无向图的 BFS/DFS 实现理解visited哈希集合、队列/递归这两种驱动结构在算法中的分工。树与图遍历是搜索的特例树代表的是“一对多”的关系而图具有更高的自由度可以表示任意的“多对多”关系。因此树可以看作图的一种特例树的遍历操作也是图的遍历操作的一种特例。图和树都需要应用搜索算法来实现遍历操作。图的遍历方式分为两种广度优先遍历BFS由近及远一层层向外扩张深度优先遍历DFS优先走到底无路可走再回头。在仓库中两者的实现都位于codes/语言/chapter_graph/目录下如 graph_bfs.py、graph_dfs.py并统一建立在邻接表数据结构之上即 GraphAdjList 类。以 Python 版为例邻接表内部是一个dict[Vertex, list[Vertex]]key 为顶点、value 为该顶点的所有邻接顶点这使得“获取指定顶点的所有邻接顶点”可以一次查表完成——这正是 BFS/DFS 实现的前提。广度优先遍历BFS核心思想由近及远广度优先遍历是一种由近及远的遍历方式从某个节点出发始终优先访问距离最近的顶点并一层层向外扩张。从左上角顶点出发首先遍历该顶点的所有邻接顶点然后遍历下一个顶点的所有邻接顶点以此类推直至所有顶点访问完毕。算法步骤与队列BFS 通常借助队列实现。队列“先入先出”的性质与 BFS “由近及远”的思想异曲同工。算法流程如下将遍历起始顶点startVet加入队列并开启循环。在循环的每轮迭代中弹出队首顶点并记录访问然后将该顶点的所有邻接顶点加入到队列尾部。循环步骤 2直到所有顶点被访问完毕后结束。为了防止重复遍历顶点需要借助一个哈希集合visited记录哪些顶点已被访问。提示哈希集合可以看作一个只存储key而不存储value的哈希表它可以在 $O(1)$ 时间复杂度下进行key的增删查改操作。根据key的唯一性哈希集合通常用于数据去重等场景。Python 参考实现下面是仓库中 graph_bfs.py 的核心代码def graph_bfs(graph: GraphAdjList, start_vet: Vertex) - list[Vertex]: 广度优先遍历 # 使用邻接表来表示图以便获取指定顶点的所有邻接顶点 res [] # 顶点遍历序列 visited setVertex # 哈希集合记录已被访问的顶点 que dequeVertex # 队列用于实现 BFS # 以顶点 start_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从源码结构看这里有一个值得注意的细节顶点是在“入队时”而不是“出队时”被标记进visited的。这样做的效果是同一个顶点至多入队一次队列长度不会因重复入队而膨胀如果等到出队时再判重同一顶点可能被多个邻居重复压入队列虽然结果仍然正确但会浪费额外的入队/出队开销。多语言实现的差异仓库为 BFS 提供了十余种语言实现各语言的核心逻辑一致但在“队列”与“哈希集合”的落地方式上各有取舍Javagraph_bfs.java使用HashSetVertex作访问集合LinkedList实现Queueoffer/poll对应入队/出队JavaScriptgraph_bfs.js直接用数组que模拟队列shift()出队、push()入队配合Set判重Gograph_bfs.go用切片模拟队列出队采用queue queue[1:]的切片头偏移技巧访问集合用空结构体map[Vertex]struct{}表示map 中仅存 key正是“哈希集合”语义Cgraph_dfs.c 中的isVisited函数BFS 版同理C 语言没有内建哈希集合参考实现退化为对结果数组res做线性查找单次判重耗时 $O(|V|)$。这说明visited哈希集合在 C 版中是用更朴素的方式替代的判重开销会相应上升。遍历序列是否唯一不唯一。广度优先遍历只要求按“由近及远”的顺序遍历而多个相同距离的顶点的遍历顺序允许被任意打乱。以上述示例图为例顶点 $1$、$3$ 的访问顺序可以交换顶点 $2$、$4$、$6$ 的访问顺序也可以任意交换——它们都是合法的 BFS 序列。复杂度分析时间复杂度所有顶点都会入队并出队一次使用 $O(|V|)$ 时间在遍历邻接顶点的过程中由于是无向图所有边都会被访问 $2$ 次使用 $O(2|E|)$ 时间总体 $O(|V| |E|)$。空间复杂度列表res、哈希集合visited、队列que中的顶点数量最多为 $|V|$使用 $O(|V|)$ 空间。深度优先遍历DFS核心思想走到尽头再回头深度优先遍历是一种优先走到底、无路可走再回头的遍历方式。从左上角顶点出发访问当前顶点的某个邻接顶点直到走到尽头时返回再继续走到尽头并返回以此类推直至所有顶点遍历完成。这种“走到尽头再返回”的算法范式通常基于递归实现。与 BFS 类似DFS 也需要借助哈希集合visited记录已被访问的顶点以避免重复访问。递归参考实现下面是仓库中 graph_dfs.py 的核心代码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) # 递归访问邻接顶点 def graph_dfs(graph: GraphAdjList, start_vet: Vertex) - list[Vertex]: 深度优先遍历 res [] # 顶点遍历序列 visited set[Vertex]() # 哈希集合记录已被访问的顶点 dfs(graph, visited, res, start_vet) return res对比 BFS 与 DFS 两份代码可以看到两者的结构差异正来自驱动方式的不同关注点BFSDFS待处理顶点容器显式队列que隐式递归调用栈扩展顶点的时机循环中“出队即扩展”递归中“入栈即扩展”visited标记时机入队时标记进入递归记录访问时标记公共部分都遍历graph.adj_list[vet]邻接表并跳过已访问顶点仓库中的图示用虚线刻画了递归过程直虚线代表向下递推表示开启了一个新的递归方法来访问新顶点曲虚线代表向上回溯表示此递归方法已经返回回溯到了开启此方法的位置。建议将动画图与代码结合起来在脑中模拟或者用笔画下来整个 DFS 过程包括每个递归方法何时开启、何时返回。遍历序列是否唯一与广度优先遍历类似深度优先遍历序列的顺序也不是唯一的。给定某顶点先往哪个方向探索都可以即邻接顶点的顺序可以任意打乱都是深度优先遍历。以树的遍历为例“根 → 左 → 右”“左 → 根 → 右”“左 → 右 → 根”分别对应前序、中序、后序遍历它们展示了三种遍历优先级然而这三者都属于深度优先遍历。复杂度分析时间复杂度所有顶点都会被访问 $1$ 次使用 $O(|V|)$ 时间所有边都会被访问 $2$ 次使用 $O(2|E|)$ 时间总体 $O(|V| |E|)$。空间复杂度列表res、哈希集合visited的顶点数量最多为 $|V|$递归深度最大为 $|V|$对应一条从起点贯穿到最远的路径因此使用 $O(|V|)$ 空间。运行验证驱动代码与测试仓库中每个参考文件末尾都带有可直接运行的 Driver Code便于对照输出验证理解。以 graph_dfs.py 为例示例图由 $7$ 个顶点 $0 \sim 6$ 和 $6$ 条边构成v vals_to_vets([0, 1, 2, 3, 4, 5, 6]) edges [ [v[0], v[1]], [v[0], v[3]], [v[1], v[2]], [v[2], v[5]], [v[4], v[5]], [v[5], v[6]], ] graph GraphAdjList(edges) res graph_dfs(graph, v[0]) # 从顶点 0 出发的深度优先遍历按邻接表插入顺序模拟递归展开可以得到顶点序列0, 1, 2, 5, 4, 6, 3从 $0$ 出发沿 $0\to1\to2\to5$ 一直走到底在 $5$ 处先后扩展 $4$走到底回溯和 $6$最后回到 $0$ 再访问 $3$。BFS 的 Driver Codegraph_bfs.py则使用 $10$ 个顶点、$12$ 条边更稠密的图输出顶点序列0, 1, 3, 2, 4, 6, 5, 7, 8顶点 $9$ 未参与任何边从源码结构看GraphAdjList构造时仅注册出现在边中的顶点因此不会被遍历到。此外Go 版还附带了单元测试graph_dfs_test.go 与 graph_bfs_test.go 构造与 Python 版相同的示例图并调用遍历函数可以在 CI 中持续验证多语言实现的行为一致性。小结BFS 与 DFS 是图论中两类互补的遍历范式BFS 用队列驱动、逐层向外扩展天然适合求“最短路最少边数”类问题DFS 用递归栈驱动、深入到底再回溯天然适合路径枚举、连通性判定等问题。两者都以邻接表为载体获取邻接顶点以visited哈希集合保证每个顶点只被访问一次时间复杂度均为 $O(|V| |E|)$空间复杂度均为 $O(|V|)$。遍历序列在“等距/同层顶点可任意换序”的意义上不唯一因此比较两份遍历结果时应关注相对层次BFS或前驱关系DFS而非逐位相等。仓库中codes/python、codes/java、codes/go、codes/javascript、codes/c等目录提供了同一算法的对照实现适合作为学习遍历算法时逐语言精读的入口。【免费下载链接】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），仅供参考