Condition: undirected graph
Start with edges, add all edges to the priority queue, pop up one by one, if the start and end of the edge are not in the same search set, add the edge to the result set, and merge the two points into the same search set
The diagram is represented and generated in: click on the open link
import java.util.Collection; import java.util.Comparator; import java.util.HashMap; import java.util.HashSet; import java.util.PriorityQueue; import java.util.Set; Public class union-find Set public static class UnionFind {private HashMap<Node, Node> fatherMap; private HashMap<Node, Integer> rankMap; public UnionFind() { fatherMap = new HashMap<Node, Node>(); rankMap = new HashMap<Node, Integer>(); } private Node findFather(Node n) { Node father = fatherMap.get(n); if (father ! = n) { father = findFather(father); } fatherMap.put(n, father); return father; } /** makeSets public void makeSets(Collection<Node> Nodes) {fathermap.clear (); rankMap.clear(); for (Node node : nodes) { fatherMap.put(node, node); rankMap.put(node, 1); } } public boolean isSameSet(Node a, Node b) { return findFather(a) == findFather(b); } public void union(Node a, Node b) { if (a == null || b == null) { return; } Node aFather = findFather(a); Node bFather = findFather(b); if (aFather ! = bFather) { int aFrank = rankMap.get(aFather); int bFrank = rankMap.get(bFather); if (aFrank <= bFrank) { fatherMap.put(aFather, bFather); rankMap.put(bFather, aFrank + bFrank); } else { fatherMap.put(bFather, aFather); rankMap.put(aFather, aFrank + bFrank); }}}} // public static class EdgeComparator implements Comparator<Edge> {@override public int compare(Edge) o1, Edge o2) { return o1.weight - o2.weight; Public static Set<Edge> kruskalMST(Graph Graph) {UnionFind UnionFind = new UnionFind(); unionFind.makeSets(graph.nodes.values()); PriorityQueue<Edge> PriorityQueue = new PriorityQueue<>(new EdgeComparator())); For (Edge Edge: graph.edges) {// add all edges to the priorityQueue priorityqueue.add (Edge); } Set<Edge> result = new HashSet<>(); while (! priorityQueue.isEmpty()) { Edge edge = priorityQueue.poll(); // if (! Unionfind.issameset (edge.from, edge.to)) {// If the edge from and to are already in the set, discard the edge; // Otherwise add the edge to the set and find the set result.add(edge); unionFind.union(edge.from, edge.to); } } return result; }}Copy the code