概论
约 11047 字大约 37 分钟
图
- 图是由顶点（vertex）和边（edge）组成的数据结构，用来表示多对多关系
图的种类
- 有向图：图中边是有方向，加权无向图，图中的边有权值
- 无向图：图中边没有方向，加权有向图，图中的边有权值
图的相关概念
顶点（vertex）：图中的每个节点
边（edge）：图中节点与节点之间的连线
度：与该顶点相连的边的数量，
权：边可以有权重，代表从源顶点到目标顶点的距离、费用、时间或其他度量。
出/入度：在有向图中，每个节点有出度和入度。出度：从该节点出发的边的个数。入度：指向该节点边的个数。
- A (2 out / 0 in)
- B、C、E (1 out / 1 in)
- D (2 out / 2 in)
- F (0 out / 2 in)
连通性：在图中表示节点的连通情况，我们称之为连通性。
连通图：无向图中任何两个节点都是可以到达
非连通图：无向图中有节点不能到达其他节点
强连通图：有向图中任何两个节点是可以相互到达的
连通分量：在无向图中的极大连通子图
- 无向图中节点1、2、5构成的子图就是一个连通分量，该子图所有节点都是相互可达到的。
- 节点3、4、6构成的子图 也是一个连通分量。
- 节点3、4 构成的子图并*不是**该无向图的联通分量吗？因为必须是极大联通子图才能是连通分量，所以必须是节点3、4、6构成的子图才是连通分量。
- 图论中岛屿问题其实就是求连通分量
强连通分量：在有向图中极大强连通子图。
- 节点1、2、3、4、5 构成的子图是强连通分量，因为这是强连通图，也是极大图。
- 节点6、7、8 构成的子图 不是强连通分量，因为这不是强连通图，节点8 不能达到节点6。
- 节点1、2、5 构成的子图 也不是 强连通分量，因为这不是极大图。
图的表达方式
- 邻接矩阵；使用 二维数组来表示图结构。 从节点的角度来表示图
有向图表示：grid[2][5] = 6，表示 节点 2 连接 节点5 为有向图，边的权值为6。
无向图表示：grid[2][5] = 6，grid[5][2] = 6，表示节点2 与 节点5 相互连通，边的权值为6。
优点：简单易理解，检查任意两个顶点间是否存在边的操作非常快，适合稠密图，在边数接近顶点数平方的图中，空间效率高。
缺点：稀疏图导致二维数组过大造成空间浪费 且遍历 边 的时候需要遍历整个n * n矩阵，造成时间浪费
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
// 节点编号从1到n，所以申请 n+1 这么大的数组
int[][] graph = new int[n + 1][n + 1];
for (int i = 0; i < m; i++) {
int s = scanner.nextInt();
int t = scanner.nextInt();
// 使用邻接矩阵表示无向图，1 表示 s 与 t 是相连的
graph[s][t] = 1;
//int val = scanner.nextInt();//有权图，无权图默认1
//graph[s][t] = val;
}
scanner.close();
}
- 邻接表：使用 数组 + 链表的方式来表示。 邻接表是从边的数量来表示图，
优点：只需要存储边，空间利用率高，遍历节点连接情况相对容易
缺点：检查任意两个节点间是否存在边，效率相对低，需要O(V)时间，V表示某节点连接其他节点的数量。复杂不易理解
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();//节点个数
int m = scanner.nextInt();//边数
// 节点编号从1到n，所以申请 n+1 这么大的数组
List<LinkedList<Integer>> graph = new ArrayList<>(n + 1);
for (int i = 0; i <= n; i++) {
graph.add(new LinkedList<>());
}
while (m-- > 0) {
int s = scanner.nextInt();
int t = scanner.nextInt();
// 使用邻接表表示 s -> t 是相连的
graph.get(s).add(t);
}
}
图的遍历
- 图的深度优先搜索(Depth First Search) 。每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。这样的访问策略是优先往纵向挖掘深入，而不是对一个结点的所有邻接结点进行横向访问。是一个递归的过程
void dfs(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本节点所连接的其他节点) {
处理节点;
dfs(图，选择的节点); // 递归
回溯，撤销处理结果
}
}
- 图的广度优先搜索(Broad First Search) 。类似于一个分层搜索的过程，需要使用队列以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点
bfs是先把本节点所连接的所有节点遍历一遍，走到下一个节点的时候，再把连接节点的所有节点遍历一遍，搜索方向更像是广度，四面八方的搜索过程。
广搜的搜索方式就适合于解决两个点之间的最短路径问题。因为广搜是从起点出发，以起始点为中心一圈一圈进行搜索，一旦遇到终点，记录之前走过的节点就是一条最短路。
797所有可能的路径
给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。
示例 1：输入：graph = [[1,2],[3],[3],[]] 输出：[[0,1,3],[0,2,3]]
解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3
示例 2：
输入：graph = [[4,3,1],[3,2,4],[3],[4],[]]
输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
//邻接矩阵写法dfs
class Solution {
List<List<Integer>> results = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
//始终从0开始，所以总是需要把节点0加入
path.add(0);
dfs(graph,0);
return results;
}
//深度搜索，第一个参数是要遍历的图，第二参数是当前节点编号
public void dfs(int[][] graph, int n){
//如果遍历到最后一个节点，则停止遍历
if(n == graph.length - 1){
//达到目标节点，保存此条路径并结束搜索
results.add(new ArrayList<>(path));
return;
}
//遍历当前节点所有关联的节点
for(int i=0; i<graph[n].length; i++){
//将当前节点保存在本次搜索路径中
path.add(graph[n][i]);
//继续遍历与当前节点关联的节点
dfs(graph,graph[n][i]);
//回溯(ArrayList的remove()方法传入整数会被作为下标，
//使用path.size()-1可以严格控制删除最后一个元素)
path.remove(path.size()-1);
}
return;
}
}
//邻接表写法
public class Main {
static List<List<Integer>> result = new ArrayList<>(); // 收集符合条件的路径
static List<Integer> path = new ArrayList<>(); // 1节点到终点的路径
public static void dfs(List<LinkedList<Integer>> graph, int x, int n) {
if (x == n) { // 找到符合条件的一条路径
result.add(new ArrayList<>(path));
return;
}
for (int i : graph.get(x)) { // 找到 x指向的节点
path.add(i); // 遍历到的节点加入到路径中来
dfs(graph, i, n); // 进入下一层递归
path.remove(path.size() - 1); // 回溯，撤销本节点
}
}
public static void mainStart(List<LinkedList<Integer>> graph,int n) {
path.add(1); // 无论什么路径已经是从1节点出发
dfs(graph, 1, n); // 开始遍历
// 输出结果
if (result.isEmpty()) System.out.println(-1);
for (List<Integer> pa : result) {
for (int i = 0; i < pa.size() - 1; i++) {
System.out.print(pa.get(i) + " ");
}
System.out.println(pa.get(pa.size() - 1));
}
}
}
200岛屿数量leetcode
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1
示例 2：
输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3
时间复杂度：O(MN)，其中 M 和 N 分别为行数和列数。
空间复杂度：O(MN)，在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到 MN。
//图的深度优先
//遇到一个没有遍历过的节点陆地，计数器就加一，然后把该节点陆地所能遍历到的陆地都标记上。
//在遇到标记过的陆地节点和海洋节点的时候直接跳过。 这样计数器就是最终岛屿的数量。
import java.util.Scanner;
public class Main {
// 定义方向数组，用于移动：右、下、左、上
private static final int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
// 深度优先搜索方法
public static void dfs(int[][] grid, boolean[][] visited, int x, int y) {
for (int i = 0; i < 4; i++) {
int nextX = x + dir[i][0];
int nextY = y + dir[i][1];
// 检查边界条件和访问条件
if (nextX >= 0 && nextX < grid.length && nextY >= 0 && nextY < grid[0].length) {
if (!visited[nextX][nextY] && grid[nextX][nextY] == 1) {
// 没有访问过的同时是陆地的
visited[nextX][nextY] = true;
dfs(grid, visited, nextX, nextY);
}
}
}
}
// 主方法
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 输入行数
int m = scanner.nextInt(); // 输入列数
int[][] grid = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
grid[i][j] = scanner.nextInt();
}
}
boolean[][] visited = new boolean[n][m]; // 访问标记数组
int result = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!visited[i][j] && grid[i][j] == 1) {
visited[i][j] = true;
result++; // 遇到没访问过的陆地，+1
dfs(grid, visited, i, j); // 将与其链接的陆地都标记为 true
}
}
}
System.out.println(result); // 输出岛屿数量
}
}
//广搜法
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
// 定义方向数组，用于移动：右、下、左、上
private static final int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
// 广度优先搜索方法
public static void bfs(int[][] grid, boolean[][] visited, int x, int y) {
Queue<int[]> que = new LinkedList<>();
que.offer(new int[]{x, y});
visited[x][y] = true; // 只要加入队列，立刻标记
while (!que.isEmpty()) {
int[] cur = que.poll();
int curX = cur[0];
int curY = cur[1];
for (int i = 0; i < 4; i++) {
int nextX = curX + dir[i][0];
int nextY = curY + dir[i][1];
// 检查边界条件和访问条件
if (nextX >= 0 && nextX < grid.length && nextY >= 0 && nextY < grid[0].length) {
if (!visited[nextX][nextY] && grid[nextX][nextY] == 1) {
que.offer(new int[]{nextX, nextY});
visited[nextX][nextY] = true; // 只要加入队列立刻标记
}
}
}
}
}
// 主方法
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 输入行数
int m = scanner.nextInt(); // 输入列数
int[][] grid = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
grid[i][j] = scanner.nextInt();
}
}
boolean[][] visited = new boolean[n][m]; // 访问标记数组
int result = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!visited[i][j] && grid[i][j] == 1) {
result++; // 遇到没访问过的陆地，+1
bfs(grid, visited, i, j); // 将与其链接的陆地都标记为 true
}
}
}
System.out.println(result); // 输出岛屿数量
}
}
图的拓补排序
给出一个 有向无环图，把这个有向图转成线性的排序 就叫拓扑排序。
拓扑排序的应用
- 任务调度：比如编译依赖图中，任务之间有先后依赖关系，拓扑排序可以确定任务的执行顺序。
- 课程安排：在课程依赖图中，某些课程需要先修完某些其他课程，拓扑排序可以用于安排课程的学习顺序。
- 判断有向无环图
- 构建系统：在构建项目时，模块之间可能存在依赖关系，拓扑排序可以决定模块的编译顺序。
拓扑排序的算法
- Kahn's 算法bfs（基于入度）：基于贪心。首先找到图中所有入度为 0 的顶点，将它们加入结果列表，并移除它们的边。然后，继续处理入度变为 0 的顶点，直到所有顶点都被处理完。如果图中存在环，则无法进行拓扑排序。
- 深度优先搜索 (DFS) 的算法：基于递归。对图中的每一个顶点进行 DFS，当某个顶点的所有邻接顶点都已经访问过时，将该顶点加入栈中。最后，栈中保存的顶点顺序即为拓扑排序的结果。
节点的入度表示 有多少条边指向它，节点的出度表示有多少条边 从该节点出发。
Kahn's 算法的步骤
- 找到入度为0 的节点，加入结果集
- 将该节点从图中移除
- 如果我们发现结果集元素个数 不等于 图中节点个数，我们就可以认定图中一定有 有向环！这也是拓扑排序判断有向环的方法。
- 为什么要把节点从图中移除？为的是将该节点作为出发点所连接的边删掉。删掉的目的是什么呢？要把该节点作为出发点所连接的节点的 入度 减一。
基于 DFS 的拓扑排序算法
- 初始化所有顶点为未访问状态。
- 对每一个未访问的顶点调用 DFS。
- 在 DFS 的过程中，递归访问邻接顶点，直到没有未访问的邻接顶点。
- 当一个顶点的所有邻接顶点都已被访问时，将该顶点压入栈。
- 重复步骤 2-4，直到所有顶点都被访问。
- 最后从栈中依次弹出顶点，得到的顺序即为拓扑排序。
题目描述：某个大型软件项目的构建系统拥有 N 个文件，文件编号从 0 到 N - 1，在这些文件中，某些文件依赖于其他文件的内容，这意味着如果文件 A 依赖于文件 B，则必须在处理文件 A 之前处理文件 B （0 <= A, B <= N - 1）。请编写一个算法，用于确定文件处理的顺序。
输入描述：第一行输入两个正整数 M, N。表示 N 个文件之间拥有 M 条依赖关系。后续 M 行，每行两个正整数 S 和 T，表示 T 文件依赖于 S 文件。
输出描述：输出共一行，如果能处理成功，则输出文件顺序，用空格隔开。如果不能成功处理（相互依赖），则输出 -1。
输入示例：
5 4
0 1
0 2
1 3
2 4
- 输出示例：0 1 2 3 4
public class Main {
public static void main(String[] args) {
//第一行输入两个正整数 M, N。表示 N 个文件之间拥有 M 条依赖关系。
//后续 M 行，每行两个正整数 S 和 T，表示 T 文件依赖于 S 文件。
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();//文件数
int m = scanner.nextInt();//一来关系数
List<List<Integer>> umap = new ArrayList<>(); // 记录文件依赖关系
int[] inDegree = new int[n]; // 记录每个文件的入度
for (int i = 0; i < n; i++)
umap.add(new ArrayList<>());
for (int i = 0; i < m; i++) {
int s = scanner.nextInt();
int t = scanner.nextInt();//T 文件依赖于 S 文件。
umap.get(s).add(t); // 记录s指向哪些文件
inDegree[t]++; // t的入度加一
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) {
// 入度为0的文件，可以作为开头，先加入队列
queue.add(i);
}
}
List<Integer> result = new ArrayList<>();
// 拓扑排序
while (!queue.isEmpty()) {
int cur = queue.poll(); // 当前选中的文件
result.add(cur);
for (int file : umap.get(cur)) {
inDegree[file]--; // cur的指向的文件入度-1
if (inDegree[file] == 0) {
queue.add(file);
}
}
}
if (result.size() == n) {
for (int i = 0; i < result.size(); i++) {
System.out.print(result.get(i));
if (i < result.size() - 1) {
System.out.print(" ");
}
}
} else {
System.out.println(-1);
}
}
}
最小生成树普里姆算法prim/克鲁斯卡尔算法Kruskal
最小生成树MST(Minimum Cost Spanning Tree)。给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小.可由普里姆算法和克鲁斯卡尔算法求得
普利姆(Prim)算法采用贪心的策略求最小生成树，在包含n个顶点的连通图中，找出只有(n-1)条边包含所有n个顶点的连通子图(极小连通子图),每次寻找距离 最小生成树最近的节点 并加入到最小生成树中
prim三部曲
- 第一步，选距离生成树最近节点
- 第二步，最近节点加入生成树
- 第三步，更新非生成树节点到生成树的距离（即更新minDist数组）
使用一维数组记录路径。 parent[节点编号]=节点编号,就把一条边记录下来了,不是parent[cur] = j原因是，当cur=1第一个节点在筛选小于10001的值时，很多j值都满足条件，则parent[cur]被反复覆盖例如cur = 1， 在 for循环中可能j=2、3都符合条件，那么本来应该记录节点1 与2、3、4相连的.如果parent[cur] = j更新逻辑parent[1]=2, parent[1]=3.只能记录节点1与3相连，其他相连情况都被覆盖了.如果这么写 parent[j] = cur， 那就是 parent[2] = 1, parent[3] = 1才能完整表示出 节点1与其他节点都是链接的，没有被覆盖。
kruscal的思路：
- 遍历根据权值排序后的边
- 如果边首尾的两个节点在同一个集合，说明如果连上这条边图中会出现环
- 如果边首尾的两个节点不在同一个集合，加入到最小生成树，并把两个节点加入同一个集合
prim 算法是对节点进行操作的，节点数越少越好。时间复杂度为 O(n^2)，其中n为节点数量，它的运行效率和图中边数无关，适用稠密图（接近或等于完全图（所有节点皆相连））。
Kruskal算法是对边进行操作的，边越少越好， 时间复杂度 为 nlogn，其中n 为边的数量，适用稀疏图(边数少)。
无向图中已知所有的岛屿以及它们之间的距离。以最小化公路建设长度确保链接到所有岛屿。
输入描述：第一行包含两个整数V 和 E，V代表顶点数，E代表边数 。顶点编号是从1到V。例如：V=2，一个有两个顶点，分别是1和2。接下来共有 E 行，每行三个整数 v1，v2 和 val，v1 和 v2 为边的起点和终点，val代表边的权值。
输出描述：输出联通所有岛屿的最小路径总距离6
Prim
import java.util.*;
public class Prim {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int v = scanner.nextInt();
int e = scanner.nextInt();
int[][] grid = new int[v + 1][v + 1];//1.初始化邻接矩阵
for (int i = 0; i <= v; i++) {
Arrays.fill(grid[i], Integer.MAX_VALUE);
}
for (int i = 0; i < e; i++) {
int x = scanner.nextInt();
int y = scanner.nextInt();
int k = scanner.nextInt();
grid[x][y] = k;
grid[y][x] = k;
}
scanner.close();
int[] minDist = new int[v + 1];//2.所有节点到最小生成树的最小距离
Arrays.fill(minDist, Integer.MAX_VALUE);
boolean[] visited = new boolean[v + 1];//3. 记录节点是否已访问
int[] parent = new int[v+1];//4.记录路径
for (int i = 1; i < v; i++) {//5.循环v-1
int cur = 1;
int minVal = Integer.MAX_VALUE;
for (int j = 1; j <= v; j++) {//6.选择距离生成树最近的节点
if (!visited[j] && minDist[j] < minVal) {
minVal = minDist[j];
cur = j;
}
}
visited[cur] = true;//7.将最近的节点加入生成树
for (int j = 1; j <= v; j++) {// 8.更新非生成树节点到生成树的距离
if (!visited[j] && grid[cur][j] != Integer.MAX_VALUE && grid[cur][j] < minDist[j]) {
minDist[j] = grid[cur][j];
parent[j] = cur;//记录路径
}
}
}
int result = 0;
for (int i = 2; i <= v; i++) {
result += minDist[i];
//System.out.println(parent[i] + " - " + i + "\t" + grid[i][parent[i]]);
}
System.out.println(result);
}
}
Kruscal
import java.util.*;
class Edge {
int l, r, val;
Edge(int l, int r, int val) {
this.l = l;
this.r = r;
this.val = val;
}
}
public class Kruscal {
private static int[] father = new int[10001];
public static void init() {
for (int i = 0; i < n; i++) {
father[i] = i;
}
}
public static int find(int u) {
if (u == father[u]) return u;
return father[u] = find(father[u]);
}
public static void join(int u, int v) {
u = find(u);
v = find(v);
if (u != v) father[v] = u;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int v = scanner.nextInt();
int e = scanner.nextInt();
List<Edge> edges = new ArrayList<>();//1.初始化边
for (int i = 0; i < e; i++) {
int v1 = scanner.nextInt();
int v2 = scanner.nextInt();
int val = scanner.nextInt();
edges.add(new Edge(v1, v2, val));
}
scanner.close();
List<Edge> result = new ArrayList<>(); // 存储最小生成树的边
edges.sort(Comparator.comparingInt(edge -> edge.val));//排序
init();
int result_val = 0;
for (Edge edge : edges) {
int x = find(edge.l);
int y = find(edge.r);
if (x != y) {
result_val += edge.val;
result.add(edge); // 保存最小生成树的边
join(x, y);
}
}
System.out.println(result_val);
// for (Edge edge : result) {
// System.out.println(edge.l + " - " + edge.r + " : " + edge.val);
// }
}
}
测试数据
//答案6
// String input = "7 11\n" +
// "1 2 1\n" +
// "1 3 1\n" +
// "1 5 2\n" +
// "2 6 1\n" +
// "2 4 2\n" +
// "2 3 2\n" +
// "3 4 1\n" +
// "4 5 1\n" +
// "5 6 2\n" +
// "5 7 1\n" +
// "6 7 1\n";
// System.setIn(new ByteArrayInputStream(input.getBytes()));
迪杰特斯拉算法Dijkstra
- 求有向图中从起点到终点的最短路径
- 输入描述：第一行包含两个正整数，第一个正整数 N 表示一共有 N 个公共汽车站，第二个正整数 M 表示有 M 条公路。接下来为 M 行，每行包括三个整数，S、E 和 V，代表了从 S 车站可以单向直达 E 车站，并且需要花费 V 单位的时间。
- 输出描述：输出一个整数，代表小明从起点到终点所花费的最小时间。
- 输出示例：12
注意：
dijkstra 算法可以同时求 起点到所有节点的最短路径
权值不能为负数
- dijkstra三部曲：
第一步，选源点到哪个节点近且该节点未被访问过
第二步，该最近节点被标记访问过
第三步，更新非访问节点到源点的距离（即更新minDist数组）
prim是求 非访问节点到最小生成树的最小距离，
因为 minDist表示 节点到最小生成树的最小距离，所以 新节点cur的加入，只需要 使用 grid[cur][j] ，grid[cur][j] 就表示 cur 加入生成树后，生成树到 节点j 的距离。
而 dijkstra是求 非访问节点到源点的最小距离。
因为 minDist表示 节点到源点的最小距离，所以 新节点 cur 的加入，需要使用 源点到cur的距离 （minDist[cur]） + cur 到 节点 v 的距离 （grid[cur][v]），才是 源点到节点v的距离。
不能求负数权的原因是，可以选负数边的时候，因为负数变的终点已经被选择了
prim算法 可以有负权值吗？当然可以！prim算法只需要将节点以最小权值和链接在一起，不涉及到单一路径
朴素版当 n 很大，边 的数量 也很多的时候（稠密图）
SPFA堆优化的整体思路和 朴素版是大体一样的，区别是 堆优化从边的角度出发且利用堆来排序。
但 n 很大，边 的数量 很小的时候（稀疏图），是不是可以换成从边的角度来求最短路呢？
朴素版
import java.util.*;
public class Dijkstra {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int v = scanner.nextInt();
int e = scanner.nextInt();
int[][] grid = new int[v + 1][v + 1];
for (int i = 0; i <= v; i++) {
Arrays.fill(grid[i], Integer.MAX_VALUE);
}
for (int i = 0; i < e; i++) {
int x = scanner.nextInt();
int y = scanner.nextInt();
int k = scanner.nextInt();
grid[x][y] = k;
// grid[y][x] = k;//区别1：迪杰特斯拉是有向图
}
int[] minDist = new int[v + 1];
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[1]=0;//区别2. 迪杰特斯拉选定起点
boolean[] visited = new boolean[v + 1];
for (int i = 1; i < v; i++) {
int cur = 1;
int minVal = Integer.MAX_VALUE;
for (int j = 1; j <= v; j++) {
if (!visited[j] && minDist[j] < minVal) {
minVal = minDist[j];
cur = j;
}
}
visited[cur] = true;
for (int j = 1; j <= v; j++) {//区别3：更新起点到终点的最小距离,且可达
if (!visited[j] && grid[cur][j] != Integer.MAX_VALUE
&& minDist[cur] + grid[cur][j] < minDist[j]) {
minDist[j] = minDist[cur] + grid[cur][j];
}
}
}
if (minDist[v] == Integer.MAX_VALUE) {//区别4：minDist是起点到终点的最小距离
System.out.println(-1);
} else {
System.out.println(minDist[v]);
}
scanner.close();
}
}
SPFA
import java.util.*;
public class DijkstraSPFA {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int v = scanner.nextInt();
int e = scanner.nextInt();
List<List<Edge>> grid = new ArrayList<>(v + 1);
for (int i = 0; i <= v; i++) {
grid.add(new ArrayList<>());
}
for (int i = 0; i < e; i++) {
int p1 = scanner.nextInt();
int p2 = scanner.nextInt();
int val = scanner.nextInt();
grid.get(p1).add(new Edge(p2, val));
}
int[] minDist = new int[v + 1];
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[1] = 0;
boolean[] visited = new boolean[v + 1];
PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(edge -> edge.val));
pq.add(new Edge(1, 0));//初始化队列，源点到源点的距离为0，所以初始为0
while (!pq.isEmpty()) {
Edge cur = pq.poll();// 1. 选源点到哪个节点近且该节点未被访问过（通过优先级队列实现
if (visited[cur.to]) continue;
visited[cur.to] = true;// 2. 该最近节点被标记访问过
for (Edge edge : grid.get(cur.to)) { // 3. 更新非访问节点到源点的距离minDist数组
// cur指向的节点edge.to，这条边的权值为 edge.val
if (!visited[edge.to] && minDist[cur.to] + edge.val < minDist[edge.to]) {
minDist[edge.to] = minDist[cur.to] + edge.val;
pq.add(new Edge(edge.to, minDist[edge.to]));
}
}
}
if (minDist[v] == Integer.MAX_VALUE) {
System.out.println(-1); // 不能到达终点
} else {
System.out.println(minDist[v]); // 到达终点最短路径
}
}
}
class Edge{
int to,val;
public Edge(int to,int val){
this.to = to;
this.val = val;
}
}
测试数据
// String input = "7 9\n" +
// "1 2 1\n" +
// "1 3 4\n" +
// "2 3 2\n" +
// "2 4 5\n" +
// "3 4 2\n" +
// "4 5 3\n" +
// "2 6 4\n" +
// "5 7 4\n" +
// "6 7 9\n";
// System.setIn(new ByteArrayInputStream(input.getBytes()));
Bellman_ford算法
Bellman_ford算法的核心思想是 采用动态规划对所有边进行松弛n-1次操作（n为节点数量），从而求得目标最短路。
什么叫做松弛relax the edge,求minDist时，minDist[B] = min(minDist[A] + value, minDist[B])
状态一： minDist[A] + value 可以推出 minDist[B] 状态二： minDist[B]本身就有权值 （可能是其他边链接的节点B 例如节点C，以至于 minDist[B]记录了其他边到minDist[B]的权值）
为什么是n-1？对所有边松弛一次，相当于计算 起点到达 与起点一条边相连的节点 的最短距离，1到n则需要n-1次松弛
Bellman_ford分类
- 正权回路：松弛n次以上 会怎么样？在没有负权回路的图中，松弛 n 次以上 ，结果不会有变化。
- 负权回路（图中出现环且环上的边总权值为负数。如果在这样的图中求最短路的话， 就会在这个环里无限循环 （也是负数+负数 只会越来越小），无法求出最短路径。）负权回路，如果松弛 n 次，结果就会有变化了，因为 有负权回路 就是可以无限最短路径（一直绕圈，就可以一直得到无限小的最短距离）。
那么每松弛一次，都会更新最短路径，所以结果会一直有变化。 - 单源有限回路：最多经过 k 个城市的条件下，而不是一定经过k个城市，也可以经过的城市数量比k小，但要最短的路径。本题是最多经过 k 个城市， 那么是 k + 1条边相连的节点。为什么是k+1？1->2->3->4。节点1 最多已经经过2个节点 到达节点4，那么中间是有多少条边呢，是 3 条边对吧。
所以本题就是求：起点最多经过k + 1 条边到达终点的最短距离。
对所有边松弛一次，相当于计算 起点到达 与起点一条边相连的节点 的最短距离，那么对所有边松弛 k + 1次，就是求 起点到达 与起点k + 1条边相连的节点的 最短距离。因为minDist可能因为负权回路导致不应该本轮更新的负权回路节点也跟着更新了，下一轮才更新的节点因为本轮算出来的值更新了，导致所有的minDist都更新了一遍
在每次计算 minDist 时候，要基于 对所有边上一次松弛的 minDist 数值才行，所以我们要记录上一次松弛的minDist。
1.边的顺序影响松弛更新的结果
2.本题可以有负权回路，说明只要多做松弛，结果是会变的。本题要求最多经过k个节点，对松弛次数是有限制的。本体关注松弛结果，而上面的只要松弛结果变了就认为成环了
3.dijkstra 是贪心的思路 每一次搜索都只会找距离源点最近的非访问过的节点。如果限制最多访问k个节点，那么 dijkstra 未必能在有限次就能到达终点，即使在经过k个节点确实可以到达终点的情况下。
Bellman_ford 队列优化算法（又名SPFA）
只需要对 上一次松弛的时候更新过的节点作为出发节点所连接的边 进行松弛就够了。
基于以上思路，如何记录 上次松弛的时候更新过的节点呢？
用队列来记录。（其实用栈也行，对元素顺序没有要求）
在理论上 时间复杂度更胜一筹，但实际上，也要看图的稠密程度，如果 图很大且非常稠密的情况下，虽然 SPFA的时间复杂度接近Bellman_ford，但实际时间消耗 可能是 SPFA耗时更多。
在正权回路上， (!que.empty()) 队里里 会不会造成死循环？ 正权回路 就是有环，但环的总权值为正数。在有环且只有正权回路的情况下，即使元素重复加入队列，最后，也会因为 所有边都松弛后，节点数值（minDist数组）不在发生变化了 而终止。（而且有重复元素加入队列是正常的，多条路径到达同一个节点，节点必要要选择一个最短的路径，而这个节点就会重复加入队列进行判断，选一个最短的）
对所有边 最多松弛 n -1 次，就一定可以求出所有起点到所有节点的最小距离即 minDist数组。即使再松弛n次以上， 所有起点到所有节点的最小距离（minDist数组） 不会再变了。
SPFA版本
稠密大图，该图有250个节点和10000条边， 在这种情况下， SPFA 的时间复杂度 是接近与 bellman_ford的。
但因为 SPFA 节点的进出队列操作，耗时很大，所以相同的时间复杂度的情况下，SPFA 实际上更耗时了。
朴素版
public class BellmanFord {
public static void main(String[] args) {
// String input = "6 7\n" +
// "5 6 -2\n" +
// "1 2 1\n" +
// "5 3 1\n" +
// "2 5 2\n" +
// "2 4 -3\n" +
// "4 6 4\n" +
// "1 3 5\n";
// String input = "4 4\n" +
// "1 2 -1\n" +
// "2 3 1\n" +
// "3 1 -1\n" +
// "3 4 1";
String input = "6 7\n" +
"1 2 1\n" +
"2 4 -3\n" +
"2 5 2\n" +
"1 3 5\n" +
"3 5 1\n" +
"4 6 4\n" +
"5 6 -2\n" +
"2 6 1";
System.setIn(new ByteArrayInputStream(input.getBytes()));
Scanner scanner = new Scanner(System.in);
int v = scanner.nextInt();
int e = scanner.nextInt();
List<int[]> grid = new ArrayList<>();
for(int i=0;i<e;i++){
int x = scanner.nextInt();
int y = scanner.nextInt();
int z = scanner.nextInt();
grid.add(new int[]{x,y,z});
}
// bellmanFord(grid,v,e);
// bellmanFord2(grid,v,e);
int src = scanner.nextInt(); // 起点
int dst = scanner.nextInt(); // 终点
int k = scanner.nextInt(); // 最大允许步数
bellmanFord3(grid,v,e,src,dst,k);
}
}
正权回路
public static void bellmanFord(List<int[]> grid,int v,int e){
int[] midDest = new int[v+1];
Arrays.fill(midDest,Integer.MAX_VALUE);
midDest[1] = 0;
for(int i = 1;i < v; i++){
for(int[] side : grid){
int from = side[0];
int to = side[1];
int val = side[2];
if(midDest[from] != Integer.MAX_VALUE && midDest[to] > midDest[from] + val){
midDest[to] = midDest[from] + val;
}
}
}
if (midDest[v] == Integer.MAX_VALUE) {
System.out.println("unconnected"); // 不能到达终点
} else {
System.out.println(midDest[v]); // 到达终点最短路径
}
}
负权回路
public static void bellmanFord2(List<int[]> grid,int v,int e){
int[] midDest = new int[v+1];
Arrays.fill(midDest,Integer.MAX_VALUE);
midDest[1] = 0;
boolean flag = false;//区别1.flag
for (int i = 1; i <= v; i++) { // 区别2.松弛n次，最后一次判断负权回路
for (int[] side : grid) {
int from = side[0];
int to = side[1];
int price = side[2];
if (i < v) { // 区别3.多加一次松弛判断负权回路
if (midDest[from] != Integer.MAX_VALUE && midDest[to] > midDest[from] + price) {
midDest[to] = midDest[from] + price;
}
} else {
if (midDest[from] != Integer.MAX_VALUE && midDest[to] > midDest[from] + price) {
flag = true;
}
}
}
}
if (flag) {//区别4.flag判断circle
System.out.println("circle");
} else if (midDest[v] == Integer.MAX_VALUE) {
System.out.println("unconnected");
} else {
System.out.println(midDest[v]);
}
}
单源有限回路
public static void bellmanFord3(List<int[]> grid,int v,int e,int src,int dst,int k){
int[] minDist = new int[v + 1];
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[src] = 0;
int[] minDistCopy = new int[v + 1]; // 区别1.复制数组
for (int i = 1; i <= k + 1; i++) {//区别2.k+1次
minDistCopy = minDist.clone();
for (int[] side : grid) {
int from = side[0];
int to = side[1];
int price = side[2];
//区别3. 使用 minDistCopy 来计算 minDist
if (minDistCopy[from] != Integer.MAX_VALUE && minDist[to] > minDistCopy[from] + price){
minDist[to] = minDistCopy[from] + price;
}
}
}
//区别4.dst不一样
if (minDist[dst] == Integer.MAX_VALUE) {
System.out.println("unreachable"); // 不能到达终点
} else {
System.out.println(minDist[dst]); // 到达终点最短路径
}
}
SPFA公共测试
import java.util.*;
class Edge { // 邻接表
int to,val; // 链接的节点val; // 边的权重
Edge(int to, int val) { // 构造函数
this.to = to;
this.val = val;
}
}
public class BellmanFordSPFA {
public static void main(String[] args) {
// String input = "6 7\n" +
// "5 6 -2\n" +
// "1 2 1\n" +
// "5 3 1\n" +
// "2 5 2\n" +
// "2 4 -3\n" +
// "4 6 4\n" +
// "1 3 5\n";
// String input = "4 4\n" +
// "1 2 -1\n" +
// "2 3 1\n" +
// "3 1 -1\n" +
// "3 4 1";
String input = "6 7\n" +
"1 2 1\n" +
"2 4 -3\n" +
"2 5 2\n" +
"1 3 5\n" +
"3 5 1\n" +
"4 6 4\n" +
"5 6 -2\n" +
"2 6 1";
System.setIn(new ByteArrayInputStream(input.getBytes()));
Scanner scanner = new Scanner(System.in);
int v = scanner.nextInt();
int e = scanner.nextInt();
List<List<Edge>> edges = new ArrayList<>(v + 1);
for(int i=0;i<=v;i++) {
edges.add(new ArrayList<>());
}
// 将所有边保存起来
for (int i = 0; i < e; i++) {
int p1 = scanner.nextInt();
int p2 = scanner.nextInt();
int val = scanner.nextInt();
edges.get(p1).add(new Edge(p2, val));
}
// bellmanFordSPFA(edges,v,e);
// bellmanFordSPFA2(edges,v,e);
int start = scanner.nextInt(); // 起点
int end = scanner.nextInt(); // 终点
int k = scanner.nextInt(); // 允许的最大边数
bellmanFordSPFA3(edges,v,e,start,end,k);
}
}
正权回路
public static void bellmanFordSPFA(List<List<Edge>> edges,int v,int e){
int[] minDist = new int[v + 1];
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[1] = 0;
Queue<Integer> queue = new LinkedList<>();
queue.add(1);
boolean[] isInQueue = new boolean[v + 1]; //区别1. 优化已经在队里的元素不用重复添加
while (!queue.isEmpty()) {
int node = queue.poll();
isInQueue[node] = false; //区别2. 从队列里取出的时候，取消标记
for (Edge edge : edges.get(node)) {
int from = node;
int to = edge.to;
int value = edge.val;
if (minDist[to] > minDist[from] + value) { // 开始松弛
minDist[to] = minDist[from] + value;
if (!isInQueue[to]) { // 区别3.已经在队列里的元素不用重复添加
queue.add(to);
isInQueue[to] = true;
}
}
}
}
if (minDist[v] == Integer.MAX_VALUE) {
System.out.println("unconnected"); // 不能到达终点
} else {
System.out.println(minDist[v]); // 到达终点最短路径
}
}
负权回路
public static void bellmanFordSPFA2(List<List<Edge>> edges,int v,int e){
int[] minDist = new int[v + 1];
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[1] = 0;
Queue<Integer> queue = new LinkedList<>();
queue.add(1); // 队列里放入起点
int[] count = new int[v + 1]; // 记录节点加入队列的次数
count[1]++;
boolean flag = false;
while (!queue.isEmpty()) {
int node = queue.poll();
for (Edge edge : edges.get(node)) {
int from = node;
int to = edge.to;
int value = edge.val;
if (minDist[to] > minDist[from] + value) { // 开始松弛
minDist[to] = minDist[from] + value;
queue.add(to);
count[to]++;
if (count[to] == v) { // 如果加入队列次数超过 n-1 次，说明图中存在负权回路
flag = true;
queue.clear(); // 清空队列
break;
}
}
}
}
if (flag) {
System.out.println("circle");
} else if (minDist[v] == Integer.MAX_VALUE) {
System.out.println("unconnected");
} else {
System.out.println(minDist[v]);
}
}
单源有限回路
public static void bellmanFordSPFA3(List<List<Edge>> edges,int v,int e,int start,int end,int k){
int[] minDist = new int[v + 1];
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[start] = 0;
Queue<Integer> queue = new LinkedList<>();
queue.offer(start); // 队列里放入起点
int[] minDistCopy = new int[v + 1]; // 用来记录每一次遍历的结果
k++;
while (k-- > 0 && !queue.isEmpty()) {
boolean[] visited = new boolean[v + 1]; // 每一轮松弛中，控制节点不用重复入队列
minDistCopy = minDist.clone(); // 复制数组内容
int queueSize = queue.size();
while (queueSize-- > 0) {
int node = queue.poll();
for (Edge edge : edges.get(node)) {
int from = node;
int to = edge.to;
int price = edge.val;
if (minDist[to] > minDistCopy[from] + price) {
minDist[to] = minDistCopy[from] + price;
if (visited[to]) continue; // 不用重复放入队列，但需要重复松弛，所以放在这里位置
visited[to] = true;
queue.offer(to);
}
}
}
}
if (minDist[end] == Integer.MAX_VALUE) {
System.out.println("unreachable");
} else {
System.out.println(minDist[end]);
}
}
Floyd 算法
- 多源最短路问题。即 求多个起点到多个终点的多条最短路径。
- dijkstra朴素版、dijkstra堆优化、Bellman算法、Bellman队列优化（SPFA） 都是单源最短路，即只能有一个起点。
- Floyd算法核心思想是动态规划。例如我们再求节点1 到 节点9 的最短距离，用二维数组来表示即：grid[1][9]，如果最短距离是10 ，那就是 grid[1][9] = 10。
那 节点1 到 节点9 的最短距离 是不是可以由 节点1 到节点5的最短距离 + 节点5到节点9的最短距离组成呢？
即 grid[1][9] = grid[1][5] + grid[5][9]
节点1 到节点5的最短距离 是不是可以有 节点1 到 节点3的最短距离 + 节点3 到 节点5 的最短距离组成呢？
即 grid[1][5] = grid[1][3] + grid[3][5]
以此类推，节点1 到 节点3的最短距离 可以由更小的区间组成。
那么这样我们是不是就找到了，子问题推导求出整体最优方案的递归关系呢。
节点1 到 节点9 的最短距离 可以由 节点1 到节点5的最短距离 + 节点5到节点9的最短距离组成， 也可以有 节点1 到节点7的最短距离 + 节点7 到节点9的最短距离的距离组成。
那么选哪个呢？要选一个最小的，毕竟是求最短路。
此时我们已经接近明确递归公式了。 - 动规五部曲：
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
空间优化
从滚动数组的角度来看，我们定义一个 grid[n + 1][ n + 1][2] 这么大的数组就可以，因为k 只是依赖于 k-1的状态，并不需要记录k-2，k-3，k-4 等等这些状态。
那么我们只需要记录 grid[i][j][1] 和 grid[i][j][0] 就好，之后就是 grid[i][j][1] 和 grid[i][j][0] 交替滚动。
如果本层计算（本层计算即k相同，从三维角度来讲） gird[i][j] 用到了 本层中刚计算好的 grid[i][k] 会有什么问题吗？
如果 本层刚计算好的 grid[i][k] 比上一层 （即k-1层）计算的 grid[i][k] 小，说明确实有 i 到 k 的更短路径，那么基于 更小的 grid[i][k] 去计算 gird[i][j] 没有问题。
如果 本层刚计算好的 grid[i][k] 比上一层 （即k-1层）计算的 grid[i][k] 大， 这不可能，因为这样也不会做更新 grid[i][k]的操作。
所以本层计算中，使用了本层计算过的 grid[i][k] 和 grid[k][j] 是没问题的。
那么就没必要区分，grid[i][k] 和 grid[k][j] 是 属于 k - 1 层的呢，还是 k 层的。
import java.util.*;
public class Floyd {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 节点数量
int m = scanner.nextInt(); // 边的数量
int[][] grid = new int[n + 1][n + 1]; // 定义邻接矩阵
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
grid[i][j] = Integer.MAX_VALUE;
}
}
for (int i = 0; i < m; i++) {
int p1 = scanner.nextInt();
int p2 = scanner.nextInt();
int val = scanner.nextInt();
grid[p1][p2] = val;
grid[p2][p1] = val; // 双向图
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
grid[i][j] = Math.min(grid[i][j], grid[i][k] + grid[k][j]);
}
}
}
int z = scanner.nextInt();
while (z-- > 0) {
int start = scanner.nextInt();
int end = scanner.nextInt();
if (grid[start][end] == 10005) {
System.out.println(-1);
} else {
System.out.println(grid[start][end]);
}
}
}
}
A * 算法精讲 （A star算法）
Astar 是一种 广搜的改良版。 在搜索最短路的时候， 如果是无权图（边的权值都是1） 那就用广搜，代码简洁，时间效率和 dijkstra 差不多 （具体要取决于图的稠密）
如果是有权图（边有不同的权值），优先考虑 dijkstra。
而 Astar 关键在于 启发式函数， 也就是 影响 广搜或者 dijkstra 从 容器（队列）里取元素的优先顺序。
BFS 是没有目的性的 一圈一圈去搜索， 而 A * 是有方向性的去搜索。可以节省很多没有必要的遍历步骤。
对队列里节点进行排序，就需要给每一个节点权值，如何计算权值呢？
每个节点的权值为F，给出公式为：F = G + H
G：起点达到目前遍历节点的距离
F：目前遍历的节点到达终点的距离
起点达到目前遍历节点的距离 + 目前遍历的节点到达终点的距离 就是起点到达终点的距离。
本题的图是无权网格状，在计算两点距离通常有如下三种计算方式：
曼哈顿距离，计算方式： d = abs(x1-x2)+abs(y1-y2)
欧氏距离（欧拉距离） ，计算方式：d = sqrt( (x1-x2)^2 + (y1-y2)^2 )
切比雪夫距离，计算方式：d = max(abs(x1 - x2), abs(y1 - y2))
x1, x2 为起点坐标，y1, y2 为终点坐标 ，abs 为求绝对值，sqrt 为求开根号，
选择哪一种距离计算方式 也会导致 A * 算法的结果不同。
本题，采用欧拉距离才能最大程度体现 点与点之间的距离。
所以 使用欧拉距离计算 和 广搜搜出来的最短路的节点数是一样的。 （路径可能不同，但路径上的节点数是相同的）
计算出来 F 之后，按照 F 的 大小，来选去出队列的节点。
可以使用 优先级队列 帮我们排好序，每次出队列，就是F最小的节点。
A * 算法的时间复杂度 其实是不好去量化的，因为他取决于 启发式函数怎么写。
最坏情况下，A * 退化成广搜，算法的时间复杂度 是 O(n * 2)，n 为节点数量。
最佳情况，是从起点直接到终点，时间复杂度为 O(dlogd)，d 为起点到终点的深度。
因为在搜索的过程中也需要堆排序，所以是 O(dlogd)。
实际上 A * 的时间复杂度是介于 最优 和最坏 情况之间， 可以 非常粗略的认为 A * 算法的时间复杂度是 O(nlogn) ，n 为节点数量。
A * 算法的空间复杂度 O(b ^ d) ,d 为起点到终点的深度，b 是 图中节点间的连接数量，本题因为是无权网格图，所以 节点间连接数量为 4。
A * 算法并不能保证一定是最短路，因为在设计 启发式函数的时候，要考虑 时间效率与准确度之间的一个权衡。
保证运行效率的情况下，A * 算法中的启发式函数 设计往往不是最短路，而是接近最短路的 次短路设计。
缺点：A * 在一次路径搜索中，大量不需要访问的节点都在队列里，会造成空间的过度消耗。
如果题目中，给出 多个可能的目标，然后在这多个目标中 选择最近的目标，这种 A * 就不擅长了， A * 只擅长给出明确的目标 然后找到最短路径。
如果是多个目标找最近目标（特别是潜在目标数量很多的时候），可以考虑 Dijkstra ，BFS 或者 Floyd。
总结
- 单源且边为正数，直接Dijkstra。
- 稠密图都是朴素版，稀疏图都有堆优化
- 单源边可为负数或者有限节点最短路，Bellman-Ford，
- 如果是遇到多源点求最短路，直接 Floyd。
- 对于A * 游戏开发、地图导航、数据包路由等都广泛使用 A * 算法。