图论-代码随想录刷题记录[JAVA]
文章目录
- 前言
- Floyd 算法
- dijkstra（朴素版）
- 最小生成树之prim
- kruskal算法
前言
新手小白记录第一次刷代码随想录
1.自用 抽取精简的解题思路 方便复盘
2.代码尽量多加注释
3.记录踩坑
4.边刷边记录，更有成就感！
5.解题思路绝大部分来自代码随想录【仅自用 无商用！！！】
Floyd 算法
【题目描述】
小明喜欢去公园散步，公园内布置了许多的景点，相互之间通过小路连接，小明希望在观看景点的同时，能够节省体力，走最短的路径。
给定一个公园景点图，图中有 N 个景点（编号为 1 到 N），以及 M 条双向道路连接着这些景点。每条道路上行走的距离都是已知的。
小明有 Q 个观景计划，每个计划都有一个起点 start 和一个终点 end，表示他想从景点 start 前往景点 end。由于小明希望节省体力，他想知道每个观景计划中从起点到终点的最短路径长度。 请你帮助小明计算出每个观景计划的最短路径长度。
【输入描述】
第一行包含两个整数 N, M, 分别表示景点的数量和道路的数量。
接下来的 M 行，每行包含三个整数 u, v, w，表示景点 u 和景点 v 之间有一条长度为 w 的双向道路。
接下里的一行包含一个整数 Q，表示观景计划的数量。
接下来的 Q 行，每行包含两个整数 start, end，表示一个观景计划的起点和终点。
【输出描述】
对于每个观景计划，输出一行表示从起点到终点的最短路径长度。如果两个景点之间不存在路径，则输出 -1。
【输入示例】
7 3 1 2 4 2 5 6 3 6 8 2 1 2 2 3
【输出示例】
4 -1
【提示信息】
从 1 到 2 的路径长度为 4，2 到 3 之间并没有道路。
1 <= N, M, Q <= 1000.
思路
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的最短距离的距离组成。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 顶点数
int m = sc.nextInt(); // 边数
// 初始化距离矩阵，最大值设置为10005
final int INF = 10005;
int[][] grid = new int[n + 1][n + 1];
// 初始化 grid 数组
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i != j) {
grid[i][j] = INF;
}
}
}
// 输入边信息
for (int i = 0; i < m; i++) {
int p1 = sc.nextInt();
int p2 = sc.nextInt();
int val = sc.nextInt();
grid[p1][p2] = val;
grid[p2][p1] = val; // 双向图
}
// Floyd-Warshall 算法
//注意k要放在最外层
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (grid[i][k] + grid[k][j] < grid[i][j]) {
grid[i][j] = grid[i][k] + grid[k][j];
}
}
}
}
// 输出查询结果
int z = sc.nextInt(); // 查询次数
while (z-- > 0) {
int start = sc.nextInt();
int end = sc.nextInt();
if (grid[start][end] == INF) {
System.out.println(-1);
} else {
System.out.println(grid[start][end]);
}
}
sc.close(); // 关闭Scanner
}
}
dijkstra（朴素版）
【题目描述】
小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。
小明的起点是第一个车站，终点是最后一个车站。然而，途中的各个车站之间的道路状况、交通拥堵程度以及可能的自然因素（如天气变化）等不同，这些因素都会影响每条路径的通行时间。
小明希望能选择一条花费时间最少的路线，以确保他能够尽快到达目的地。
【输入描述】
第一行包含两个正整数，第一个正整数 N 表示一共有 N 个公共汽车站，第二个正整数 M 表示有 M 条公路。
接下来为 M 行，每行包括三个整数，S、E 和 V，代表了从 S 车站可以单向直达 E 车站，并且需要花费 V 单位的时间。
【输出描述】
输出一个整数，代表小明从起点到终点所花费的最小时间。
思路
- 第一步，选源点到哪个节点近且该节点未被访问过
- 第二步，该最近节点被标记访问过
- 第三步，更新非访问节点到源点的距离（即更新minDist数组
- minDist数组 用来记录 每一个节点距离源点的最小距离。
- 示例中节点编号是从1开始，所以为了让大家看的不晕，minDist数组下标我也从 1 开始计数，下标0 就不使用了，这样 下标和节点标号就可以对应上了，避免大家搞混
模拟过程
0、初始化
minDist数组数值初始化为int最大值。
这里在强点一下 minDist数组的含义：记录所有节点到源点的最短路径，那么初始化的时候就应该初始为最大值，这样才能在后续出现最短路径的时候及时更新。
源点（节点1） 到自己的距离为0，所以 minDist[1] = 0
此时所有节点都没有被访问过，所以 visited数组都为0
- 模拟过程
以下为dijkstra 三部曲
1.1 第一次模拟
1、选源点到哪个节点近且该节点未被访问过
源点距离源点最近，距离为0，且未被访问。
2、该最近节点被标记访问过
标记源点访问过
3、更新非访问节点到源点的距离（即更新minDist数组） ，如图：
更新 minDist数组，即：源点（节点1） 到 节点2 和 节点3的距离。
源点到节点2的最短距离为1，小于原minDist[2]的数值max，更新minDist[2] = 1
源点到节点3的最短距离为4，小于原minDist[3]的数值max，更新minDist[3] = 4
1.2 第二次模拟
1、选源点到哪个节点近且该节点未被访问过
未访问过的节点中，源点到节点2距离最近，选节点2
2、该最近节点被标记访问过
节点2被标记访问过
3、更新非访问节点到源点的距离（即更新minDist数组） ，如图：
更新 minDist数组，即：源点（节点1） 到 节点6 、 节点3 和 节点4的距离。
以后的过程以此类推
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 输入节点数 n 和边数 m
int n = sc.nextInt();
int m = sc.nextInt();
// 定义一个邻接矩阵，初始化为一个很大的数
final int INF = Integer.MAX_VALUE;
int[][] grid = new int[n + 1][n + 1];
// 初始化 grid 为 INF，表示没有直接路径
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i != j) {
grid[i][j] = INF;
}
}
}
// 输入边的信息
for (int i = 0; i < m; i++) {
int p1 = sc.nextInt();
int p2 = sc.nextInt();
int val = sc.nextInt();
grid[p1][p2] = val;
}
// 设置起点和终点
int start = 1;
int end = n;
// 存储从源点到每个节点的最短距离
int[] minDist = new int[n + 1];
// 记录顶点是否被访问过
boolean[] visited = new boolean[n + 1];
// 初始化最短距离数组，起始点到自身的距离为0，其他为INF
for (int i = 1; i <= n; i++) {
minDist[i] = INF;
}
minDist[start] = 0;
// 遍历所有节点，执行Dijkstra算法
for (int i = 1; i <= n; i++) {
int minVal = INF;
int cur = -1;
// 选择距离起点最近且未访问过的节点
for (int v = 1; v <= n; v++) {
if (!visited[v] && minDist[v] < minVal) {
minVal = minDist[v];
cur = v;
}
}
// 如果当前节点无法访问，则跳出循环（即剩下的节点不可达）
if (cur == -1) break;
visited[cur] = true; // 标记该节点已被访问
// 更新非访问节点到源点的最短距离
for (int v = 1; v <= n; v++) {
if (!visited[v] && grid[cur][v] != INF && minDist[cur] + grid[cur][v] < minDist[v]) {
minDist[v] = minDist[cur] + grid[cur][v];
}
}
}
// 输出结果，如果终点不可达，输出 -1
if (minDist[end] == INF) {
System.out.println(-1);
} else {
System.out.println(minDist[end]);
}
sc.close(); // 关闭Scanner
}
}
最小生成树之prim
卡码网：53.寻宝
题目描述：
在世界的某个区域，有一些分散的神秘岛屿，每个岛屿上都有一种珍稀的资源或者宝藏。国王打算在这些岛屿上建公路，方便运输。
不同岛屿之间，路途距离不同，国王希望你可以规划建公路的方案，如何可以以最短的总公路距离将 所有岛屿联通起来。
给定一张地图，其中包括了所有的岛屿，以及它们之间的距离。以最小化公路建设长度，确保可以链接到所有岛屿。
输入描述：
第一行包含两个整数V 和 E，V代表顶点数，E代表边数 。顶点编号是从1到V。例如：V=2，一个有两个顶点，分别是1和2。
接下来共有 E 行，每行三个整数 v1，v2 和 val，v1 和 v2 为边的起点和终点，val代表边的权值。
输出描述：
输出联通所有岛屿的最小路径总距离
输入示例：
7 11
1 2 1
1 3 1
1 5 2
2 6 1
2 4 2
2 3 2
3 4 1
4 5 1
5 6 2
5 7 1
6 7 1
输出示例：
6
思路
-
第一步，选距离生成树最近节点
-
第二步，最近节点加入生成树
-
第三步，更新非生成树节点到生成树的距离（即更新minDist数组）
-
minDist数组用来记录 每一个节点距离最小生成树的最近距离。
-
示例中节点编号是从1开始，minDist数组下标也从 1 开始计数。
初始状态
minDist 数组 里的数值初始化为 最大数，因为本题 节点距离不会超过 10000，所以 初始化最大数为 10001就可以。
现在 还没有最小生成树，默认每个节点距离最小生成树是最大的，这样后面我们在比较的时候，发现更近的距离，才能更新到 minDist 数组上。
模拟过程（只模拟两轮）
第一轮
1、prim三部曲，第一步：选距离生成树最近节点
选择距离最小生成树最近的节点，加入到最小生成树，刚开始还没有最小生成树，所以随便选一个节点加入就好（因为每一个节点一定会在最小生成树里，所以随便选一个就好），那我们选择节点1 （符合遍历数组的习惯，第一个遍历的也是节点1）
2、prim三部曲，第二步：最近节点加入生成树
此时 节点1 已经算最小生成树的节点。
3、prim三部曲，第三步：更新非生成树节点到生成树的距离（即更新minDist数组）
注意图中我标记了 minDist数组里更新的权值，是哪两个节点之间的权值，例如 minDist[2] =1 ，这个 1 是 节点1 与 节点2 之间的连线，清楚这一点对最后我们记录 最小生成树的权值总和很重要。
第二轮
1、prim三部曲，第一步：选距离生成树最近节点
选取一个距离 最小生成树（节点1） 最近的非生成树里的节点，节点2，3，5 距离 最小生成树（节点1） 最近，选节点 2（其实选 节点3或者节点2都可以，距离一样的）加入最小生成树。
2、prim三部曲，第二步：最近节点加入生成树
此时 节点1 和 节点2，已经是最小生成树的节点。
3、prim三部曲，第三步：更新非生成树节点到生成树的距离（即更新minDist数组）
接下来，我们要更新节点距离最小生成树的距离，如图：
import java.util.*;
public class Main {
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 = 1; i <= v; i++) {
Arrays.fill(grid[i], 10001);
}
// 读取边的信息并填充邻接矩阵
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;
}
// 所有节点到最小生成树的最小距离
int[] minDist = new int[v + 1];
Arrays.fill(minDist, 10001);
// 记录节点是否在树里
boolean[] isInTree = new boolean[v + 1];
// Prim算法主循环
只需要循环v-1次建立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 (!isInTree[j] && minDist[j] < minVal) {
minVal = minDist[j];
cur = j;
}
}
// 将最近的节点加入生成树
isInTree[cur] = true;
// 更新非生成树节点到生成树的距离
for (int j = 1; j <= v; j++) {
//当前cur节点比较
if (!isInTree[j] && grid[cur][j] < minDist[j]) {
minDist[j] = grid[cur][j];
}
}
}
// 统计结果
int result = 0;
for (int i = 2; i <= v; i++) {
result += minDist[i];// 从2开始，跳过起始节点
}
System.out.println(result);
scanner.close();
}
}
kruskal算法
- 题目同上题，找最小生成树。
思路
- prim 算法是维护节点的集合，而 Kruskal 是维护边的集合。
- 边的权值排序，因为要优先选最小的边加入到生成树里
- 遍历排序后的边
- 如果边首尾的两个节点在同一个集合，说明如果连上这条边图中会出现环
- 如果边首尾的两个节点不在同一个集合，加入到最小生成树，并把两个节点加入同一个集合
模拟
排序后的边顺序为[(1,2) (4,5) (1,3) (2,6) (3,4) (6,7) (5,7) (1,5) (3,2) (2,4) (5,6)]
(1,2) 表示节点1 与 节点2 之间的边。权值相同的边，先后顺序无所谓。
开始从头遍历排序后的边。
选边(1,2)，节点1 和 节点2 不在同一个集合，所以生成树可以添加边(1,2)，并将 节点1，节点2 放在同一个集合。
选边(4,5)，节点4 和 节点 5 不在同一个集合，生成树可以添加边(4,5) ，并将节点4，节点5 放到同一个集合。
在上面的讲解中，看图的话 大家知道如何判断 两个节点 是否在同一个集合（是否有绿色的线连在一起），以及如何把两个节点加入集合（就在图中把两个节点连上）
- 但在代码中，如果将两个节点加入同一个集合，又如何判断两个节点是否在同一个集合呢？
- 用并查集
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 Main {
private static int n = 10001;
private static int[] father = new int[n];
// 并查集初始化
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) return;
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<>();
int result_val = 0;
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));
}
//对边进行排序
edges.sort(Comparator.comparingInt(edge -> edge.val));
// 并查集初始化
init();
// 从头开始遍历边
for (Edge edge : edges) {
int x = find(edge.l);
int y = find(edge.r);
if (x != y) {
result_val += edge.val;
join(x, y);
}
}
System.out.println(result_val);
scanner.close();
}
}