尧图网站建设 
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 算法》英文版 Graph Traversal 章节 展开系统讲解有向/无向图的两大基础遍历算法——广度优先遍历BFS与深度优先遍历DFS从树是图的特例这一出发点讲清算法思想给出可一键运行的完整代码并结合仓库中graph_bfs/graph_dfs/graph_adjacency_list等真实源码剖析队列与递归的实现细节、visited哈希集合的去重机制以及二者的时空复杂度与序列不唯一性。读完本文你将能够在任意支持的语言代码库中独立实现并验证图的两种遍历。为什么图遍历是树遍历的推广树描述的是一对多的层级关系而图的自由度更高可以表示任意多对多关系。因此可以把树看作图的一种特殊情况树的遍历操作自然也是图遍历操作的一种特殊情况仅当图中恰好构成一棵树时二者表现一致。图和树的遍历都依赖搜索算法来驱动。常见的图遍历方法同样分为两类广度优先遍历Breadth-First Traversal对应广度优先搜索BFS深度优先遍历Depth-First Traversal对应深度优先搜索DFS。两条遍历路线覆盖了从起点出发一层一层扫与一头扎到底再回头的两种典型策略是后续图算法如拓扑排序、最短路径、连通分量、二分图判定等的共同基石。广度优先搜索由近及远的逐层扩散广度优先搜索从近到远推进从给定顶点出发始终优先访问距离最近的顶点再向外一层层扩展。如图所示从左上角顶点出发先遍历该顶点的全部邻接顶点再遍历下一层顶点的全部邻接顶点依此类推直到所有顶点都被访问。BFS 的算法实现BFS 通常借助队列实现见下方代码。队列具有先进先出的特性与 BFS由近及远的思路天然吻合。将起始顶点startVet加入队列进入循环每轮循环弹出队首顶点并记为已访问随后把该顶点的全部邻接顶点加入队尾重复步骤 2直到所有顶点都被访问完毕。为了防止重复访问顶点还需要一个哈希集合visited记录哪些顶点已被访问。!!! tip 为什么用哈希集合哈希集合hash set可看作只存 key、不存 value 的哈希表对 key 的插入、删除、查找、更新均可在 $O(1)$ 时间内完成。基于 key 的唯一性哈希集合通常被用于数据去重等场景。在图的遍历中用它来判断某个顶点是否已访问恰到好处。仓库在 Python 中的实现位于 graph_bfs.py其核心代码如下为便于对照保留与仓库文件一致的实现逻辑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从源码可以提炼出三个值得注意的细节入队即标记visited.add(adj_vet)与que.append(adj_vet)同时发生即加入队列的那一刻就记为已访问。如果等到真正出队时才标记同一个顶点可能被多个邻接顶点重复入队导致队列膨胀、遍历序列冗余。这是 BFS 实现中容易踩坑的边界点。队列与集合分工明确队列que决定下一个访问谁集合visited决定哪些不再处理。二者最大规模都受顶点数 $|V|$ 约束。邻接表是前提代码通过graph.adj_list[vet]获取某顶点的全部邻接顶点说明当前实现建立在邻接表的图表示之上详见后文源码剖析。参考文档中的分步示意图graph_bfs_step1..11建议结合代码逐帧对照第几层顶点何时入队、何时出队以加深理解。!!! question 广度优先遍历序列是否唯一不唯一。广度优先搜索只要求按由近及远的顺序遍历**同一距离层内顶点的访问顺序可以被任意打乱**。以上图为例顶点 $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记录已访问顶点、避免走回头路。仓库在 Python 中的实现位于 graph_dfs.py核心逻辑拆分为递归辅助函数dfs与对外入口graph_dfsdef 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 resDFS 的算法流程可通过示意图理解图中的两类虚线分别代表两种动作竖直虚线表示向下递归发起一次新的递归调用来访问新顶点弯曲虚线表示向上回溯本次递归调用返回到发起处。文档建议将分步图graph_dfs_step1..11与代码结合在脑中或纸上完整模拟每次递归何时开始、何时返回的整个过程。!!! question 深度优先遍历序列是否唯一与 BFS 类似深度优先遍历序列同样不唯一。给定某个顶点可以优先选择任意一个探索方向换言之邻接顶点的遍历顺序可以任意调整得到的结果仍然是深度优先搜索。 以树的遍历为例根 → 左 → 右左 → 根 → 右左 → 右 → 根分别对应前序、中序、后序遍历。它们代表三种不同的访问优先级但**都属于深度优先搜索**。这直观地说明DFS 定义的是一类先深入后回溯的策略而不是某一条固定路径。DFS 复杂度分析时间复杂度每个顶点被访问 $1$ 次用时 $O(|V|)$所有边被访问 $2$ 次用时 $O(2|E|)$。合计 $O(|V| |E|)$与 BFS 同阶。空间复杂度列表res与哈希集合visited最多容纳 $|V|$ 个顶点递归调用栈的最大深度也为 $|V|$例如遍历一条链状图因此总空间为 $O(|V|)$。这也意味着对极深的图进行 DFS 时要留意递归栈溢出的风险必要时可改写为显式栈迭代。源码级剖析为什么遍历建立在邻接表之上上述两段代码都通过graph.adj_list[vet]枚举某顶点的所有邻接顶点。图在仓库中主要有两种存储结构本节结合真实代码说明遍历对邻接表的依赖及其合理性。邻接表GraphAdjList的实现见 graph_adjacency_list.py。它用一个dict[Vertex, list[Vertex]]以顶点为 key、该顶点的全部邻接顶点列表为 value。add_edge()双向追加无向图add_vertex()负责为邻接表新增空列表。BFS/DFS 的核心动作是取出某顶点的全部邻居在邻接表上只需一次哈希查找加一次列表遍历代价正比于该顶点的度degree与全图规模无关。邻接矩阵对应实现见 graph_adjacency_matrix.cPython 侧为 graph_adjacency_matrix.py。若要枚举一个顶点的邻居必须扫描整行 $|V|$ 个元素遍历全部顶点累计需要 $O(|V|^2)$。因此在需要高频枚举邻居的图遍历场景中稀疏图更适合用邻接表承载 BFS/DFS。visited集合所存元素在不同语言中的形态略有差异但语义一致Python用set[Vertex]Vertex是仓库自定义的顶点类见 modules/vertex.py集合按对象身份去重C用unordered_setVertex *直接对顶点指针做哈希比较见 graph_bfs.cpp 与 graph_dfs.cppJava用SetVertexHashSet顶点对象按equals/hashCode判重见 graph_bfs.java。可见记录已访问与枚举邻居这两大基础能力决定了 BFS/DFS 的通用实现骨架在跨语言时高度一致只是容器与判重语义随语言惯例微调。一键运行与结果验证仓库为每种语言都提供了可直接运行的驱动代码driver code以 BFS 的 Python 驱动为例见 graph_bfs.py# 初始化无向图10 个顶点 12 条边 v vals_to_vets([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]) edges [ [v[0], v[1]], [v[0], v[3]], [v[1], v[2]], [v[1], v[4]], [v[2], v[5]], [v[3], v[4]], [v[3], v[6]], [v[4], v[5]], [v[4], v[7]], [v[5], v[8]], [v[6], v[7]], [v[7], v[8]], ] graph GraphAdjList(edges) # 广度优先遍历 res graph_bfs(graph, v[0]) print(vets_to_vals(res))运行方式也很直接python codes/python/chapter_graph/graph_bfs.py python codes/python/chapter_graph/graph_dfs.pyDFS 的 Python 驱动则构造了一个 7 顶点、6 条边的无向图同样打印遍历序列见 graph_dfs.py。运行后可以把打印出的顶点序列与上方的分步图逐层核对BFS 序列按到起点的距离严格分层DFS 序列则表现为一条深入—回溯—再深入的路径。仓库还提供了批量自测入口 test_all.py可一次性校验该语言下全部示例。若希望用 C 复现相关示例位于 chapter_graph/CMakeLists.txt其中定义了graph_bfs与graph_dfs两个可执行目标add_executable(graph_bfs graph_bfs.cpp) add_executable(graph_dfs graph_dfs.cpp)从codes/cpp目录使用 CMake 生成工程并构建后即可运行graph_bfs、graph_dfs两个目标观察输出。驱动代码中valsToVets(...)、vetsToVals(...)等工具函数封装在 utils 中负责顶点值类型与顶点对象之间的互转便于打印。同一算法的多语言全景图遍历属于通用基础算法仓库在 codes 下为绝大多数语言都提供了 BFS/DFS 对照实现例如语言BFS 文件DFS 文件Pythongraph_bfs.pygraph_dfs.pyCgraph_bfs.cppgraph_dfs.cppJavagraph_bfs.javagraph_dfs.javaCgraph_bfs.cgraph_dfs.cGograph_bfs.gograph_dfs.goJavaScriptgraph_bfs.jsgraph_dfs.js此外TypeScript、C#、Swift、Rust、Ruby、Kotlin、Dart 等语言也在 codes 各自的chapter_graph目录下提供了同名实现可作为学习同一算法在不同语言范式对象指针、值类型、泛型容器下如何落地的最佳对照素材。BFS 与 DFS 对比小结对比维度广度优先遍历BFS深度优先遍历DFS核心数据结构队列FIFO递归调用栈或显式栈访问顺序由近及远逐层扩散先深入到底再逐层回溯是否需标记已访问是入队时标记是递归进入前标记时间复杂度$O(VE)$$O(VE)$空间复杂度$O(V)$队列$O(V)$递归栈最坏深度遍历序列是否唯一不唯一同层可换序不唯一邻接顺序可换序典型后续应用无权图最短路径、层级扩散类问题连通分量、拓扑排序、回溯搜索等需要注意的是以上时间复杂度的前提是图以邻接表存储且遍历全部顶点与边若使用邻接矩阵枚举邻居的代价将上升为 $O(|V|^2)$。文中所有结论与代码均可直接在仓库中复核算法正文见 Graph Traversal 章节图中插图与逐帧步骤图位于 graph_traversal.assets章节练习可参考 exercises.md更完整的图论知识体系图的表示、增删改查则可继续阅读 chapter_graph 目录 下的 graph.md 与 graph_operations.md。【免费下载链接】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 算法：图的广度优先遍历与深度优先遍历（BFS / DFS）实现与源码级解析
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 算法》英文版 Graph Traversal 章节 展开系统讲解有向/无向图的两大基础遍历算法——广度优先遍历BFS与深度优先遍历DFS从树是图的特例这一出发点讲清算法思想给出可一键运行的完整代码并结合仓库中graph_bfs/graph_dfs/graph_adjacency_list等真实源码剖析队列与递归的实现细节、visited哈希集合的去重机制以及二者的时空复杂度与序列不唯一性。读完本文你将能够在任意支持的语言代码库中独立实现并验证图的两种遍历。为什么图遍历是树遍历的推广树描述的是一对多的层级关系而图的自由度更高可以表示任意多对多关系。因此可以把树看作图的一种特殊情况树的遍历操作自然也是图遍历操作的一种特殊情况仅当图中恰好构成一棵树时二者表现一致。图和树的遍历都依赖搜索算法来驱动。常见的图遍历方法同样分为两类广度优先遍历Breadth-First Traversal对应广度优先搜索BFS深度优先遍历Depth-First Traversal对应深度优先搜索DFS。两条遍历路线覆盖了从起点出发一层一层扫与一头扎到底再回头的两种典型策略是后续图算法如拓扑排序、最短路径、连通分量、二分图判定等的共同基石。广度优先搜索由近及远的逐层扩散广度优先搜索从近到远推进从给定顶点出发始终优先访问距离最近的顶点再向外一层层扩展。如图所示从左上角顶点出发先遍历该顶点的全部邻接顶点再遍历下一层顶点的全部邻接顶点依此类推直到所有顶点都被访问。BFS 的算法实现BFS 通常借助队列实现见下方代码。队列具有先进先出的特性与 BFS由近及远的思路天然吻合。将起始顶点startVet加入队列进入循环每轮循环弹出队首顶点并记为已访问随后把该顶点的全部邻接顶点加入队尾重复步骤 2直到所有顶点都被访问完毕。为了防止重复访问顶点还需要一个哈希集合visited记录哪些顶点已被访问。!!! tip 为什么用哈希集合哈希集合hash set可看作只存 key、不存 value 的哈希表对 key 的插入、删除、查找、更新均可在 $O(1)$ 时间内完成。基于 key 的唯一性哈希集合通常被用于数据去重等场景。在图的遍历中用它来判断某个顶点是否已访问恰到好处。仓库在 Python 中的实现位于 graph_bfs.py其核心代码如下为便于对照保留与仓库文件一致的实现逻辑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从源码可以提炼出三个值得注意的细节入队即标记visited.add(adj_vet)与que.append(adj_vet)同时发生即加入队列的那一刻就记为已访问。如果等到真正出队时才标记同一个顶点可能被多个邻接顶点重复入队导致队列膨胀、遍历序列冗余。这是 BFS 实现中容易踩坑的边界点。队列与集合分工明确队列que决定下一个访问谁集合visited决定哪些不再处理。二者最大规模都受顶点数 $|V|$ 约束。邻接表是前提代码通过graph.adj_list[vet]获取某顶点的全部邻接顶点说明当前实现建立在邻接表的图表示之上详见后文源码剖析。参考文档中的分步示意图graph_bfs_step1..11建议结合代码逐帧对照第几层顶点何时入队、何时出队以加深理解。!!! question 广度优先遍历序列是否唯一不唯一。广度优先搜索只要求按由近及远的顺序遍历**同一距离层内顶点的访问顺序可以被任意打乱**。以上图为例顶点 $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记录已访问顶点、避免走回头路。仓库在 Python 中的实现位于 graph_dfs.py核心逻辑拆分为递归辅助函数dfs与对外入口graph_dfsdef 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 resDFS 的算法流程可通过示意图理解图中的两类虚线分别代表两种动作竖直虚线表示向下递归发起一次新的递归调用来访问新顶点弯曲虚线表示向上回溯本次递归调用返回到发起处。文档建议将分步图graph_dfs_step1..11与代码结合在脑中或纸上完整模拟每次递归何时开始、何时返回的整个过程。!!! question 深度优先遍历序列是否唯一与 BFS 类似深度优先遍历序列同样不唯一。给定某个顶点可以优先选择任意一个探索方向换言之邻接顶点的遍历顺序可以任意调整得到的结果仍然是深度优先搜索。 以树的遍历为例根 → 左 → 右左 → 根 → 右左 → 右 → 根分别对应前序、中序、后序遍历。它们代表三种不同的访问优先级但**都属于深度优先搜索**。这直观地说明DFS 定义的是一类先深入后回溯的策略而不是某一条固定路径。DFS 复杂度分析时间复杂度每个顶点被访问 $1$ 次用时 $O(|V|)$所有边被访问 $2$ 次用时 $O(2|E|)$。合计 $O(|V| |E|)$与 BFS 同阶。空间复杂度列表res与哈希集合visited最多容纳 $|V|$ 个顶点递归调用栈的最大深度也为 $|V|$例如遍历一条链状图因此总空间为 $O(|V|)$。这也意味着对极深的图进行 DFS 时要留意递归栈溢出的风险必要时可改写为显式栈迭代。源码级剖析为什么遍历建立在邻接表之上上述两段代码都通过graph.adj_list[vet]枚举某顶点的所有邻接顶点。图在仓库中主要有两种存储结构本节结合真实代码说明遍历对邻接表的依赖及其合理性。邻接表GraphAdjList的实现见 graph_adjacency_list.py。它用一个dict[Vertex, list[Vertex]]以顶点为 key、该顶点的全部邻接顶点列表为 value。add_edge()双向追加无向图add_vertex()负责为邻接表新增空列表。BFS/DFS 的核心动作是取出某顶点的全部邻居在邻接表上只需一次哈希查找加一次列表遍历代价正比于该顶点的度degree与全图规模无关。邻接矩阵对应实现见 graph_adjacency_matrix.cPython 侧为 graph_adjacency_matrix.py。若要枚举一个顶点的邻居必须扫描整行 $|V|$ 个元素遍历全部顶点累计需要 $O(|V|^2)$。因此在需要高频枚举邻居的图遍历场景中稀疏图更适合用邻接表承载 BFS/DFS。visited集合所存元素在不同语言中的形态略有差异但语义一致Python用set[Vertex]Vertex是仓库自定义的顶点类见 modules/vertex.py集合按对象身份去重C用unordered_setVertex *直接对顶点指针做哈希比较见 graph_bfs.cpp 与 graph_dfs.cppJava用SetVertexHashSet顶点对象按equals/hashCode判重见 graph_bfs.java。可见记录已访问与枚举邻居这两大基础能力决定了 BFS/DFS 的通用实现骨架在跨语言时高度一致只是容器与判重语义随语言惯例微调。一键运行与结果验证仓库为每种语言都提供了可直接运行的驱动代码driver code以 BFS 的 Python 驱动为例见 graph_bfs.py# 初始化无向图10 个顶点 12 条边 v vals_to_vets([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]) edges [ [v[0], v[1]], [v[0], v[3]], [v[1], v[2]], [v[1], v[4]], [v[2], v[5]], [v[3], v[4]], [v[3], v[6]], [v[4], v[5]], [v[4], v[7]], [v[5], v[8]], [v[6], v[7]], [v[7], v[8]], ] graph GraphAdjList(edges) # 广度优先遍历 res graph_bfs(graph, v[0]) print(vets_to_vals(res))运行方式也很直接python codes/python/chapter_graph/graph_bfs.py python codes/python/chapter_graph/graph_dfs.pyDFS 的 Python 驱动则构造了一个 7 顶点、6 条边的无向图同样打印遍历序列见 graph_dfs.py。运行后可以把打印出的顶点序列与上方的分步图逐层核对BFS 序列按到起点的距离严格分层DFS 序列则表现为一条深入—回溯—再深入的路径。仓库还提供了批量自测入口 test_all.py可一次性校验该语言下全部示例。若希望用 C 复现相关示例位于 chapter_graph/CMakeLists.txt其中定义了graph_bfs与graph_dfs两个可执行目标add_executable(graph_bfs graph_bfs.cpp) add_executable(graph_dfs graph_dfs.cpp)从codes/cpp目录使用 CMake 生成工程并构建后即可运行graph_bfs、graph_dfs两个目标观察输出。驱动代码中valsToVets(...)、vetsToVals(...)等工具函数封装在 utils 中负责顶点值类型与顶点对象之间的互转便于打印。同一算法的多语言全景图遍历属于通用基础算法仓库在 codes 下为绝大多数语言都提供了 BFS/DFS 对照实现例如语言BFS 文件DFS 文件Pythongraph_bfs.pygraph_dfs.pyCgraph_bfs.cppgraph_dfs.cppJavagraph_bfs.javagraph_dfs.javaCgraph_bfs.cgraph_dfs.cGograph_bfs.gograph_dfs.goJavaScriptgraph_bfs.jsgraph_dfs.js此外TypeScript、C#、Swift、Rust、Ruby、Kotlin、Dart 等语言也在 codes 各自的chapter_graph目录下提供了同名实现可作为学习同一算法在不同语言范式对象指针、值类型、泛型容器下如何落地的最佳对照素材。BFS 与 DFS 对比小结对比维度广度优先遍历BFS深度优先遍历DFS核心数据结构队列FIFO递归调用栈或显式栈访问顺序由近及远逐层扩散先深入到底再逐层回溯是否需标记已访问是入队时标记是递归进入前标记时间复杂度$O(VE)$$O(VE)$空间复杂度$O(V)$队列$O(V)$递归栈最坏深度遍历序列是否唯一不唯一同层可换序不唯一邻接顺序可换序典型后续应用无权图最短路径、层级扩散类问题连通分量、拓扑排序、回溯搜索等需要注意的是以上时间复杂度的前提是图以邻接表存储且遍历全部顶点与边若使用邻接矩阵枚举邻居的代价将上升为 $O(|V|^2)$。文中所有结论与代码均可直接在仓库中复核算法正文见 Graph Traversal 章节图中插图与逐帧步骤图位于 graph_traversal.assets章节练习可参考 exercises.md更完整的图论知识体系图的表示、增删改查则可继续阅读 chapter_graph 目录 下的 graph.md 与 graph_operations.md。【免费下载链接】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），仅供参考