图论
797. 所有可能的路径
为什么path先把索引加上，图这个数据结构的索引，包含了数据信息，所以索引到数据表再到索引这个过程。一般回溯索引没有涉及问题中的含义。
class Solution {
List<Integer> path=new ArrayList<>();//Deque
List<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<>();//Deque
List<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)
{
//二维必须包含最内层的new
graph[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 duplicate
public 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 duplicate
public 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有的例子输入了0
father = 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->v
static 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 false
static 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，选中，更新isInTree
isInTree[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->v
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 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);
}
//步骤2
while(!q.isEmpty()){
int a=q.poll();
result.add(a);
for(int j :outedge[a]){
//如果相关节点受影响之后（是前++）变成了无入度，又要加入到q
if(--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;//得初始化：起点到自己距离是0
boolean[] 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;//只有在队列的元素才是true
for(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;//只有在队列的元素才是true
for(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;//只有在队列的元素才是true
for(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得5
public knight(int a,int b,int c){
x=a;
y=b;
g=c;
h=oushiDist(a,b);
f=g+h;
}
@Override
public 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，堆：PriorityQueue
static 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 * 算法中的启发式函数 设计往往不是最短路，而是接近最短路的 次短路设计。
