图的广度优先搜索(BFS)思路

与之前深度优先搜索算法相似,广度优先搜索算法也是一个主要解决图问题的搜索算法。通过之前的学习,我们知道深度优先搜索算法可以应用于二叉树问题,或最大面积的搜索,但一些经典的路径问题,如求解图中的最短路径问题,则需要应用广度优先搜索算法。

广度优先搜索算法与深度优先搜索算法类似,也是查询的方法之一,它也是从某个状态出发查询可以到达的所有状态。但不同于深度优先搜索算法,广度优先搜索算法总是先去查询距离初始状态最近的状态,而不是一直向最深处查询结果。

广度优先搜索算法本质上是查找算法。为了解决查找问题,之前我们介绍了很多查找算法,如顺序查找、二分查找、哈希查找。广度优先搜索算法更多地针对图的搜索,此外,广度优先搜索算法可以解决单一起点的最短路径问题,最短路径问题会在后面细讲解。

既然可以被称为搜索算法,那么广度优先搜索算法会与深度优先搜索算法具有一些相通的性质,如广度优先搜索算法也可以解决走迷宫问题。但如果使用广度优先搜索算法走迷宫,因为其搜索的条件发生了改变,搜索的宗旨就不在于最快地、有逻辑地走出迷宫,而在于寻遍迷宫的每一个角落。

现在我们可以假设迷宫里的某一个角落有一个宝藏,我们需在迷宫中找到宝藏。如果这时候我们依然使用深度优先搜索算法,因为此时求解问题的目标不是走出迷宫而是寻找宝藏,我们会因为无法巧妙地设定递归退出条件而进入死胡同或者漫无目的地搜索。

如图 1 所示,此时深度优先搜索算法进入了死胡同,无法再进行移动(根据不重复原则),而仍有区域没有被遍历到。所以很明显深度优先搜索不是找宝藏的高效算法。
深度优先搜索算法找宝藏
图 1:深度优先搜索算法找宝藏

而广度优先搜索迷宫的方法则如图 2~图 4 所示。
广度优先搜索找宝藏(1)
图 2:广度优先搜索找宝藏(1)

广度优先搜索找宝藏(2)
图 3:广度优先搜索找宝藏(2)

广度优先搜索找宝藏(3)
图 4:广度优先搜索找宝藏(3)

对比深度优先搜索算法,可以看出,广度优先搜索算法在搜索所有答案的时候会采用由近及远的方式来搜索。先访问离起始点最近的点,再访问远一些的点。换句话说,广度优先搜索会优先访问一步可以直接到达的点,再访问走两步、三步或更多步可以到达的点。

因此,广度优先搜索算法也叫作层次搜索算法,一层一层地去寻找问题的答案。在一层一层地遍历最近的点时,我们需要通过一定的数据结构来记录这些即将遍历的点。在兼顾高效且便利的前提下,我们将采用队列的数据存储方式来记录即将遍历的点。

现在我们已经对图的广度优先搜索的基本思想有了了解,下面将以实际例子进行具体介绍。请点击:广度优先搜索应用实例—艰难旅行