有哪些做电子小报的网站,知识营销案例有哪些,珠海网站建设哪个平台好,做网站后面加什么53.寻宝 题目#xff1a;53. 寻宝#xff08;第七期模拟笔试#xff09; (kamacoder.com) 思路#xff1a;首先#xff0c;我不知道怎么存这样的东西#xff0c;用三维数组吗#xff0c;没搞懂#xff0c;果断放弃 prim算法实现
import java.util.*;class Main {publi…53.寻宝 题目53. 寻宝第七期模拟笔试 (kamacoder.com) 思路首先我不知道怎么存这样的东西用三维数组吗没搞懂果断放弃 prim算法实现
import java.util.*;class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int v scanner.nextInt();int e scanner.nextInt();// 填一个默认最大值题目描述val最大为10000int[][] 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];// 我们只需要循环 n-1次建立 n - 1条边就可以把n个节点的图连在一起for (int i 1; i v; i) {// 1、prim三部曲第一步选距离生成树最近节点int cur -1; // 选中哪个节点 加入最小生成树int minVal Integer.MAX_VALUE;for (int j 1; j v; j) { // 1 - v顶点编号这里下标从1开始// 选取最小生成树节点的条件// 1不在最小生成树里// 2距离最小生成树最近的节点if (!isInTree[j] minDist[j] minVal) {minVal minDist[j];cur j;}}// 2、prim三部曲第二步最近节点cur加入生成树isInTree[cur] true;// 3、prim三部曲第三步更新非生成树节点到生成树的距离即更新minDist数组// cur节点加入之后 最小生成树加入了新的节点那么所有节点到 最小生成树的距离即minDist数组需要更新一下// 由于cur节点是新加入到最小生成树那么只需要关心与 cur 相连的 非生成树节点 的距离 是否比 原来 非生成树节点到生成树节点的距离更小了呢for (int j 1; j v; j) {// 更新的条件// 1节点是 非生成树里的节点// 2与cur相连的某节点的权值 比 该某节点距离最小生成树的距离小// 很多录友看到自己 就想不明白什么意思其实就是 cur 是新加入 最小生成树的节点那么 所有非生成树的节点距离生成树节点的最近距离 由于 cur的新加入需要更新一下数据了if (!isInTree[j] grid[cur][j] minDist[j]) {minDist[j] grid[cur][j];}}}// 统计结果int result 0;for (int i 2; i v; i) { // 不计第一个顶点因为统计的是边的权值v个节点有 v-1条边result minDist[i];}System.out.println(result);}
}小结
prim算法的关键是加点。
prim三步曲
第一步选距离生成树最近节点第二步最近节点加入生成树第三步更新非生成树节点到生成树的距离即更新minDist数组
Kruskal 算法实现
import java.util.*;class Edge implements ComparableEdge {int l, r, val;Edge(int l, int r, int val) {this.l l;this.r r;this.val val;}Overridepublic int compareTo(Edge other) {return Integer.compare(this.val, other.val);}
}class Main {private static int[] father;// 并查集初始化public static void init(int n) {father new int[n];for (int i 0; i n; i) {father[i] i;}}// 并查集的查找操作public static int find(int u) {return u father[u] ? u : (father[u] find(father[u])); // 路径压缩}// 并查集的加入集合public static void join(int u, int v) {u find(u); // 寻找u的根v find(v); // 寻找v的根if (u ! v) { // 如果发现根不同则将v的根指向u的根father[v] u;}}public static void main(String[] args) {Scanner scanner new Scanner(System.in);int v scanner.nextInt();int e scanner.nextInt();ListEdge edges new ArrayList();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));}// 按边的权值对边进行从小到大排序Collections.sort(edges);// 并查集初始化init(v 1); // 初始化大小为 v 1 的并查集因为节点编号是从 1 开始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; // 这条边可以作为生成树的边join(x, y); // 两个节点加入到同一个集合}}System.out.println(result_val);scanner.close();}
}小结
Kruskal算法需要自定义一个数据结构Edge存放边和权值为了方便比较需要实现Comparable接口
kruscal的思路
边的权值排序因为要优先选最小的边加入到生成树里遍历排序后的边 如果边的两个节点在同一个集合说明如果连上这条边图中会出现环如果边的两个节点不在同一个集合加入到最小生成树并把两个节点加入同一个集合
