53. 寻宝 — prim算法
题目链接:https://kamacoder.com/problempage.php?pid=1053
文档讲解:https://programmercarl.com/kamacoder/0053.%E5%AF%BB%E5%AE%9D-prim.html
思路
本题是最小生成树的模板题,最小生成树可以使用 prim算法,也可以使用 kruskal算法计算出来。
prim算法 是从节点的角度 采用贪心的策略 每次寻找距离 最小生成树最近的节点 并加入到最小生成树中。prim算法核心有三步:
- 第一步,选距离生成树最近节点
- 第二步,最近节点加入生成树
- 第三步,更新非生成树节点到生成树的距离(即更新minDist数组)
其中,minDist
数组用来记录每一个节点距离最小生成树的最近距离。minDist
数组里的数值初始化为最大数,因为本题 节点距离不会超过 10000,所以初始化最大数为 10001就可以。
代码
import java.util.*;
class Main{
public static void main (String[] args) {
Scanner in = new Scanner(System.in);
int v = in.nextInt();
int e = in.nextInt();
int[][] grid = new int[v + 1][v + 1];
for (int i = 0; i <= v; i++) {
Arrays.fill(grid[i], 10001);
}
int[] minDist = new int[v + 1];
Arrays.fill(minDist, 10001);
boolean[] isInTree = new boolean[v + 1];
for (int i = 0; i < e; i++) {
int x = in.nextInt(), y = in.nextInt();
grid[x][y] = in.nextInt();
grid[y][x] = grid[x][y];
}
for (int i = 1; i < v; i++) { // 只需要加入v-1条边即可连通
// 1、prim三部曲,第一步:选距离生成树最近节点
int cur = -1, minVal = Integer.MAX_VALUE;
for (int j = 1; j <= v; j++) { // 开始选点
// 选取最小生成树节点的条件:
// (1)不在最小生成树里
// (2)距离最小生成树最近的节点
if (!isInTree[j] && minDist[j] < minVal) {
cur = j;
minVal = minDist[j];
}
}
// 2、prim三部曲,第二步:最近节点(cur)加入生成树
isInTree[cur] = true;
// 3、prim三部曲,第三步:更新非生成树节点到生成树的距离(即更新minDist数组)
for (int j = 1; j <= v; j++) {
if (!isInTree[j] && grid[cur][j] < minDist[j]) {
minDist[j] = grid[cur][j];
}
}
}
int res = 0;
for (int i = 2; i <= v; i++) { // 不计第一个顶点,因为统计的是边的权值,v个节点有 v-1条边
res += minDist[i];
}
System.out.println(res);
}
}
53. 寻宝 — kruskal算法
题目链接:https://kamacoder.com/problempage.php?pid=1053
文档讲解:https://programmercarl.com/kamacoder/0053.%E5%AF%BB%E5%AE%9D-Kruskal.html
思路
prim 算法是维护节点的集合,而 kruskal 是维护边的集合。
kruscal的思路:
- 边的权值排序,因为要优先选最小的边加入到生成树里
- 遍历排序后的边
- 如果边首尾的两个节点在同一个集合,说明如果连上这条边图中会出现环
- 如果边首尾的两个节点不在同一个集合,加入到最小生成树,并把两个节点加入同一个集合
判断首尾两个节点是否在同一个集合,需要用到并查集。
代码
import java.util.*;
import java.util.stream.Collectors;
class Main{
static int[] father;
static int v, e;
static class Edge{
int left, right, val;
public int getVal(){ return val; }
Edge(int left, int right, int val) {
this.left = left;
this.right = right;
this.val = val;
}
}
public static void main (String[] args) {
Scanner in = new Scanner(System.in);
v = in.nextInt();
e = in.nextInt();
father = new int[v + 1];
List<Edge> edgeList = new ArrayList<>();
for (int i = 0; i < e; i++) {
int m = in.nextInt();
int n = in.nextInt();
int dist = in.nextInt();
edgeList.add(new Edge(m, n, dist));
}
// 按边的权值对边进行从小到大排序
edgeList = edgeList.stream().sorted(Comparator.comparing(Edge::getVal)).
collect(Collectors.toList());
init();
int res = 0;
for (Edge edge : edgeList) {
if (!isSame(edge.left, edge.right)) { // 如果不在一个集合中,则加入
res += edge.val;
join(edge.left, edge.right);
}
}
System.out.println(res);
}
public static void init() {
for (int i = 1; i <= v; i++) father[i] = i;
}
public static int find(int u) {
return u == father[u] ? u : (father[u] = find(father[u]));
}
public static boolean isSame(int u, int v) {
return find(u) == find(v);
}
public static void join(int u, int v) {
u = find(u);
v = find(v);
if (u == v) return;
father[v] = u;
}
}
复习二叉树部分
标签:第六十三,prim,int,随想录,生成,nextInt,算法,minDist,节点 From: https://blog.csdn.net/Danny_8/article/details/140299897513.找树左下角的值
112.路径总和
113.路径总和ii
106.从中序与后序遍历序列构造二叉树
105.从前序与中序遍历序列构造二叉树