本文共 3343 字,大约阅读时间需要 11 分钟。
广度优先搜索算法(Breadth First Search),又称为"宽度优先搜索"或"横向优先搜索",简称BFS。
它的思想是:从图中某顶点v出发,在访问了v之后依次访问v的各个未曾访问过的邻接点,然后分别从这些邻接点出发依次访问它们的邻接点,并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问,直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问,则需要另选一个未曾被访问过的顶点作为新的起始点,重复上述过程,直至图中所有顶点都被访问到为止。需要注意,遍历过的节点不能再次被遍历。
BFS可用于解决2类问题:
从A出发是否存在到达B的路径;
从A出发到达B的最短路径(这个应该叫最少步骤合理,第一次遍历到目的节点,其所经过的路径为最短路径);注意,使用 BFS 只能求解无权图的最短路径。使用队列来存储每一轮遍历得到的节点,对于遍历过的节点,应该将它标记,防止重复遍历。
计算在网格中从原点到特定点的最短路径长度
[[1,1,0,1],
[1,0,1,0], [1,1,1,1], [1,0,1,1]]private static class Position { int r, c, length; public Position(int r, int c, int length) { this.r = r; this.c = c; this.length = length; }}public static int minPathLength(int[][] grids, int tr, int tc) { int[][] next = { { 1, 0}, { -1, 0}, { 0, 1}, { 0, -1}}; int m = grids.length, n = grids[0].length; Queuequeue = new LinkedList<>(); queue.add(new Position(0, 0, 1)); while (!queue.isEmpty()) { Position pos = queue.poll(); for (int i = 0; i < 4; i++) { //4是数组next的长度 Position nextPos = new Position(pos.r + next[i][0], pos.c + next[i][1], pos.length + 1); if (nextPos.r < 0 || nextPos.r >= m || nextPos.c < 0 || nextPos.c >= n) continue; if (grids[nextPos.r][nextPos.c] != 1) continue; grids[nextPos.r][nextPos.c] = 0; if (nextPos.r == tr && nextPos.c == tc) return nextPos.length; queue.add(nextPos); } } return -1; }
给定一个正整数n,求和为n的最小全平方数(例如,1,4,9,16,…)。
Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4.Input: n = 13
Output: 2 Explanation: 13 = 4 + 9.class Solution { public int numSquares(int n) { Listsquares = getSquares(n);//获取所有平方数,存在链表中 Queue queue = new LinkedList<>(); boolean[] marked = new boolean[n + 1];//这里是n+1,比较好计算 queue.add(n); marked[n] = true; int level = 0;//level为第几层 while(!queue.isEmpty()){ int size = queue.size(); level++; while(size-- > 0){ int top = queue.poll(); for(int s : squares){ if (top - s==0){ return level; } if (top - s < 0){ break; } if (marked[top - s]){ continue; } marked[top - s] =true;//标记为true的不再遍历 queue.add(top - s); } } } return n; } //先定义一个求小于n的所有平方数的方法 private List getSquares(int n){ List list = new ArrayList<>(); int square = 1; int i = 3; while (square <= n){ list.add(square); square += i; i += 2; } return list; }}
转载地址:http://jerwi.baihongyu.com/