模板"/>
BFS模板
思想：
start 进入BFS的起始
target 目标
queue< > 这个泛型注意在给的是矩阵的时候可以写个类 来代替 例Point
Set<> 承装访问过的结点
size 每一层的队列长度 动态 指定了一层的数据
step 最短的步数
分析问题：
一般求最短路径 使用BFS 返回的这个最短路径都是step
因为while循环一次step++ 每次都是遍历一整层
// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {Queue<Node> q; // 核心数据结构Set<Node> visited; // 避免走回头路q.offer(start); // 将起点加入队列visited.add(start);int step = 0; // 记录扩散的步数while (q not empty) {int sz = q.size();/* 将当前队列中的所有节点向四周扩散 */for (int i = 0; i < sz; i++) {Node cur = q.poll();/* 划重点：这里判断是否到达终点 */if (cur is target)return step;/* 将 cur 的相邻节点加入队列 */for (Node x : cur.adj())if (x not in visited) {q.offer(x);visited.add(x);}}/* 划重点：更新步数在这里 */step++;}
}
注意防止重复计算 如果是矩阵中可以根据题意把[][]置0 啥的
常考题会用BFS返回值 所以里面是双层LIST 内层的LIST通常直接加入poll出来的值
List<List<Integer>> res=new ArrayList();
Queue<> queue=new LinkedList<>();
Set<> set=new HashSet<>();
结点入队
queue.offer(root); set.add(root);
while(queue 不空)
{
int size=queue.size();
List list=new ArrayList();
for( i 0->size) 一层
{cur=queue.poll();弹出list.add(cur.val);level x->x+1 从当前poll的这一层想办法找到下一层树 图 下一层很好找 左右孩子 邻接点就行但抽象问题 要好好思考怎么走到下一层 当前结点的什么状态是他的下一层if(！set.contains (x+1) && x+1 !=null) {queue.offer(x+1)}
}
res.add(list);
step++; 当求最短路径 或者 最少的尝试次数等等 一定返回step仔细想一下 每一层的遍历setp才+1 我们求最短的时候可不是直接用程序就找到了最短的情况而是遍历了一整层，等遇到那一层是target的时候 就知道我怎么走能在这层遇到target 然后返回这个层数 好像是从start一路找到了target是的 其实是遍历了好多层每一层肯定会有一个最优秀的解 就好比有10层楼 1层楼有8间教室 目标在5层的3教室我前4层的教室都遍历了 到第五层的时候我也遍历了3个教室但是step只记录层数 我们也不知道每一层的最优解是谁但是就假装告诉别人自己是从101 201 301 401 503这样就是最短路径啦 所以step记录最短路径 就是他只是记录层数，既然到了target每一层肯定有最优解 ！！！我们无需直到最优解到底是谁 ！！！但是默认经过这一层step+1
}
以上就是这个模板
一般难点就在于找到target 以及 找到邻接点的表现
图的BFS 需要用set避免重复计入 树就不会重复记录
深拷贝就是new List(list1);
虽然和list1的内容一致 但是不是指向同一个对象 list1后续的API操作不影响这个list
岛屿数目
这题的难点在于 你能联想到用BFS
start应该是第一个1的
邻接点应该是上下左右
class Point//用于方便形容ch 对象
{int x;int y;public Point(int x,int y){this.x=x;this.y=y;}}
class Solution {public int numIslands(char[][] grid) {//鲁棒防御if(grid==null||grid.length<=0||grid[0].length<=0)return 0;int m=grid.length; int n=grid[0].length;int numsOfIsland=0;//find startfor(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]=='1')//start!!!!!{bfs(grid,i,j); //transfer start to bfs numsOfIsland++;//退出bfs的时候一定队列为空了 就是周围都是水}}}return numsOfIsland;}//public void bfs(char [][]grid,int x,int y){int []diX={0,0,-1,1};int []diY={1,-1,0,0};Queue<Point> queue=new LinkedList<>();Point root=new Point(x,y);grid[x][y]='0';queue.offer(root);while(!queue.isEmpty()){int size=queue.size();for(int j=0;j<size;j++){Point cur=queue.poll();//需要判断下是在层里poll还是层外poll for(int i=0;i<4;i++){int adjX=cur.x+diX[i];int adjY=cur.y+diY[i];if(!isNoBoud(grid,adjX,adjY))continue; //越界了if(grid[adjX][adjY]=='1'){Point adj=new Point(adjX,adjY);grid[adjX][adjY]='0';queue.offer(adj);}}}}}public boolean isNoBoud(char [][]grid,int x,int y){int m=grid.length;int n=grid[0].length;return x>=0&&x<m&&y>=0&&y<n;}
}
解锁
邻接点的思考 是突破点
其余的没啥
// 将 s[j] 向上拨动一次
String plusOne(String s, int j) {char[] ch = s.toCharArray();if (ch[j] == '9')ch[j] = '0';elsech[j] += 1;return new String(ch);
}
// 将 s[i] 向下拨动一次
String minusOne(String s, int j) {char[] ch = s.toCharArray();if (ch[j] == '0')ch[j] = '9';elsech[j] -= 1;return new String(ch);
}
int openLock(String[] deadends, String target) {// 记录需要跳过的死亡密码Set<String> deads = new HashSet<>();for (String s : deadends) deads.add(s);// 记录已经穷举过的密码，防止走回头路Set<String> visited = new HashSet<>();Queue<String> q = new LinkedList<>();// 从起点开始启动广度优先搜索int step = 0;q.offer("0000");visited.add("0000");while (!q.isEmpty()) {int sz = q.size();/* 将当前队列中的所有节点向周围扩散 */for (int i = 0; i < sz; i++) {String cur = q.poll();/* 判断是否到达终点 */if (deads.contains(cur))continue;if (cur.equals(target))return step;/* 将一个节点的未遍历相邻节点加入队列 */for (int j = 0; j < 4; j++) {String up = plusOne(cur, j);if (!visited.contains(up)) {q.offer(up);visited.add(up);}String down = minusOne(cur, j);if (!visited.contains(down)) {q.offer(down);visited.add(down);}}}/* 在这里增加步数 */step++;}// 如果穷举完都没找到目标密码，那就是找不到了return -1;
}
多源BFS
腐烂的橘子
刚才的都是queue.offer(root)只有一个入口 找root的邻接点
但是如果是多个入口并发 就提前找到所有入口加入到队列中
以所有入口为出发点 找邻接点加入
橘子有永远不腐烂的时候 全局变量cont
更多推荐
BFS模板
发布评论