【算法】图的广度优先遍历

图的广度优先遍历

图的广度优先遍历 （Breadth-First-Search，简称 BFS）是一种图形搜索算法，它从图的某一节点出发，按照一定的顺序依次访问该节点所有未被访问的邻接点，然后再从这些已访问的邻接点出发，继续访问它们各自的未被访问的邻接点，以此类推，直到访问完图中所有可达节点。

在广度优先遍历中，通常使用一个队列来存储待访问的节点。初始时，将起始节点放入队列。然后，执行以下操作直到队列为空：从队列中取出一个节点，访问该节点，并将其标记为已访问。将该节点的所有未被访问的邻接节点加入队列。

广度优先遍历的算法步骤如下：

1. 初始化所有节点均未被访问，并初始化一个空队列。
2. 从图中的某个节点 v 出发，访问 v 并标记其已被访问，将 v 入队。
3. 如果队列非空，则继续执行，否则算法结束。
4. 将队头元素 v 出队，依次访问 v 的所有未被访问的邻接点，标记已被访问并入队。
5. 重复步骤 3 和步骤 4，直到访问完图中所有可达节点。

广度优先遍历的秘籍是先被访问的节点，其邻接点先被访问。根据广度优先遍历的秘籍，可以设置一个辅助数组 visited[i]=false，表示第 i 个节点未被访问；visited[i]=true，表示第 i 个节点已被访问。

广度优先遍历的实现方式可以是基于邻接矩阵或邻接表。

基于邻接矩阵的实现方式是用一个一维数组来表示顶点，用一个二维数组来实现对边的存储，若 a 和 b 之间有边，那就让二位数组中的这两个数据对应的数据中填入 1；没有回路用一个很大的树来表示就好了。

基于邻接表的实现方式是将图中的节点存储在链表中，每个节点包含其数据和指向其邻接点的指针。

算法题目

• 909.蛇梯棋.js
• 433.最小基因变化.js
• 127.单词接龙.js