4.2 图的遍历（广度优先搜索BFS、深度优先搜索DFS）

文档摘要

4.2 图的遍历（广度优先搜索BFS、深度优先搜索DFS） 4.2 图的遍历（广度优先搜索BFS、深度优先搜索DFS）图的遍历是指从图中的某个顶点出发，按照某种策略访问图中的所有顶点，并且每个顶点只访问一次。图的遍历是图论中的一个基本问题，也是许多图算法的基础。常见的图遍历算法有两种：广度优先搜索（BFS）和深度优先搜索（DFS）。 4.2.1 广度优先搜索（BFS） 1. 算法思想广度优先搜索（BFS）是一种按层遍历图的算法。它从起始顶点开始，首先访问起始顶点的所有邻居，然后访问这些邻居的邻居，以此类推，直到访问完所有可达顶点。BFS 类似于水波扩散，一层一层地向外扩展。 2. 算法步骤选择一个起始顶点。创建一个队列，并将加入队列。