广度优先搜索是图论里比较常用的算法,但是也不仅仅适用于图,有一些问题需要我们抽象成图,这也是比较难的一部分。
bfs框架
bfs的思路就是一层一层搜索,在复杂的图中可能还需要标记一下该节点是否被搜过。bfs是可以被抽象成框架的。树的层序遍历是1最简单的bfs,因为树也是一种特殊的图。以层序遍历为例看一下bfs的框架。
1 | class Solution { |
核心框架可以抽象为
1 | //起始节点入队 |
由于是树的层序遍历可以看到其实很多步骤都是不必要的,比如记录当前队列size。但是大部分题都需要这么做。
以二叉树的一道题为例
这道题求二叉树的最小深度
这题要求根节点到最近叶子节点的最短路径上的节点数量。
用层序遍历的方法考虑,遍历到最靠近根节点的叶子结点那层就可以停止遍历。就是两个节点都为null的节点。
1 | class Solution { |
这道题可以用dfs做,在深搜那里再总结一下。
bfs还可以用来求一些益智问题,关键在于把问题抽象成图,考虑起始状态和终止状态。
比较经典的问题就是8数码,Leetcode上有一道类似的leetcode773滑动谜题 就是把9个格子换成了6个格子。思路都一样。
这题也是个最短路问题,和上一道一样,bfs在边权都相等的时候是可以求出最短路的。
这类题的难点是建图。一个是状态表示部分,一般的图都是一个数字表示一个节点,这道题我们可以用长度为6的字符串来表示一个节点。第二个是每个状态之间的距离。也就是每条边的长度。题目中说每次可以上下左右移动,那么这四个状态和之前的那个距离就为1,可以看作是下一层。
先看下代码。
1 | int slidingPuzzle(vector<vector<int>>& board) { |
可以看到,除了队列之外,还维护了一个dist映射,用来表示每个节点的最短距离,还可以用来判断该节点是否是第一次访问。在从当前状态扩展到下个状态时还有个一维到二维的坐标变换。
bfs还有一个应用,就是求图的拓扑序。这个其实生活中用的很多,比如一个工程,有很多活动流程,这些活动的执行都是要有一定先后顺序的。用有向图的顶点表示活动,有向边表示活动的先后顺序的网络叫做AOV网络。对图求拓扑序还可以判断图中是否有自环。
leetcode207 这题就是判断是否有自环,还有leetcode210 和这题一样,只不过把拓扑序存在了一个数组里返回。
Bfs求拓扑序的步骤是 1、输入网络(建图)2、选出入度为0的节点入队 3、每次pop访问这个节点的同时删除他的所有出边。循环2、3步。直到没有入度为0的节点为止。如果这时图中还有顶点没有访问到的话,就说明图中存在有向环。因为这时剩下的顶点都有入边。
1 | bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { |
这里入参用边缘列表来表示图,为了建图以及计算出入边,用二维矩阵(邻接表)来表示图。每一行第一个数代表一个节点,这一行表示他的出边连接的节点。
1 | bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { |
其实bfs本质就是图的层序遍历,也可以看作是暴力枚举。只不过这个枚举的顺序和性质可以让我们计算最短距离。