2.6　用广度优先搜索在网格中找到最短路径

广度优先搜索（BFS）算法是另一个用于图遍历的基础技术，目的是用尽可能最少的步骤获取最短路径，并且权衡内存方面的消耗，尤其针对高端主机和计算机的游戏。

准备工作

广度优先搜索是上层算法，依赖于每个图的通用函数的实现，所以这个算法在Graph类中实现。

操作步骤

虽然本节只定义一个函数，但是请注意代码中的注释，以便更好地理解代码逻辑：

1. 声明GetPathBFS函数：

2. 声明并初始化在算法中需要用到的变量：

3. 实现查找路径的BFS算法：

运行原理

BFS算法与DFS算法相似，因为它也基于图的顺序遍历，但是不像DFS那样用栈，BFS使用队列存储访问过的节点。

延伸阅读

你可能没有注意到这里没有实现BuildPath方法，因为在2.5节已经讨论过。