|
文章目录
广度优先搜索深度优先搜索拓扑排序并查集(Disjoint-set)Dijkstra算法求单源最短路径Bellman-Ford求单源最短路径Floyd求全图最短路径Kruskal算法求最小生成树Prim算法求最小生成树总结应用
广度优先搜索
广度优先搜索可以用来求解无权图的最短路径问题。广度优先搜索每遍历到下一层则路径长度加一，遍历到终点时的路径长度即是问题的解。 二进制矩阵中的最短路径 广度优先搜索如果需要按层次执行某些操作（比如查找最大的层、无权图的单源最短路径等问题），需要使用两层循环，外层循环判空，内层循环对当前层进行操作。下面的题目中bfs就是单源最短路径的模板题。
class Solution {
int[][] grid;
int len;
public int shortestPathBinaryMatrix(int[][] grid) {
len = grid.length;
if (grid[0][0] == 1 || grid[len-1][len-1] == 1) return -1;
this.grid = grid;
return bfs();
}
public int bfs() {
Queue queue = new ArrayDeque();
queue.add(new int[]{0,0});
grid[0][0] = 1;
int[] disx = new int[]{-1, -1, -1, 0, 0, 1, 1, 1};
int[] disy = new int[]{-1, 0, 1, -1, 1, -1, 0, 1};
int ans = 1;
while (!queue.isEmpty()) {
int size = queue.size();
while (--size >= 0) {
int x = queue.peek()[0];
int y = queue.poll()[1];
if (x == len-1 && y == len-1) return ans;
for (int i = 0; i = len || nextx = len || nexty |