BFS - wenzhoullq/leetcode GitHub Wiki
- 模板一
List<Integer> ans=new ArrayList<>();
Queue<TreeNode> q=new LinkedList<>();
if(root!=null) q.add(root);
while(!q.isEmpty()){
int size=q.size();
int max=Integer.MIN_VALUE;
for(int i=0;i<size;i++){
TreeNode temp=q.poll();
if(max<temp.val) max=temp.val;
if(temp.left!=null) q.add(temp.left);
if(temp.right!=null) q.add(temp.right);
}
ans.add(max);
}
return ans;
- 模板二
int bfs(int starty,int startx,int target){
if(matrix[starty][startx]==target) return 0;
Queue<int[]> q=new LinkedList<>();
boolean[][] visit=new boolean[leny][lenx];
q.add(new int[]{starty,startx});
visit[starty][startx]=true;
int ans=0;
while(!q.isEmpty()){
int size=q.size();
for(int i=0;i<size;i++){
int[] temp=q.poll();
int y=temp[0],x=temp[1];
for(int[] dir:direct){
int yy=y+dir[0],xx=x+dir[1];
if(yy<0||xx<0||yy==leny||xx==lenx||visit[yy][xx]||matrix[yy][xx]==0) continue;
visit[yy][xx]=true;
if(matrix[yy][xx]==target) return ans+1;
q.add(new int[]{yy,xx});
}
}
ans++;
}
return -1;
}
模板一适合于树的层次遍历,模板二适合于图的遍历,并且模板二因为枝剪,它的时间复杂度远低于模板一
最简单的BFS
934. 最短的桥 采用模板2降低时间复杂度
入度问题
2360. 图中的最长环先把非环的去掉,然后再进行dfs
最为简单的BFS,但是需要注意的是,最多和最少的思路不一样,最多是终点出发探索所有的可能的出发点;最少是出发点最早发现可能的终点
1036. 逃离大迷宫//值得注意的是,因为区域过大,不能使用visit[][],需要使用hash算法的HashSet来替代,然后通过访问的格子数来确定是否被封锁
重点在于类的设计和状态的变化,甚至某些题会有时间的考虑
推箱子 用hash记录状态
864. 获取所有钥匙的最短路径 (类似于推箱子)
838. 推多米诺(多米诺类会考虑到时间问题,在新的状态下不急于加入Q,而是将加入一个暂时队列,如果两次受力则去除)
1298. 你能从盒子里获得的最大糖果数(加一个标志位,如果增加新的箱子则重新)
多源BFS关键词是最多
xx是别的算法,BFS是用来找那个最小路径
难点在于构图,如果当点数过多(如100000),则此时不能用邻接表和邻接矩阵,得用类似于克鲁斯卡尔算法德思想去构造
815. 公交路线 难点在于构图,因为很容易出稀疏矩阵,因此用路线当作对象,然后遍历访问,对访问过的点和路线进行删除做到枝剪