彩票网站开发制作模版,渭南seo快速排名,网站建设业务怎么跑,株洲建设网站并查集的延伸--克鲁斯卡尔法求最小生成树MST 力扣 1135 力扣 1584并查集 UnionFind.java 力扣 1135 力扣 1584
package com.caoii;/**program:labu-pratice-study*package:com.caoii*author: Alan*Time: 2024/4/14 9:09*description: 最小生成树相关题目测试*/import org.jun… 并查集的延伸--克鲁斯卡尔法求最小生成树MST 力扣 1135 力扣 1584并查集 UnionFind.java 力扣 1135 力扣 1584
package com.caoii;/**program:labu-pratice-study*package:com.caoii*author: Alan*Time: 2024/4/14 9:09*description: 最小生成树相关题目测试*/import org.junit.jupiter.api.Test;import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;public class MstTest {/*力扣1135想象一下你是个城市基建规划者地图上有 n 座城市它们按以 1 到 n 的次序编号。给你整数 n 和一个数组 conections其中 connections[i] [xi, yi, costi]表示将城市 xi 和城市 yi 连接所要的costi连接是双向的。返回连接所有城市的最低成本每对城市之间至少有一条路径。如果无法连接所有 n 个城市返回 -1 该最小成本 应该是所用全部连接成本的总和*/static class Node {int xi;int yi;int costi;Node(int xi, int yi, int costi) {this.xi xi;this.yi yi;this.costi costi;}}public int minimumCost(int n, int[][] connections) {int sum 0;if (connections.length n - 1) {return -1;// 具备链接条件的边 小于 n-1 条 则无法形成 最小生成树}ArrayListNode nodeArrayList new ArrayListNode();for (int[] connection : connections) {Node node new Node(connection[0], connection[1], connection[2]);nodeArrayList.add(node);}// 按 costi 的值 给 list 排序nodeArrayList.sort(new ComparatorNode() {Overridepublic int compare(Node o1, Node o2) {return o1.costi - o2.costi;}});// 测试排序/*for (Node node : nodeArrayList) {System.out.println(node.xi node.yi node.costi);}*/UnionFind unionFind new UnionFind(n 1);for (Node node : nodeArrayList) {if (!unionFind.connected(node.xi, node.yi)) {unionFind.union(node.xi, node.yi);sum node.costi;if (unionFind.count() 2) {return sum;}}}if (unionFind.count() 2) {return sum;} else {return -1;}}Testpublic void test_01() {int n 4;int connections[][] new int[][]{{1, 2, 3},{3, 4, 4},};System.out.println(minimumCost(n, connections));}/*力扣1584* 给你一个points 数组表示 2D 平面上的一些点其中 points[i] [xi, yi] 。连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 |xi - xj| |yi - yj| 其中 |val| 表示 val 的绝对值。请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时才认为所有点都已连接*/public int minCostConnectPoints(int[][] points) {ArrayListNode nodeArrayList new ArrayListNode();for (int i 0; i points.length; i) {for (int j i 1; j points.length; j) {int costi Math.abs(points[i][0] - points[j][0]) Math.abs(points[i][1] - points[j][1]);Node node new Node(i, j, costi);nodeArrayList.add(node);}// i j 的取值范围 在 0到(n-1) 之间// 此时取到了 任意两个顶点之间相连的 所有边// 不存在找不出 生成树的情况 故而不需要判断 M 是否小于 N-1}// 按照costi 升序排序Collections.sort(nodeArrayList, Comparator.comparingInt((Node a) - a.costi));/*// 测试排序结果for (Node node : nodeArrayList) {System.out.println(node.xi node.yi node.costi);}System.out.println();// 按照costi 降序排序//通过显式指定参数类型可以帮助编译器更好地理解Lambda表达式Collections.sort(nodeArrayList, Comparator.comparingInt((Node a) - a.costi).reversed());for (Node node : nodeArrayList) {System.out.println(node.xi node.yi node.costi);}*/int n points.length;int sum 0;UnionFind unionFind new UnionFind(n);for (Node node : nodeArrayList) {if (!unionFind.connected(node.xi, node.yi)) {unionFind.union(node.xi, node.yi);sum node.costi;if (unionFind.count() 1) {// 只剩一个连通分量 循环结束return sum;}}}// 不存在找不出 生成树的情况 故而不需要在循环结束后再判断 是否还剩唯一一个连通分量return sum;}Testpublic void test_02() {int[][] points new int[][]{{0, 0}, {2, 2}, {3, 10}, {5, 2}, {7, 0}};System.out.println(minCostConnectPoints(points));}
}并查集 UnionFind.java
package com.caoii;/**program:labu-pratice-study*package:com.caoii*author: Alan*Time: 2024/4/12 21:53*description: 并查集的实现*/public class UnionFind {// 记录连通分量private int count;// 节点X的父节点 是 parent[x]private int[] parent;//使用一个size数组 记录每棵树包含的节点数目//来让两个树合并的时候尽量让小的树接到大的树的下面//这样每次使用find向上找根节点的复杂度能相对减少//private int[] size;// 通过改造find函数 可将每个树都变成 真正高度为2// 即 每个子节点都直接与最高根节点相连的样式// 故size就不必再使用了// 构造函数 n 为 图的节点数目public UnionFind(int n) {this.count n;// 一开始互不连通 则 连通分量的数目等于节点数目parent new int[n];// 父节点指针初始时指向自己for (int i 0; i n; i) {parent[i] i;//size[i] 1;}// 若两个节点被连通 则其中任意一个节点的根节点指针指向另一个节点}/*将p和q 所在的连通分量进行 链接*/public void union(int p, int q) {int rootP find(p);int rootQ find(q);// find方法获取两个树的最高根节点if (rootP rootQ) {// 两棵树已经连通则最高根节点一定相同// 不需要 再次链接 直接退出方法return;}/*改进find之后不用size了//两棵树最高根节点不同的时候//两棵树合并为一棵树 设置P的根节点为Qif (size[rootP] size[rootQ]) {parent[rootQ] rootP;size[rootP] size[rootQ];// P树更高 则 把 Q树接在P树下面让Q的父节点指针指向P// P的高度增加// 实际上此时所说的高度不是真的高度而是该树的全部节点个数} else {parent[rootP] rootQ;size[rootQ] size[rootP];}*///两棵树最高根节点不同的时候//两棵树合并为一棵树 设置P的根节点为Qparent[rootP] rootQ;count--;// 两个分量合二为一 分量数目减一}/*返回某个节点X的最高根节点*/public int find(int x) {/*传统方法 逐次向上寻找最高根节点while (parent[x] ! x) {x parent[x];}return x;// 若根节点指针指向自己则返回自己// 若根节点指针没有指向自己则把根节点指针指向的元素赋值给X 并循环判断// 若 3--5--6 则 X3时执行x5 —— 5!parent[5]6 —— x6 —— 6parent[6]6 —— return 6*/// 改进方法 在寻找最高根节点的过程中// 将树构造为 真实高度为2 所有子节点都与根节点直接相连的形式if (parent[x] ! x) {// x的根节点 不是 x 自己// 则x 存在根节点parent[x] find(parent[x]);// 递归运算// 最后}return parent[x];// 递归出口 递归到最高层根节点 此时 xparent[x] 所以返回x// 则 次高层处节点为y, parent[y] find(parent[y]) x// 即次高层处节点的父指针指向最高节点// 同理 次次高层处节点为z, parent[z] find(parent[z]) find(y) parent[y] x// 即次次高层处节点的父指针指向最高节点x// 以此类推// 最后结果就是所有子节点都直接与根节点直接相连 树的真是高度为2}/*判断 p 和 q 是否连通*/public boolean connected(int p, int q) {int rootP find(p);int rootQ find(q);return rootP rootQ;// 若两个树的最高节点相同则p与q连通}/*返回图中有多少个连通分量*/public int count() {return count;}
}
