BFS算法(——模板习题与总结)

时间:2022-06-01 14:06:40

  首先需要说明的是BFS算法(广度优先算法)本质上也是枚举思想的一种体现,本身效率不是很高,当数据规模很小的时候还是可以一试的。其次很多人可能有这样的疑问,使用搜索算法的时候,到底选用DFS还是BFS,博主觉得对于最短路搜索来说是都可以的,数据规模不大,广搜解决最短路的效率要高一些,还有对于搜索过程中搜索的单位为1时,广搜更合适。

  这里总结一下BFS算法,DFS是一条路走到黑,不行再回退一步,直到所有的路都试一遍,而BFS则是需要有一种层的概念,每次走到一个状态,将该层所有可能的状态都加入队列,直到某一个状态符合条件或者队列拓展结束。

  具体算法,先将一个起点加入队列,将该点的下一个所有可能的情况都加入队列,再按照加入队列的顺序,一一进行搜索。直到队列为空或者符合条件而结束搜索。

  下面上一道练习题:http://poj.org/problem?id=3278    这道题中的人可以有三种走法,一旦走到直接结束搜索,相对于DFS来说效率更高些。

  下面上一道经典的迷宫问题:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2412这道题挺有意思的,也可以使用DFS来写。

  之前都是使用结构体数组模拟队列操作,也可以使用C++STL中的队列容器来写。