力扣HOT 100（图）
图论
797. 所有可能的路径
为什么path先把索引加上，图这个数据结构的索引，包含了数据信息，所以索引到数据表再到索引这个过程。一般回溯索引没有涉及问题中的含义。
class Solution {List<Integer> path=new ArrayList<>();//DequeList<List<Integer>> result=new ArrayList<>();private void backTrack(int[][] graph,int i, int n){if(i==n){//以后都别直接add一个引用。多维数组时result.add(new ArrayList<>(path));return;}for(int j:graph[i]){path.add(j);backTrack(graph,j,n);//remove()参数是索引path.remove(path.size()-1);}}public List<List<Integer>> allPathsSourceTarget(int[][] graph) {path.add(0);backTrack(graph,0,graph.length-1);return result;}
}用deque，只能赋值LinkedList
class Solution {Deque<Integer> path=new LinkedList<>();//DequeList<List<Integer>> result=new ArrayList<>();private void backTrack(int[][] graph,int i, int n){if(i==n){//以后都别直接add一个引用。多维数组时result.add(new ArrayList<>(path));return;}for(int j:graph[i]){//队列path.addLast(j);backTrack(graph,j,n);path.pollLast();}}public List<List<Integer>> allPathsSourceTarget(int[][] graph) {path.add(0);backTrack(graph,0,graph.length-1);return new ArrayList<>(result);}
}98. 所有可达路径
邻接矩阵：
import java.util.*;class Main{//图数据结构static Deque<Integer> path=new LinkedList<>();static List<List<Integer>> result=new ArrayList<>();private static void backTrack(int[][] graph,int i,int n){if(i==n){result.add(new ArrayList<>(path));return;}for(int j=1;j<=n;j++){if(graph[i][j]==1){path.add(j);backTrack(graph,j,n);path.removeLast();}}}public static void main(String[] args){Scanner scan=new Scanner(System.in);int n=scan.nextInt();int[][] graph=new int[n+1][n+1];int m=scan.nextInt();for(int i=0;i<m;i++){int a=scan.nextInt();int b=scan.nextInt();graph[a][b]=1;}path.addFirst(1);backTrack(graph,1,n);if (result.size() == 0) {System.out.println(-1);} else{for(List<Integer> list:result){for(int i=0;i<list.size();i++){System.out.print(list.get(i));if(i<list.size()-1){System.out.print(" ");}}System.out.print("\n");}}scan.close();}
}邻接表，因为数组里面不是基本类型，所以需要初始化一下。
对于多维数组（如int[][]），如果数组是基本类型，则Java会自动处理内层数组的初始化；如果数组是非基本类型，则内层数组也需要显式初始化。两次new两次箭头，
new int[][]一次把两个箭头生成。
由列表组成的数组（固定数量决定用这个）。所以是下面的类型。
import java.util.*;class Main{//图数据结构static Deque<Integer> path=new LinkedList<>();static List<List<Integer>> result=new ArrayList<>();private static void backTrack(List<Integer>[] graph,int i,int n){if(i==n){result.add(new ArrayList<>(path));return;}for(int j:graph[i]){path.add(j);backTrack(graph,j,n);path.removeLast();}}public static void main(String[] args){Scanner scan=new Scanner(System.in);int n=scan.nextInt();//n+1个ArrayList数组，new那里没有<>//List[] graph=new List[n+1];也可以List<Integer>[] graph=new ArrayList[n+1];//固定行，用数组int m=scan.nextInt();for(int i=0;i<=n;++i){//二维必须包含最内层的newgraph[i]=new ArrayList<>();}for(int i=0;i<m;i++){int a=scan.nextInt();int b=scan.nextInt();graph[a].add(b);}path.addFirst(1);backTrack(graph,1,n);if (result.isEmpty()) {System.out.println(-1);}else{for(List<Integer> list:result){for(int i=0;i<list.size();i++){System.out.print(list.get(i));if(i<list.size()-1){System.out.print(" ");}}System.out.print("\n");}}scan.close();}
}99.岛屿数量
就是求连通图的数量。
看成m个节点和n个节点相连的图。
import java.util.*;class Main{static int[][] direct={{1,0},{0,1},{0,-1},{-1,0}};static int n,m;private static void backTrack(int[][] graph,boolean[][] visited,int x,int y){for(int[] d:direct){int curX=x+d[0],curY=y+d[1];if(curX<0 || curX>=n ||curY<0 ||curY>=m)continue;if(!visited[curX][curY]&&graph[curX][curY]==1){visited[curX][curY]=true;backTrack(graph,visited,curX,curY);}}}public static void main(String[] args){Scanner scan=new Scanner(System.in);n=scan.nextInt();m =scan.nextInt();int[][] graph=new int[n ][m];for(int i=0;i<n;++i){for(int j=0;j<m;++j){graph[i][j]=scan.nextInt();}}int count=0;boolean[][] visited=new boolean[n][m];for(int i=0;i<n;++i){for(int j=0;j<m;++j){if(visited[i][j]==false&&graph[i][j]==1){visited[i][j]=true;backTrack(graph,visited,i,j);count++;}}}scan.close();System.out.println(count);}
}
把在里面的条件放在前面剪枝也可以：
if (visited[x][y] || grid[x][y] == 0) return; // 终止条件：访问过的节点 或者 遇到海水bfs和上面，只是改遍历每个 连通分量 的方式，那么还是主函数每个节点都要判断要不要bfs，要的话说明到达新大陆，count++（在主函数操作而不是bfs）
import java.util.*;class Main{//一个pair一个点static class pair{int first;int second;public pair(int first,int second){this.first=first;this.second=second;}}//对应层次的左右孩子。四个邻居/孩子static int[][] direct={{1,0},{0,1},{0,-1},{-1,0}};static Deque<pair> queue=new LinkedList<>();//显式的队列，dfs隐式的栈static int n,m,count;private static void bfs(int[][] graph,boolean[][] visited,int x,int y){queue.addLast(new pair(x,y));// visited[x][y]=true;不必要，main里面已经有了while(!queue.isEmpty()){pair p = queue.pollFirst();int prex=p.first;int prey=p.second;for(int[] d:direct){int curX=prex+d[0],curY=prey+d[1];if(curX<0 || curX>=n ||curY<0 ||curY>=m)continue;if(!visited[curX][curY]&&graph[curX][curY]==1){visited[curX][curY]=true;queue.addLast(new pair(curX,curY));//queue里面放已经访问的}}}}public static void main(String[] args){Scanner scan=new Scanner(System.in);n=scan.nextInt();m =scan.nextInt();int[][] graph=new int[n ][m];for(int i=0;i<n;++i){for(int j=0;j<m;++j){graph[i][j]=scan.nextInt();}}boolean[][] visited=new boolean[n][m];queue.addLast(new pair(0,0));for(int i=0;i<n;++i){for(int j=0;j<m;++j){if(visited[i][j]==false&&graph[i][j]==1){visited[i][j]=true;bfs(graph,visited,i,j);//从（i,j）开始遍历。遍历完联通子图，下一次从新的连通子图开始count++;}}}scan.close();System.out.println(count);}
}
dfs还有话说：
先污染后治理：
private void dfs(int x, int y) {if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y]=='0' || visited[x][y]) return;visited[x][y] = true;for (int[] d : directs) {int nextX = x + d[0];int nextY = y + d[1];dfs(nextX, nextY); //先污染后治理}}下面这样也行但是时间长点：
private void dfs(int x, int y) {visited[x][y] = true;for (int[] d : directs) {int nextX = x + d[0];int nextY = y + d[1];if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= m || grid[nextX][nextY]=='0'||visited[nextX][nextY] ) continue;dfs(nextX, nextY); //先污染后治理}}不用visited，bfs超时，dfs可以
class Pair {int first, second;public Pair(int x, int y) {this.first = x;this.second = y;}
}
// 在一些题解中，可能会把「已遍历过的陆地格子」标记为和海洋格子一样的 0，美其名曰「陆地沉没方法」，即遍历完一个陆地格子就让陆地「沉没」为海洋。这种方法看似很巧妙，但实际上有很大隐患，因为这样我们就无法区分「海洋格子」和「已遍历过的陆地格子」了。如果题目更复杂一点，这很容易出 bug。class Solution {int n, m;//网格结构的 DFS 与二叉树的 DFS 最大的不同之处在于，遍历中可能遇到遍历过的结点。int[][] directs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};char[][] grid;private void bfs(int x, int y) {Deque<Pair> q = new LinkedList<>();q.push(new Pair(x, y));grid[x][y]='2';while (!q.isEmpty()) {Pair curr = q.poll();int currX = curr.first;int currY = curr.second;for (int[] d : directs) {int nextX = currX + d[0];int nextY = currY + d[1];//超时if ( nextX < 0 || nextX >= n || nextY < 0 || nextY >= m ||grid[nextX][nextY]!='1') {continue;}q.push(new Pair(nextX, nextY));}}}private void dfs(int x, int y) {grid[x][y]='2';for (int[] d : directs) {int nextX = x + d[0];int nextY = y + d[1];//可过if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= m || grid[nextX][nextY]!='1') continue;dfs(nextX, nextY); }}public int numIslands(char[][] grid) {this.grid=grid;n = grid.length;m = grid[0].length;int count=0;for(int i=0;i<n;++i){for(int j=0;j<m;++j){//没访问的陆地if(grid[i][j]=='1' ){bfs(i,j);count++;}}}return count ;}
}看看注释：
class Pair {int first, second;public Pair(int x, int y) {this.first = x;this.second = y;}
}
// 在一些题解中，可能会把「已遍历过的陆地格子」标记为和海洋格子一样的 0，美其名曰「陆地沉没方法」，即遍历完一个陆地格子就让陆地「沉没」为海洋。这种方法看似很巧妙，但实际上有很大隐患，因为这样我们就无法区分「海洋格子」和「已遍历过的陆地格子」了。如果题目更复杂一点，这很容易出 bug。class Solution {int n, m;//网格结构的 DFS 与二叉树的 DFS 最大的不同之处在于，遍历中可能遇到遍历过的结点。boolean[][] visited;int[][] directs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};char[][] grid;private void bfs(int x, int y) {Deque<Pair> q = new LinkedList<>();q.push(new Pair(x, y));visited[x][y] = true;while (!q.isEmpty()) {Pair curr = q.poll();int currX = curr.first;int currY = curr.second;for (int[] d : directs) {int nextX = currX + d[0];int nextY = currY + d[1];if ( nextX < 0 || nextX >= n || nextY < 0 || nextY >= m ||grid[nextX][nextY]=='0'|| visited[nextX][nextY]) {continue;}q.push(new Pair(nextX, nextY));visited[nextX][nextY] = true;}}}private void dfs(int x, int y) {visited[x][y] = true;for (int[] d : directs) {int nextX = x + d[0];int nextY = y + d[1];if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= m || grid[nextX][nextY]=='0'||visited[nextX][nextY] ) continue;dfs(nextX, nextY); }}public int numIslands(char[][] grid) {this.grid=grid;n = grid.length;m = grid[0].length;int count=0;visited = new boolean[n][m];for(int i=0;i<n;++i){for(int j=0;j<m;++j){//陆地海洋、访问数组：成对出现在判断条件if(grid[i][j]=='1' &&!visited[i][j]){dfs(i,j);count++;}}}return count ;}
}100. 岛屿的最大面积
这个有点奇怪的案例：
import java.util.*;public class Main{static int maxArea,curArea;static int n,m;static boolean[][] visited;static int[][] direct = {{1,0},{0,1},{-1,0},{0,-1}};private static void bfs(int[][] graph,int x,int y){for(int[] d:direct){int curx=x+d[0],cury=y+d[1];if(curx<0 ||curx>=n ||cury<0||cury>=m)continue;if(graph[curx][cury]==1 && !visited[curx][cury]){curArea++;visited[curx][cury]=true;//递归之前先把当前节点处理了bfs(graph,curx,cury);}}}public static void main(String[] args){Scanner scan=new Scanner(System.in);n=scan.nextInt();m=scan.nextInt();int[][] graph=new int[n][m];for(int i=0;i<n;++i){for(int j=0;j<m;++j){graph[i][j]=scan.nextInt();} }visited = new boolean[n][m];for(int i=0;i<n;++i){for(int j=0;j<m;++j){if(graph[i][j]==1 && !visited[i][j]){curArea=1;visited[i][j]=true;//调用之前先把当前节点处理了bfs(graph,i,j);maxArea=Math.max(curArea,maxArea);}} }System.out.println(maxArea);}
}101. 孤岛的总面积
想用标志位代表不是孤岛就不统计了，但是出错：GPT也没有改对。
import java.util.*;public class Main {static boolean[][] visited;static int totalArea, curArea;static int n, m, yes;static int[][] direct = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};public static void bfs(int[][] graph, int i, int j) {// 如果触及边界，设置标志为不是孤岛if (i == 0 || j == 0 || i == n - 1 || j == m - 1) {yes = 1;return;}// 遍历4个方向for (int[] d : direct) {int x = i + d[0], y = j + d[1];// 检查是否越界if (x < 0 || x >= n || y < 0 || y >= m) continue;// 如果是陆地且未访问过if (graph[x][y] == 1 && !visited[x][y]) {visited[x][y] = true;curArea++;bfs(graph, x, y); // 继续递归遍历}}}public static void main(String[] args) {Scanner scan = new Scanner(System.in);n = scan.nextInt();m = scan.nextInt();int[][] graph = new int[n][m];visited = new boolean[n][m];// 输入矩阵for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {graph[i][j] = scan.nextInt();}}// 遍历所有单元格for (int x = 0; x < n; ++x) {for (int y = 0; y < m; ++y) {// 如果是陆地且未访问过if (graph[x][y] == 1 && !visited[x][y]) {visited[x][y] = true;curArea = 1;yes = 0;bfs(graph, x, y);// 如果yes没有被设置为1，说明这是一个孤岛if (yes == 0) {totalArea += curArea;}}}}System.out.println(totalArea);}
}还是用dmsxl的 方法，非孤岛全部变0了在统计。没用visited，访问了的都是0 了，count不是单独++，最后一个循环访问孤岛之前重置0.
卡玛 102.沉没孤岛
非孤岛先全部变2，不能变0不然不和海水一样了吗。
非孤岛和孤岛就区分出来了，然后二重循环改一下。
卡玛103.水流问题
简单想法，想每个节点都用一次深搜，时间复杂度到了四次方。
怎么优化呢
反过来就好啦，m x n个节点到2m+2n个节点，起点变成数量少的那批，复杂度降为三次方。这是不用visited数组的情况。
如果用visited，每个节点只会visited一次，总共只会用到一个二次方，so复杂度降到二次方。
我这样写，递归结束不了，溢出：
import java.util.*;class Main {class pair {int first, second;public pair(int first, int second) {this.first = first;this.second = second;}}static int count;static int[][] direct = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};static List<int[]> result = new ArrayList<>();static int m, n,prex,prey;static boolean[][] visited;//需要visited,resut不能重复加public static void dfs(int[][] graph, int i, int j) {if (graph[prex][prey] > graph[i][j]) return;for (int[] d : direct) {int x = i + d[0], y = j + d[1];if (x < 0 || x >= n || y < 0 || y >= m) continue;if (graph[x][y] < graph[i][j]) contnue://反方向停下，需要一直变大if(!visited[x][y]){result.add(new int[]{x, y});visited[x][y] = true;}prex=x;prey=y;dfs(graph, x, y);}}public static void main(String[] args) {Scanner scan = new Scanner(System.in);n = scan.nextInt();m = scan.nextInt();visited = new boolean[n][m];int[][] graph = new int[n][m];for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {graph[i][j] = scan.nextInt();}}for (int i = 0; i < n; ++i) {dfs(graph, i, 0);dfs(graph, i, m - 1);}for (int j = 0; j < m; ++j) {dfs(graph, 0, j);dfs(graph, n - 1, j);}System.out.println(result.isEmpty());for(int[] r:result){System.out.println(r[0]+" "+r[1]);}}
}题目都没看清楚，是：可以达到第一组边界和第二组边界的。
所以2个boolean标记数组，输出要求两个同时可以到达才加入数组。还有点细节
但是递归出口还是不很清楚
import java.util.*;class Main {static int[][] direct = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};static List<int[]> result = new ArrayList<>();static int m, n;static boolean[][] canReachOne;static boolean[][] canReachSecond;private static void bfs(int[][] graph,int i,int j,boolean[][] canReach){//能到边界canReach[i][j]=true;for(int[] d:direct){int x=i+d[0],y=j+d[1];if (x < 0 || x >= n || y < 0 || y >= m) continue;if(canReach[x][y])continue;//递归出口if(graph[i][j] > graph[x][y])continue;//只能往高走bfs(graph,x,y,canReach);}}public static void main(String[] args){Scanner scan=new Scanner(System.in);n=scan.nextInt();m=scan.nextInt();int[][] graph=new int[n][m];for(int i=0;i<n;++i){for(int j=0;j<m;++j){graph[i][j]=scan.nextInt();}}canReachOne=new boolean[n][m];canReachSecond=new boolean[n][m];//分4个写当然也对for(int i=0;i<n;++i){bfs(graph,i,0,canReachOne);bfs(graph,i,m-1,canReachSecond);}for(int j=0;j<m;++j){bfs(graph,0,j,canReachOne);bfs(graph,n-1,j,canReachSecond);}for(int i=0;i<n;++i){for(int j=0;j<m;++j){if(canReachOne[i][j] && canReachSecond[i][j])System.out.println(i+" "+j);}}}
}
看规律前面都得有visited作为递归出口，这里canReach其实包含visited含义，所以同理。
104. 建造最大岛屿
一个岛屿一个标记，相同岛屿上的每一块 都用一样的标记，并且map存储岛屿标记对应的 面积，这样最后一个循环计算所有海水块万一变成岛屿，周围合并起来的岛屿加上自己的面积，统计最大值。
注意用什么标记的。curLoc其实可以从 1开始（有visited协助判断是否遍历过），但是从2 开始就可以不用visited判断了。
注意时间是n平方。
从2开始：
import java.util.*;public class Main {class pair {int first, second;public pair(int first, int second) {this.first = first;this.second = second;}}static int m,n;static int count, curLoc = 2;static Deque<pair> queue = new LinkedList<>();static int[][] direct = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};static List<Integer[]> result = new ArrayList<>();static boolean[][] visited; // Need visited, result cannot duplicatepublic static void dfs(int[][] graph, int i, int j) {//每次调用dfs前是不是都判断了，那么调用一次就是一块陆地，放在前面合适// visited[i][j] = true;//岛屿不用count标记，不好搞，而且后面计算周围面积也是//用新的变量curLoc，独一的，计算周围面积可以判断有没有重复添加graph[i][j] = curLoc;count++;for (int[] d : direct) {int x = i + d[0], y = j + d[1];if (x < 0 || x >= n || y < 0 || y >= m) continue;if (graph[x][y] ==1 ) {//&& !visited[x][y]dfs(graph, x, y);}}}public static void main(String[] args) {Scanner scan = new Scanner(System.in);n = scan.nextInt();m = scan.nextInt();int[][] graph = new int[n][m];// visited = new boolean[n][m];for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {graph[i][j] = scan.nextInt();}}int maxCount = 1;Map<Integer, Integer> hash = new HashMap<>();for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (graph[i][j] == 1 ) {count = 0;dfs(graph, i, j);hash.put(curLoc, count);curLoc++;//maxCount初始是岛屿面积最大值maxCount=Math.max( maxCount,count);}}}for(int i=0;i<n;++i){for(int j=0;j<m;++j){// System.out.print(graph[i][j]+" ");if(graph[i][j]==0 ){int zhouwei=0;Set<Integer> set = new HashSet<>();for(int[] d :direct){int x = i + d[0], y = j + d[1];if (x < 0 || x >= n || y < 0 || y >= m) continue;int bianhao=graph[x][y];if(!set.contains(bianhao)){zhouwei+=hash.getOrDefault(bianhao,0);set.add(bianhao);}} maxCount=Math.max( maxCount,zhouwei+1);}}}System.out.println(maxCount);}
}
从1开始：
import java.util.*;public class Main {class pair {int first, second;public pair(int first, int second) {this.first = first;this.second = second;}}static int m,n;static int count, curLoc = 1;static Deque<pair> queue = new LinkedList<>();static int[][] direct = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};static List<Integer[]> result = new ArrayList<>();static boolean[][] visited; // Need visited, result cannot duplicatepublic static void dfs(int[][] graph, int i, int j) {visited[i][j] = true;graph[i][j] = curLoc;count++;for (int[] d : direct) {int x = i + d[0], y = j + d[1];if (x < 0 || x >= n || y < 0 || y >= m) continue;if (graph[x][y] ==1 && !visited[x][y]) {dfs(graph, x, y);}}}public static void main(String[] args) {Scanner scan = new Scanner(System.in);n = scan.nextInt();m = scan.nextInt();int[][] graph = new int[n][m];visited = new boolean[n][m];for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {graph[i][j] = scan.nextInt();}}int maxCount = 1;Map<Integer, Integer> hash = new HashMap<>();for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (graph[i][j] == 1 && !visited[i][j]) {count = 0;dfs(graph, i, j);hash.put(curLoc, count);curLoc++;maxCount=Math.max( maxCount,count);}}}for(int i=0;i<n;++i){for(int j=0;j<m;++j){// System.out.print(graph[i][j]+" ");if(graph[i][j]==0 ){int zhouwei=0;Set<Integer> set = new HashSet<>();for(int[] d :direct){int x = i + d[0], y = j + d[1];if (x < 0 || x >= n || y < 0 || y >= m) continue;int bianhao=graph[x][y];if(!set.contains(bianhao)){zhouwei+=hash.getOrDefault(bianhao,0);set.add(bianhao);}} maxCount=Math.max( maxCount,zhouwei+1);}}}System.out.println(maxCount);}
}注意把visited放在递归函数一开始，liao pi些
110. 字符串接龙
自己写的，先生成了graph数组，再遍历，结果是遍历了A到B每一圈的节点都统计，就是二叉树要求路径长结果你求节点数。
import java.util.*;class Main
{static Deque<Integer> queue = new LinkedList<>();static int count=0;static boolean[] visited;static String[] strs;public static int bfs(int[][] graph, int start, int end) {queue.addLast(start);visited[start] = true;int step = 1; // 记录步数while (!queue.isEmpty()) {int size = queue.size();for (int i = 0; i < size; i++) {int cur = queue.pollFirst();if (cur == end) return step; // 找到 endStr，返回步数for (int j = 0; j < strs.length; ++j) {if (graph[cur][j] == 0) continue;if (visited[j]) continue;queue.addLast(j);visited[j] = true;}}step++; // 每一层加1步}return 0; // 未找到路径，返回0}private static boolean isDiffOne(int a, int b) {int diffCount = 0;String s1 = strs[a], s2 = strs[b];if (s1.length() != s2.length()) return false;for (int i = 0; i < s1.length(); i++) {if (s1.charAt(i) != s2.charAt(i)) diffCount++;}return (diffCount == 1);}public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt() + 2;int[][] graph = new int[n][n];strs = new String[n];for (int i = 0; i < n; i++) {strs[i] = new String(scan.next());}for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (isDiffOne(i, j)) graph[i][j] = 1;// System.out.print(graph[i][j]);}// System.out.println();}visited = new boolean[n];System.out.println(bfs(graph, 0,1));}
}之后搞清楚求节点数，还是求层数。本来层序遍历那里应该练的很熟练的了。
还有区分递归 和迭代，不要迭代写一个递归出口在前面，或者循环里面写一个递归调用。
时间复杂度n2
小总结：递归or 迭代？海水陆地（周围节点上下左右direct数组）or行列代表节点一样（对称矩阵还是邻接表，遍历每个节点的邻接点）？每圈节点数量or路径长度？要不要visited数组？visited的赋值在哪里，统计or result最后的确定写哪里
13.有向图的完全可达性
把条件写在递归函数开头是处理当前节点，写在循环里面是处理下一个节点。。写在开头，对所有节点都有效，写在循环……
到现在一般递归函数参数要有 : graph邻接矩阵或者邻接表，visited数组，当前的节点i。这些以及其他可以放类属性也可以参数。
这道题也没有什么别的，就从已知的起点开始BFS或者DFS，如果一轮下来，还有节点没访问到就是+1。
邻接矩阵，邻接表
X
BFS，DFS
组合4种都要会写。
注意题目节点从1开始，加入的时候存入的时候-1，就统一了，visited数组。
import java.util.*;public class Main {public static void dfs(List<Integer>[] graph, int i, boolean[] visited) {if(visited[i]) return;visited[i] = true;for(int j : graph[i]) {dfs(graph, j, visited);}}public static void bfs(List<Integer>[] graph, int i, boolean[] visited) {Deque<Integer> q = new LinkedList<>();q.add(i);while(!q.isEmpty()) {int j = q.pollFirst();visited[j] = true;for(int k : graph[j]) {if(visited[k]) continue;q.addLast(k);}}}public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();int m = scan.nextInt();List<Integer>[] graph = new ArrayList[n];for(int i = 0; i < n; ++i) {graph[i] = new ArrayList<>();}for(int i = 0; i < m; ++i) {int start = scan.nextInt();int end = scan.nextInt();graph[start - 1].add(end - 1);}boolean[] visited = new boolean[n];// dfs(graph, 0, visited);bfs(graph, 0, visited);for(boolean v : visited) {if(!v) {System.out.println(-1);return;}}System.out.println(1);}
}
106. 岛屿的周长
不要陷入惯性思维，这个题目幽你一默。
用BFS，DFS?可以但没必要
没有算法分类，直接就是根据规律挨个统计而已。
方法一注意除了海水，还要看四条边界也是周长一部分。
方法二找到陆地之后，你不用循环k=4这样。规律是陆地✖️4 减去 所有重叠挨在一起的边。这个重叠的边可以只算一半，一个直角那样的，就行。比如左上，因为重叠的一对边一定有一边是一个左或者上。
import java.util.*;public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();int m = scan.nextInt();int[][] graph=new int[n][m];for(int i = 0; i < n; ++i) {for(int j = 0; j < m; ++j) {graph[i][j] = scan.nextInt();}}int count=0;//陆地数int overlapBian=0;for(int i = 0; i < n; ++i) {for(int j = 0; j < m; ++j) {if(graph[i][j] ==1){count++;if(i>0 && graph[i-1][j]==1)overlapBian++;if(j>0 && graph[i][j-1]==1)overlapBian++;}}}System.out.println(count * 4 - overlapBian*2);}
}
并查集理论
也就是说，无论使用并查集模板里哪一个函数（除了init函数），都会有路径压缩的过程。
路径压缩是为了一个集合里面只有两层，一个根节点，下面一排。
路径压缩后的并查集时间复杂度在O(logn)与O(1)之间，且随着查询或者合并操作的增加，时间复杂度会越来越趋于O(1)。
最后不能直接判断father[s]＝d来看，在同一条路径下面而不是确定d是根，所以只能isSame才可以。
其实代码好写，重要是理解什么时候用这个：2个节点是不是同一个根；2个集合合并。
import java.util.*;public class Main {static int[] father;private static void init() {for (int i = 0; i < father.length; ++i) {father[i] = i;}}private static int find(int x) {return x == father[x] ? x : (father[x] = find(father[x]));}private static boolean isSame(int u, int v) {u = find(u);v = find(v);return u == v;}private static void join(int u, int v) {u = find(u);v = find(v);if (u == v) return;father[u] = v;}public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();int m = scan.nextInt();father = new int[n];init();for (int i = 0; i < m; ++i) {int a = scan.nextInt()-1;int b = scan.nextInt()-1;join(a, b);}int s = scan.nextInt()-1;int d = scan.nextInt()-1;if (isSame(s, d)) {System.out.println(1);} else {System.out.println(0);}}
}108. 冗余连接
偏移的问题；
为什么一找到一个根相同的就对，因为答案就一个，只会有一次跟相同，那你re不return都一样答案。
import java.util.*;public class Main {static int[] father;private static void init(){for(int i=0;i<father.length;++i){father[i]=i;}} private static int find(int x) {return x== father[x]?x:(father[x] = find(father[x]));}private static boolean isSame(int u, int v ){u=find(u);v=find(v);return u==v;}private static void join(int u ,int v){u=find(u);v=find(v);if(u==v){return;}father[u]=v; }public static void main(String[] args){Scanner scan = new Scanner (System.in);int n=scan.nextInt();//有偏移不用-1，father多增一个。because有的例子输入了0father = new int[n+1];init();for(int i=0 ;i<n; ++i){int a=scan.nextInt();int b=scan.nextInt();if(isSame(a,b)){System.out.println((a)+" "+(b));return ;}else{ join(a,b);}}}}109. 冗余连接II
一个环就是去掉方向看作无向图就有一个环。因为是n个点n条有向边。
直接看答案了，把三种情况都说了。
1加一条倒着的（不指向根）：（2度点两条入边只可能去一个）
2加一条倒着的（指向根）：（得遍历判断了：顺着找发现一条边两点同根就是答案）
3加一条顺着的：（2度点两条入边都可去）
也可以不线性哈，这里随便画的。去掉之后是有向树就是对的。
并查集体现在，判断某条边能不能join。
所以1、3一起看，如果没找到，接着判断2.
import java.util.*;class Main{static int[] father;static void init(){for(int i=0;i<father.length;++i){father[i]=i;}}static int find(int u){return u==father[u]?u:(father[u]=find(father[u]));}static boolean isSame(int u,int v){u=find(u);v=find(v);return u==v;}//u->vstatic boolean join(int u,int v){u=find(u);v=find(v);if(u==v)return false;father[v]=u;return true;}//找到某条边两端点同根static void canDeleteShu(int[][] graph){init();for(int i=0;i<graph.length;++i){int a=graph[i][0],b=graph[i][1];if(isSame(a,b)){System.out.println(a+" "+b);return;}join(a,b);}}//如果删了还有环return falsestatic boolean canDeleteHuan(int[][] graph,int index){init();for(int i=0;i<graph.length;++i){int a=graph[i][0],b=graph[i][1];if(index==i)continue;if(!join(a,b))return false;}return true;}public static void main(String[] args){Scanner scan=new Scanner(System.in);int n = scan.nextInt();father = new int[n+1] ;int[][] graph=new int[n][2];int[] du=new int[n+1];//存储入度for(int i=0;i<n;++i){graph[i][0]=scan.nextInt();graph[i][1]=scan.nextInt();du[graph[i][1]]++;}//有入度为2 情况//倒着判断，canDeleteHuan判断能不能删for(int i=n-1;i>=0;--i){if(du[graph[i][1]]==2){if(canDeleteHuan(graph,i)){System.out.println(graph[i][0]+" "+graph[i][1]);return;}//如果删了还有环，这条边不能删除，接着找后面那条else continue;}}//根参与环的情况canDeleteShu(graph);}
}两个函数就是用isSame()和join()判断有没有环，所以并查集判断有无环很方便。我是说不看方向的无向图，或者有向环不看箭头的环。
最小生成树
prim 53. 寻宝（第七期模拟笔试）
复习一下Prim，选择一个节点加入到生成树集合，每次计算u（生成树集合）到v（非生成树节点集合）的距离（更新minDist 数组），同样把最短距离的v中的点加入到u……
minDist 数组 就记录每个节点到生成树集合 的距离。
怎么判断 生成树节点 和 非生成树节点？bool数组
注意下面的主语
mniDist，定义记清楚，当某个点选中为生成树节点，mniDist那个值也就不变了，就是最后结果。
n次的：
注意双向边，graph[x][y]和graph[y][x]；
注意 每次更新只用关注所有点到cur。
注意 i=1 始终10001，统计只用关注i=1以后的。
再关注记录 这棵最小生成树的所有组成边，不用二维数组记录（parent一维），在更新mniDisc里面更新parent，因为最后的结果一定是最小的边，被选上了（true)就不会再更新了。最后所有节点都被选中，parent就是最终最小生成树的所有组成边。
graph也一定要初始化，没有边的默认最大值。
import java.util.*;public class Main{public static void main(String[] args){Scanner scan=new Scanner(System.in);int v=scan.nextInt();int e=scan.nextInt();int[] minDisc=new int[v+1];//节点有偏移Arrays.fill(minDisc, 10001);//一开始都是非生成树节点int[][] graph=new int[v+1][v+1];for(int i=0;i<=v;++i){Arrays.fill(graph[i], 10001);//一定要初始化}for(int i=0;i<e;++i){int x=scan.nextInt();int y=scan.nextInt();int val=scan.nextInt();//无向图，要对称graph[x][y]=val;graph[y][x]=val;}boolean[] isInTree=new boolean[v+1];int[] parent=new int[v+1];//顶点j对应的最小生成树边的另一个顶点parent[j]for(int i=1;i<=v;++i){int cur=1;int minDiscMin=10001;//minDisc里面最小的《非生成树节点》for(int j=1;j<=v;++j){if(minDisc[j]<minDiscMin && !isInTree[j]){minDiscMin=minDisc[j];cur=j;}}//得到cur，选中，更新isInTreeisInTree[cur]=true;//更新minDisc数组，只用更新与cur有关的for(int k=1;k<=v;++k){//重新统计 非生成树节点k 到 生成树节点的最短距离，仅仅与变动的cur比较，更新// 由于cur节点是新加入到最小生成树，那么只需要关心与 cur 相连的 非生成树节点 的距离 是否比 原来 非生成树节点到生成树节点的距离更小了呢if(graph[k][cur]<minDisc[k] && !isInTree[k]){minDisc[k]=graph[k][cur];//更新parent[k]=cur;}}}int count=0;for(int i=2;i<=v;++i){//i=1没有更新过，一开始就是生成树节点；统计其他的v-1条边即可count+=minDisc[i];}System.out.println(count);for(int i=2;i<=v;++i){System.out.println(i+" "+parent[i]);}}
}parent和mniDist都是在!isInTree[]条件下。
克鲁斯卡尔 53. 寻宝（第七期模拟笔试）
上一题想用 并查集，其实是这里能用到。
主要就是选V-1条边，条件是不能在同一个集合里面（！isSame()），就可以join()。
记录边的话，可以用之前的parent，注意每次选边的过程，按照并查集是v1->v2，所以v2是新选的每次都唯一，so只能v2作为下标。当然也可以直接一个集合挨个add v1和v2（Prim只能parent记录，因为循环结束才能知道结果）：Kruskal 算法 输出边的话，相对prim 要容易很多，因为 Kruskal 本来就是直接操作边，边的结构自然清晰，不用像 prim一样 需要再将节点连成线输出边 （因为prim是对节点操作，而 Kruskal是对边操作，这是本质区别）
import java.util.*;public class Main{static int[] father;static void init(){for(int i=0;i<father.length;++i){father[i]=i;}}static int find(int x){return x==father[x]?x:(father[x]= find(father[x]));}static boolean isSame(int u,int v){u=find(u);v=find(v);return u==v;}// u->vstatic void join(int u, int v){u=find(u);v=find(v);if(u==v)return;father[u]=v;}public static void main(String[] args){Scanner scan=new Scanner(System.in);int v=scan.nextInt();int e=scan.nextInt();List<int[]> graph=new ArrayList<>();for(int i=0;i<e;++i){int v1=scan.nextInt();int v2=scan.nextInt();int val=scan.nextInt();graph.add(new int[]{v1,v2,val});}//排序,lambda，2维数组的元素a->按照a的哪个元素ai比较排序，默认从小到大graph.sort(Comparator.comparingInt(arr -> arr[2]));int count=0,minDist=0;//选v-1条边father =new int[v+1];init();//记得初始化//parent记录选的边，father不行因为并查集压缩路径了int[] parent=new int[v+1];for(int[] g:graph){int v1=g[0],v2=g[1],val=g[2];if(isSame(v1,v2))continue;// System.out.println(v1+" "+v2);join(v1,v2);parent[v2]=v1;//hhh这个顺序有讲究//v2每一次都是新选的节点，所以不会被覆盖count++;minDist+=val;if(count==v-1)break;//选了v-1条就结束}for(int i=1;i<=v;++i){System.out.println(i+" "+parent[i]);}System.out.println(minDist);}
}比较这两个：
二刷忘记排序，复习的时候回想一下总体过程，带点脑子。
117. 软件构建
思路：1、选入度为0 的点；2、在图中删除这个点。
所以，要统计入度，删除之后，点指向的其他点的入度要改变，怎么找到其他点？直接一个下标->List ，List数组 来存上 每个点 指向的 其他点。
q是一定要的，步骤2 看q 来调整入度 和 加入点 到q。
import java.util.*;public class Main{public static void main(String[] args){Scanner scan=new Scanner(System.in);int n=scan.nextInt();int m=scan.nextInt();int[] inDegree=new int[n];List<Integer>[] outedge=new List[n];for(int i=0;i<n;i++){outedge[i]=new ArrayList<>();}//统计 入度、出边顶点for(int i=0;i<m;++i){int a=scan.nextInt();int b=scan.nextInt();inDegree[b]++;outedge[a].add(b);}//q是必须的，记录步骤1 直接 和 间接 删除的点，好在步2 调整相关点的入度Queue<Integer> q=new LinkedList<>();List<Integer> result=new ArrayList<>();//开始步骤1、2//一开始入度就是0的入队for(int i=0;i<n;++i){if(inDegree[i]==0)q.add(i);}//步骤2while(!q.isEmpty()){int a=q.poll();result.add(a);for(int j :outedge[a]){ //如果相关节点受影响之后（是前++）变成了无入度，又要加入到qif(--inDegree[j]==0){q.add(j);}}}// 还要判断环if(result.size()<n){System.out.println(-1);return;}for(int i=0;i<result.size();++i ){System.out.print(result.get(i));if(i<result.size()-1)System.out.print(" ");}}
}最短路径
迪杰斯特拉
dijkstra算法：在有权图（权值非负数）中求从起点到其他节点的最短路径算法。
为什么 和 Prim这么像，过程都是一个数组——mniDist的更新（n-1)轮：每轮确定一个点（距离最短的），然后更新此数组。最后确定完除了起点之外的 n-1个点：
import java.util.*;class Main{public static void main(String[] args){Scanner scan=new Scanner (System.in);int n=scan.nextInt();int m=scan.nextInt();int[][] graph=new int[n+1][n+1];for(int i=1;i<=n;++i)//又忘记初始化{Arrays.fill(graph[i],Integer.MAX_VALUE);}for(int i=0;i<m;++i){int v1=scan.nextInt();int v2=scan.nextInt();graph[v1][v2]=scan.nextInt();// graph[v2][v1]=scan.nextInt();}//源头到没选中节点的最短距离int[] minDist=new int[n+1];Arrays.fill(minDist,Integer.MAX_VALUE);minDist[1]=0;//得初始化：起点到自己距离是0boolean[] visited=new boolean[n+1];for(int j=1;j<n;++j){//不能是别的负数，最后一轮int cur=1;int minD=Integer.MAX_VALUE;for(int i=1;i<=n;++i){if(minDist[i] <minD&&!visited[i]){minD=minDist[i];cur=i;}}visited[cur]=true;for(int i=1;i<=n;++i){//要不然出现负数，有溢出if(minDist[cur]==Integer.MAX_VALUE || graph[cur][i]==Integer.MAX_VALUE)continue;if(minDist[cur]+graph[cur][i]<minDist[i]&&!visited[i]){minDist[i]=minDist[cur]+graph[cur][i];}}// for(int i=2;i<=n;++i){// System.out.print(minDist[i]+" ");// }// System.out.println();}if(minDist[n]==Integer.MAX_VALUE)System.out.println(-1);else System.out.println(minDist[n]);}
}这是与prim无异的朴素版算法，也是考研学的那种过程的思想。
注意graph、起点的初始化，mniDist里面某个点一旦被选，不再参与比较，也不再更新距离。
有个问题，上面总的for循环，应该是≤n轮，为什么<n轮也行。
47. 参加科学大会（第六期模拟笔试）
前提：稀疏图，所以尽量让 时复 跟节点没关系。
改进：
1、堆优化，就是空间换时间，因为mniDist数组找最小值时间有点长与n有关，所以用PriorityQueue存下mniDist下标-权值 对帮忙找最小值，PriorityQueue会把所有的边放一遍出一遍，那么就只跟边有关。是的就这个作用而已。
2、另外结合邻接表，能够让总的 时间复杂度 更低。如果还是用邻接矩阵的话，里面更新数组 的时间复 还是 和 n有关，不行。
这样，大循环是E，小循环1是logE，小循环2是决定了大循环，其实可以看做1。可以细想。
import java.util.*;class Main{public static void main(String[] args){class edge{int v2;int val;public edge(int b, int c) {v2 = b;val = c;}}class pair{int index;int val;public pair(int a, int b) {index = a;val = b;}}Scanner scan=new Scanner(System.in);int n=scan.nextInt();int m=scan.nextInt();int[] mniDist = new int[n+1];Arrays.fill(mniDist,Integer.MAX_VALUE);mniDist[1]=0;//辅助mniDist——意义相同，pair是下标-权值 对PriorityQueue<pair> priQueue=new PriorityQueue<>(new Comparator<pair>(){public int compare(pair e1,pair e2){return e1.val-e2.val;}});priQueue.add(new pair(1,0));//适合稀疏图的——邻接表来表示List<edge>[] graph=new List[n+1];for(int i=0;i<=n;i++){graph[i]=new ArrayList<>();}for(int i=0;i<m;++i){int a=scan.nextInt();int b=scan.nextInt();int c=scan.nextInt();graph[a].add(new edge(b,c));}boolean[] visited=new boolean[n+1];while(!priQueue.isEmpty()){pair cur=priQueue.poll();visited[cur.index]=true;//选中for(edge e:graph[cur.index]){int j=e.v2;if(!visited[j]&&cur.val + e.val<mniDist[j]){mniDist[j]=cur.val + e.val;priQueue.add(new pair(j,mniDist[j]));}}}if(mniDist[n]==Integer.MAX_VALUE)System.out.println(-1);else System.out.println(mniDist[n]);}
}- 时间复杂度：O(ElogE) E 为边的数量。堆找最小值 是logE。
- 空间复杂度：O(N + E) N 为节点的数量。堆是E，mniDist是N。
注意堆怎么实现的？邻接表的实现。
94. 城市间货物运输 I
在求单源最短路的方法中，使用dijkstra 的话，则要求图中边的权值都为正数。
import java.util.*;class Main{public static void main(String[] args){class edge{int s,t,v;public edge(int a,int b, int c){s=a;t=b;v=c;}}Scanner scan=new Scanner(System.in);int n=scan.nextInt();int m=scan.nextInt();int[] mniDist=new int[n+1];Arrays.fill(mniDist,Integer.MAX_VALUE);mniDist[1]=0;//还是单源的哈List<edge> Edges=new ArrayList<>();for(int i=0;i<m;++i){int a=scan.nextInt();int b=scan.nextInt();int c=scan.nextInt();Edges.add(new edge(a,b,c));}int[] copyMniDist=new int[n+1];//松弛n-1不是m-1次，没有环的for(int i=1;i<n;++i){copyMniDist = Arrays.copyOf(mniDist,mniDist.length);for(edge e:Edges){if(copyMniDist[e.s]==Integer.MAX_VALUE)continue;//最小运输成本mniDist[e.t]=Math.min(mniDist[e.t],copyMniDist[e.s]+e.v);}}// for(int i=1;i<=n;++i)// {// System.out.println(mniDist[i]);// }if(mniDist[n]==Integer.MAX_VALUE)System.out.println("unconnected");else System.out.println(mniDist[n]);}
}像简单的 动态规划。
时间复杂度： O(N * E)
没有负权回路，remember。
每i轮确定了和起点有i条边的点的最短距离。没有回路最多n-1条边，所以n-1轮。
注意和迪杰斯特拉 的区别。
代码随想录
大家可以发现 Bellman_ford 算法每次松弛 都是对所有边进行松弛。
但真正有效的松弛，是基于已经计算过的节点在做的松弛。
照着层次遍历 来做，不加别的，因为图圈圈又绕绕，队列里面会无限制的加入点噢！
所以得加入visited数组，就是队列里面已经有的，不用重复添加了，要不然溢出。进队true出队false。
下面的程序试过了，除了负权回路，全正回路也不行。
import java.util.*;class Main{public static void main(String[] args){class edge{int t,v;public edge(int b,int c){t=b;v=c;}}Scanner scan=new Scanner (System.in);int n=scan.nextInt();int m=scan.nextInt();//邻接表更高效List<edge>[] graph=new ArrayList[n+1];for(int i=0;i<=n;++i){graph[i] = new ArrayList<>();}for(int i=0;i<m;++i){int a=scan.nextInt();int b=scan.nextInt();int c=scan.nextInt();graph[a].add(new edge(b,c));}int[] mniDist=new int[n+1];Arrays.fill(mniDist,Integer.MAX_VALUE);mniDist[1]=0;boolean[] visited=new boolean[n+1];//只是用来保证不重复添加的Deque<Integer> alreadyDots=new LinkedList<>();alreadyDots.add(1);visited[1]=true;while(!alreadyDots.isEmpty()){int cur=alreadyDots.pollFirst();visited[cur]=false;//只有在队列的元素才是truefor(edge e:graph[cur]){//更新是一定要更新的，入不入对是不一定的mniDist[e.t]=Math.min(mniDist[cur]+e.v,mniDist[e.t]);if(visited[e.t]==false){alreadyDots.addLast(e.t);visited[e.t]=true;}}}// for(int i=1;i<n;++i){// for(edge e:graph){// if(mniDist[e.s]==Integer.MAX_VALUE)continue;// mniDist[e.t]=Math.min(mniDist[e.s]+e.v,mniDist[e.t]);// }// }// for(int i=1;i<n;++i){// System.out.println(mniDist[i]); // }if(mniDist[n]==Integer.MAX_VALUE)System.out.println("unconnected");else System.out.println(mniDist[n]);}
}发现问题所在，只有更新了mniDist的，才能进队列，没有更新的本来是目前最小值，没有变化也不会影响他连着的一堆点，所以不管
import java.util.*;class Main{public static void main(String[] args){class edge{int t,v;public edge(int b,int c){t=b;v=c;}}Scanner scan=new Scanner (System.in);int n=scan.nextInt();int m=scan.nextInt();//链表更高效List<edge>[] graph=new ArrayList[n+1];for(int i=0;i<=n;++i){graph[i] = new ArrayList<>();}for(int i=0;i<m;++i){int a=scan.nextInt();int b=scan.nextInt();int c=scan.nextInt();graph[a].add(new edge(b,c));}int[] mniDist=new int[n+1];Arrays.fill(mniDist,Integer.MAX_VALUE);mniDist[1]=0;boolean[] visited=new boolean[n+1];//只是用来保证不重复添加的//放更新了的点Deque<Integer> alreadyDots=new LinkedList<>();alreadyDots.add(1);// visited[1]=true;while(!alreadyDots.isEmpty()){int cur=alreadyDots.pollFirst();visited[cur]=false;//只有在队列的元素才是truefor(edge e:graph[cur]){//更新是一定要更新的，入不入对是不一定的//更新是入队的前提if(mniDist[e.t]>mniDist[cur]+e.v){mniDist[e.t]=mniDist[cur]+e.v;//不在队列但已经是最优，不会管，可以有全+回路if(visited[e.t]==false){alreadyDots.addLast(e.t);visited[e.t]=true;}}}}// for(int i=1;i<n;++i){// for(edge e:graph){// if(mniDist[e.s]==Integer.MAX_VALUE)continue;// mniDist[e.t]=Math.min(mniDist[e.s]+e.v,mniDist[e.t]);// }// }// for(int i=1;i<n;++i){// System.out.println(mniDist[i]); // }if(mniDist[n]==Integer.MAX_VALUE)System.out.println("unconnected");else System.out.println(mniDist[n]);}
}正确的算法以上。但是仍然是不适应有负权回路，因为全正，比如1-2,2-3,3-1，判断3-1,if条件肯定不满意，3到1 权值加上3的，定必1本身的大。但是负权回路，也就是图中出现环且环上的边总权值为负数 的话，会无线循环下去的。
越稠密图，时间越大，所以不一定总比bellman_ford优秀。总的是O(k*n)，完全图那种会退化到O(E*n).
95. 城市间货物运输 II
没有想的那么高深，
1、朴素版第n次mniDist还有更新，那代表会一直更新下去，circle。
2、优化版有某个节点入队n次以上，代表mniDist必更新了n次以上，circle。
import java.util.*;class Main{public static void main(String[] args){class edge{int t,v;public edge(int a,int b){t=a;v=b;}}Scanner scan=new Scanner(System.in);int n=scan.nextInt();int m=scan.nextInt();List<edge>[] graph=new List[n+1];for(int i=0;i<=n;++i){graph[i]=new ArrayList<>();}for(int i=0;i<m;++i){int a=scan.nextInt();int b=scan.nextInt();int c=scan.nextInt();graph[a].add(new edge(b,c));}int[] mniDist=new int[n+1];Arrays.fill(mniDist,Integer.MAX_VALUE);mniDist[1]=0;Deque<Integer> q=new LinkedList<>();q.add(1);boolean[] isInQueue=new boolean[n+1];isInQueue[1]=true;int count=0;int[] inCount=new int[n+1];Arrays.fill(inCount,0);inCount[1]=1;while(!q.isEmpty()){int cur=q.pollFirst();isInQueue[cur]=false;for(edge e:graph[cur]){if(mniDist[cur]+e.v<mniDist[e.t]){mniDist[e.t]=mniDist[cur]+e.v;if(isInQueue[e.t]==false){q.add(e.t);isInQueue[e.t]=true;inCount[e.t]++;if(inCount[e.t]>=n){System.out.println("circle");return;}}}}}if(mniDist[n]==Integer.MAX_VALUE)System.out.println("unconnected");else System.out.println(mniDist[n]);// System.out.println(count);}
}感觉会SPFA的就行了，bellman_ford的，是第N次条件还满足（即要更新mniDist数组）就是圈。
96. 城市间货物运输 III
可以发现 同样的图，边的顺序不一样，使用版本一的代码 每次松弛更新的节点也是不一样的。
而边的顺序是随机的，是题目给我们的，所以本题我们才需要 记录上一次松弛的minDist，来保障 每一次对所有边松弛的结果。
也就是，之前用版本一，是没有负权回路的所适用的，要是有的话，(1,n-1)过程中的结果是根据边的顺序来的，不确定，只能确定第n-1次就是最后一次是固定的答案：
import java.util.*;class Main{public static void main(String[] args){class pair{int t,v;public pair(int a,int b){t=a;v=b;}} class edge{int s,t,v;public edge(int c,int a,int b){s=c;t=a;v=b;}}Scanner scan=new Scanner(System.in);int n=scan.nextInt();int m=scan.nextInt();int[] mniDist=new int[n+1];Arrays.fill(mniDist,Integer.MAX_VALUE);List<edge> graph = new LinkedList<>();for(int i=0;i<m;++i){int a=scan.nextInt();int b=scan.nextInt();int c=scan.nextInt();graph.add(new edge(a,b,c));}int src=scan.nextInt();int dst=scan.nextInt();int k=scan.nextInt();mniDist[src]=0;int[] mniDistCopy=new int[n+1];for(int i=1;i<=k+1;++i){//不能直接=mniDistCopy = Arrays.copyOf(mniDist, mniDist.length);for(edge e:graph){if(mniDistCopy[e.s]<Integer.MAX_VALUE &&mniDistCopy[e.s]+e.v<mniDist[e.t]){//根据上一轮的来mniDist[e.t]=mniDistCopy[e.s]+e.v;}}}if(mniDist[dst]==Integer.MAX_VALUE)System.out.println("unreachable");else System.out.println(mniDist[dst]);}
}SPFA的话，visited要放到循环外面才对，而且不使用copy数组，会超时
import java.util.*;class Main{public static void main(String[] args){class edge{int t,v;public edge(int b,int c){t=b;v=c;}}Scanner scan=new Scanner (System.in);int n=scan.nextInt();int m=scan.nextInt();//链表更高效List<edge>[] graph=new ArrayList[n+1];for(int i=0;i<=n;++i){graph[i] = new ArrayList<>();}for(int i=0;i<m;++i){int a=scan.nextInt();int b=scan.nextInt();int c=scan.nextInt();graph[a].add(new edge(b,c));}int src=scan.nextInt();int dst=scan.nextInt();int k=scan.nextInt();int[] mniDist=new int[n+1];Arrays.fill(mniDist,Integer.MAX_VALUE);mniDist[src]=0;//只是用来保证不重复添加的//放更新了的点Deque<Integer> alreadyDots=new LinkedList<>();alreadyDots.add(src);int[] mniDistCopy=new int[n+1];while(k-->=0 && !alreadyDots.isEmpty()){int qSize=alreadyDots.size();mniDistCopy=Arrays.copyOf(mniDist,mniDist.length);//visited放循环外面会错boolean[] visited=new boolean[n+1];// System.out.println(qSize);while(qSize-->0){int cur=alreadyDots.pollFirst();visited[cur]=false;//只有在队列的元素才是truefor(edge e:graph[cur]){//更新是一定要更新的，入不入对是不一定的//更新是入队的前提if(mniDist[e.t]>mniDistCopy[cur]+e.v){mniDist[e.t]=mniDistCopy[cur]+e.v;//不在队列但已经是最优，不会管，可以有全+回路if(visited[e.t]==false){alreadyDots.addLast(e.t);visited[e.t]=true;}}}}}if(mniDist[dst]==Integer.MAX_VALUE)System.out.println("unreachable");else System.out.println(mniDist[dst]);}
}以后都用这个copy数组好了，有没有负权回路都不会错。
拓展四（能否用dijkstra）
二刷看吧。
97. 小明逛公园
数据结构的过程，大循环是遍历途径节点，所以k是1到n。
原答案先用了 三维数组，然后优化成二维数组，也就是做题的做法。
import java.util.*;class Main{public static void main(String[] args){Scanner scan=new Scanner(System.in);int n = scan.nextInt();int m = scan.nextInt();int[][] graph=new int[n+1][n+1];for(int i=0;i<=n;++i){Arrays.fill(graph[i],Integer.MAX_VALUE);}//公园路，双向图for(int i=0;i<m;++i){int a = scan.nextInt();int b = scan.nextInt();int c = scan.nextInt();graph[a][b]=c;graph[b][a]=c;}for(int k=1;k<=n;++k)//遍历 途径1-n ，找最小值{for(int i=1;i<=n;++i){for(int j=1;j<=n;++j){//防溢出if(graph[i][k]==Integer.MAX_VALUE||graph[k][j]==Integer.MAX_VALUE)continue;graph[i][j]=Math.min(graph[i][j],graph[i][k]+graph[k][j]);} }}int q=scan.nextInt();for(int i=0;i<q;++i){int a = scan.nextInt();int b = scan.nextInt();if(graph[a][b]==Integer.MAX_VALUE){System.out.println(-1);}else{System.out.println(graph[a][b]);}}}
}时间当然是O(n3)；
注意细节，公园是双向图，别溢出了记得跳过。
二刷有时间看一下二维DP推导过程，说了k可不可以放里面，为什么。
127. 骑士的攻击
要么数组越界，要么超时
一开始觉得，找到唯一一个最小距离的下一个点加入就好了，但是不行。直接用堆存这些节点以及对应到终点的距离。每次周边的所有可能 还是都会存进去，但是一直优先取距离小的节点。
所以启发式体现完全靠堆，一直都是小距离的弹出，找到终点的过程是越来越小的距离点进堆，所以之前一些远距离点会慢慢下沉，没有出来的可能——那么问题来了，A * 在一次路径搜索中，大量不需要访问的节点都在队列里，会造成空间的过度消耗。IDA * 算法 对这一空间增长问题进行了优化（没事可以看看）
真的注意的点太多了
1、老是时间超限，最好用欧拉距离，可能欧式开根号时间长。也可以欧式不开根号直接用距离平方。
2、你必须得用的是visited数组，不然一直循环下去？所以加一个count还不如就用 int数组，=0就代表没有访问过。graph的意义是起点到某点的距离。！=1代表访问过了。
3、这个堆里面的类到底怎么做，坐标要有的，最终要得到f，传入3个数让构造函数自己计算f、h就好了。
4、堆的比较器，一直记不住，就（参数）->canshu1.**-canshu2.**就行了。
5、g是上一个的+5
6、弹出节点是终点的话就可以停止了，return，否则也超市
// import java.util.*;// public class Main{
// static int b1,b2;
// static int[][] directs = new int[][]{
// {-2, -1},
// {-2, 1},
// {-1, 2},
// {1, 2},
// {2, 1},
// {2, -1},
// {1, -2},
// {-1, -2}
// };// static int[][] graph=new int[1001][1001];// //坐标-距离 ，是堆的元素，
// static class knight{
// int x,y;
// double g,h,f;//f是总的// //传入四个就可以了
// public knight(int a,int b,double c,double d){
// x=a;
// y=b;
// g=c;
// h=d;
// f=g+h;
// }// public knight() {// }
// }
// //计算欧式距离的，也提取成函数
// private static double ouDistance(int x,int y){
// return Math.sqrt(Math.pow(x-b1,2)+Math.pow(y-b2,2));
// }// private static void astar(knight k){
// PriorityQueue<knight> queue=new PriorityQueue<>((k1,k2)-> (int) (k1.f-k2.f));
// queue.add(k);
// int count=0;
// while(!queue.isEmpty()){
// knight node=queue.poll();//最小的
// for(int[] d:directs){// if(node.x == b1 && node.y==b2)return ;
// int x=node.x+d[0];
// int y=node.y+d[1];
// //bfs有visited记录的
// if (x < 1 || y < 1 || x > 1000 || y > 1000 || graph[x][y]!=0)continue;
// knight next = new knight(x,y,node.g+5,ouDistance(x,y),node.g+5+ouDistance(x,y));// // 到起始点的距离,临近node，直接算
// // next.g=node.g+5;
// // //到重点的距离
// // next.h=ouDistance(x,y);
// queue.add(next);
// graph[x][y]=graph[node.x][node.y]+1;
// }
// }
// }// public static void main(String[] args){
// Scanner scan=new Scanner(System.in);
// int n = scan.nextInt();
// while(n-->0){
// for(int j=0;j<=1000;++j){
// Arrays.fill(graph[j],0);
// }
// int a1=scan.nextInt();
// int a2=scan.nextInt();
// b1=scan.nextInt();
// b2=scan.nextInt();
// double dis=ouDistance(a1,a2);
// astar(new knight(a1,a2,0,dis,dis));
// System.out.println(graph[b1][b2]);
// }
// scan.close();
// }
// }import java.util.*;public class Main {static int b1, b2;static int[][] directs = new int[][]{{-2, -1}, {-2, 1}, {-1, 2}, {1, 2},{2, 1}, {2, -1}, {1, -2}, {-1, -2}};static int[][] graph = new int[1001][1001];// 定义 knight 类static class knight {int x, y;double g, h, f;// 4 参数构造函数public knight(int a, int b, double c, double d) {x = a;y = b;g = c;h = d;f = g + h;}public knight() {}}// 计算欧式距离时间会超限private static double ouDistance(int x, int y) {return (Math.abs(x - b1) * Math.abs(x - b1) + Math.abs(y - b2) * Math.abs(y - b2));}// A* 搜索算法private static void astar(knight k) {//PriorityQueue<knight> queue = new PriorityQueue<>((k1, k2) -> (int)(k1.f-k2.f));PriorityQueue<knight> queue = new PriorityQueue<>((k1, k2) -> Double.compare(k1.f, k2.f));queue.add(k);while (!queue.isEmpty()) {knight node = queue.poll();// 检查是否到达目标位置if (node.x == b1 && node.y == b2) {return;}// 遍历 8 个方向的 "马走日" 移动for (int[] d : directs) {int x = node.x + d[0];int y = node.y + d[1];// 检查边界和是否访问过if (x < 1 || y < 1 || x > 1000 || y > 1000 || graph[x][y] != 0) {continue;}// 创建新的 knight 对象double g = node.g + 5;double h = ouDistance(x, y);knight next = new knight(x, y, g, h);// 更新 graph 数组并加入队列graph[x][y] = graph[node.x][node.y] + 1;queue.add(next);}}}public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();while (n-- > 0) {// 重置 graph 数组for (int j = 0; j <= 1000; ++j) {Arrays.fill(graph[j], 0);}int a1 = scan.nextInt();int a2 = scan.nextInt();b1 = scan.nextInt();b2 = scan.nextInt();// 初始化起点double dis = ouDistance(a1, a2);astar(new knight(a1, a2, 0, dis));// 输出结果System.out.println(graph[b1][b2]);}scan.close();}
}或者堆写外面就创建一次时间也短一些：
import java.util.*;class Main{static int b1,b2;private static int oushiDist(int x,int y){return (int)(Math.pow(x-b1,2)+Math.pow(y-b2,2));}static class knight implements Comparable<knight>{int x,y,g,h;int f;//知3得5public knight(int a,int b,int c){x=a;y=b;g=c;h=oushiDist(a,b);f=g+h;}@Overridepublic int compareTo(knight o) {return this.f-o.f;}}//起点到x，y的距离static int[][] graph=new int[1001][1001];static int[][] directs=new int[][]{{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1}};//队列/栈：Deque，堆：PriorityQueuestatic PriorityQueue<knight> q=new PriorityQueue<>();private static void aStar(knight k){q.add(k);while(!q.isEmpty()){knight node=q.poll();// 检查是否到达目标位置if (node.x == b1 && node.y == b2) {return;}for(int[] d:directs){int nextx=node.x+d[0];int nexty=node.y+d[1];//超边界了 or 之前访过 忽略if(nextx<1 ||nexty<1 ||nextx>1000 ||nexty>1000 ||graph[nextx][nexty]!=0)continue;//不是比较选择入堆，都入堆knight next=new knight(nextx,nexty,node.g+5);q.add(next);graph[nextx][nexty]=graph[node.x][node.y]+1;}}}public static void main(String[] args){Scanner scan=new Scanner(System.in);int n=scan.nextInt();while(n-->0){for(int i=0;i<1001;++i){Arrays.fill(graph[i],0);}q.clear();int a1=scan.nextInt();int a2=scan.nextInt();b1=scan.nextInt();b2=scan.nextInt();aStar(new knight(a1,a2,0));System.out.println(graph[b1][b2]);}scan.close();}
}最坏情况下，A * 退化成广搜，算法的时间复杂度 是 O(n * 2)，n 为节点数量。
最佳情况，是从起点直接到终点，时间复杂度为 O(dlogd)，d 为起点到终点的深度。
实际上 A * 的时间复杂度是介于 最优 和最坏 情况之间， 可以 非常粗略的认为 A * 算法的时间复杂度是 O(nlogn) ，n 为节点数量。
如果本题大家使用 曼哈顿距离 或者 切比雪夫距离 计算的话，可以提交试一试，有的最短路结果是并不是最短的。
A * 算法并不能保证一定是最短路，因为在设计 启发式函数的时候，要考虑 时间效率与准确度之间的一个权衡。
所以 在游戏开发设计中，保证运行效率的情况下，A * 算法中的启发式函数 设计往往不是最短路，而是接近最短路的 次短路设计。
994. 腐烂的橘子
BFS模板kuakua写，不行，坏橘子有多个，不是单源BFS
👇
1、没事，多个起点就一起放队列了再BFS，还是原先的循环不变，没问题，还是一圈一圈的（同一批进队列的可能不在一个圈罢了）。while那一层加加count。一样是层次数。是多源BFS。其实和单源的差不多。同样用队列
👇
2、但是如果队列BFS之前就没有好橘子不用bfs了，输出0，还有好橘子输出-1。就是返回的三种情况需要清晰。
细节有点多：
class Solution {int n;int m;int count=-1;int[][] directs = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};static class pair{int first,second;public pair(int x, int y) {first = x;second = y;}}Deque<pair> q = new LinkedList<>();private void bfs( int[][] grid) {while (!q.isEmpty()) {int qSize = q.size();for (int i = 0; i < qSize; i++) {pair cur = q.pollFirst();for (int[] d : directs) {int nextx = cur.first + d[0];int nexty = cur.second + d[1];//过界、不是好橘子if (nextx < 0 || nextx >= n || nexty < 0 || nexty >= m || grid[nextx][nexty] != 1 ) continue;//必须队列q.addLast(new pair(nextx, nexty));grid[nextx][nexty] = 2;}}count++;}}public int orangesRotting(int[][] grid) {n = grid.length;m = grid[0].length;//遍历前好橘子数量：int hcount=0;for(int i=0;i<n;++i){for(int j=0;j<m;++j){if(grid[i][j]==2){q.addLast(new pair(i,j));}if(grid[i][j]==1){hcount++;}}}if(hcount==0)return 0;bfs(grid);//还有橘子没腐烂，-1for(int i=0;i<n;++i){for(int j=0;j<m;++j){if(grid[i][j]==1){return -1;}}}return count;}
}时间空间O(mn)
207. 课程表
拓扑排序，辅助空间有邻接表、队列、保存入度的数组：
class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {int[] rus=new int[numCourses];Arrays.fill(rus,0);List<Integer>[] graph=new List[numCourses];for(int i=0;i<numCourses;++i){graph[i]=new LinkedList<>();}for(int[] prerequisite:prerequisites){int pre=prerequisite[1];int next=prerequisite[0];graph[pre].add(next);rus[next]++;}Deque<Integer> q=new LinkedList<>();for(int i=0;i<numCourses;++i){if(rus[i]==0)q.addLast(i);}while(!q.isEmpty()){int cur= q.poll();for(int next:graph[cur]){if(--rus[next]==0){q.add(next);}}}for(int ru:rus){if(ru!=0) return false;}return true;}
}拓扑用队列或者栈都一样的。