注册型网站推广,莆田百度seo排名,苏州有做网站的公司吗,dede小说网站模板实现描述
为了造出一棵最小生成树#xff0c;我们从最小边权的边开始#xff0c;按边权从小到大依次加入#xff0c;如果某次加边产生了环#xff0c;就扔掉这条边#xff0c;直到加入了 n-1 条边#xff0c;即形成了一棵树。
实现代码
首选我们对所有的边#xff0c…实现描述
为了造出一棵最小生成树我们从最小边权的边开始按边权从小到大依次加入如果某次加边产生了环就扔掉这条边直到加入了 n-1 条边即形成了一棵树。
实现代码
首选我们对所有的边按照权重排序之后从小到大选择边如果当前的边已经连通过了则放弃此边查看下一条边若没有连通过通过并查集进行连通直至所有点都访问过此时完成。 如上图节点0~5边关系如上 先对边权重进行从小到大排序得到
[{u:4,v:5,weight:1
},{u:0,v:5,weight:3
},{u:1,v:2,weight:4
},{u:0,v:1,weight:5
},{u:2,v:3,weight:5
},{u:3,v:4,weight:5
},{u:3,v:5,weight:6
},{u:0,v:3,weight:7
},{u:0,v:2,weight:8
},{u:2,v:5,weight:9
}]然后依次选择排序后的边 下面代码对应上图数据及其过程
import com.alibaba.fastjson.JSONObject;
import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;
import org.jetbrains.annotations.NotNull;import java.util.*;public class kruskal {/*** 边定义*/DataAllArgsConstructorNoArgsConstructorstatic class Edge implements ComparableEdge {int u, v;int weight;Overridepublic int compareTo(NotNull Edge o) {return weight - o.weight;}}static ListEdge getKruskalEdges(int nodeNum, int[][] grid) {ListEdge result new LinkedList();ListEdge edges new LinkedList();for (int i 0; i grid.length; i) {int u grid[i][0];int v grid[i][1];int weight grid[i][2];edges.add(new Edge(u, v, weight));}Collections.sort(edges);UnionFindTemplate uf new UnionFindTemplate(nodeNum);SetInteger visited new HashSet();for (Edge edge : edges) {if (uf.connected(edge.u, edge.v)) {continue;}uf.union(edge.u, edge.v);visited.add(edge.u);visited.add(edge.v);result.add(edge);if (visited.size() nodeNum) {break;}}return result;}public static void main(String[] args) {int nodeNum 6;int[][] grid {{0, 1, 5},{0, 5, 3},{0, 3, 7},{0, 2, 8},{1, 2, 4},{2, 5, 9},{3, 5, 6},{2, 3, 5},{3, 4, 5},{4, 5, 1}};System.out.println(JSONObject.toJSONString(getKruskalEdges(nodeNum, grid)));}
}其中并查集模版的实现如下
public class UnionFindTemplate {int[] parent;int[] size;int n;public int setCount;//连通分量个数public UnionFindTemplate(int n) {this.n n;this.parent new int[n];this.size new int[n];setCount n;Arrays.fill(this.size, 1);for (int i 0; i n; i) {parent[i] i;}}public int findParent(int x) {if (parent[x] x) {return x;} else {parent[x] findParent(parent[x]);return parent[x];}}public void union(int x, int y) {x findParent(x);y findParent(y);if (x y) {return;}if (size[x] size[y]) {int temp x;x y;y temp;}//y合并到xparent[y] x;size[x] size[y];setCount--;}public boolean connected(int x, int y) {x findParent(x);y findParent(y);return x y;}}
