克鲁斯克尔算法Kruskal‘s algorithm java code 参考了 https://zh.wikipedia.org/wiki/%E5%85%8B%E9%B2%81%E6%96%AF%E5%85%8B%E5%B0%94%E6%BC%94%E7%AE%97%E6%B3%95 因为没有给出java版的代码，所以自己写了：
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Comparator; import java.util.HashSet; import java.util.Iterator; import java.util.List; import java.util.PriorityQueue; import java.util.Queue; import java.util.Set; import java.util.StringTokenizer; //5 7 //1 2 9 //1 5 5 //2 5 3 //2 3 8 //2 4 2 //3 4 9 //4 5 6 //6 9 //1 2 8 //1 4 9 //2 4 1 //2 5 5 //2 3 6 //2 6 2 //3 6 7 //4 5 3 //5 6 4 class Comp4 implements Comparator<Edgee> { @Override public int compare(Edgee o1, Edgee o2) { // return o2.weight-o1.weight;//max return o1.weight - o2.weight;// mini } } class Vertev { int key; public Vertev(int key) { this.key = key; } } class Edgee { Vertev from; Vertev to; int weight; public Edgee(Vertev from, Vertev to, int weight) { this.from = from; this.to = to; this.weight = weight; } } public class kruskal { public static void main(String[] args) throws IOException { kruskalGraph(); doMethod(); } static int vs, es; public static List<Set<Edgee>> Graph = new ArrayList<>(); public static List<Set<Vertev>> AGraph = new ArrayList<>(); public static PriorityQueue<Edgee> pq = new PriorityQueue<Edgee>(new Comp4()); public static void kruskalGraph() throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); vs = Integer.parseInt(st.nextToken()); es = Integer.parseInt(st.nextToken()); for (int s = 0; s < es; s++) { st = new StringTokenizer(br.readLine()); int x = Integer.parseInt(st.nextToken()); int y = Integer.parseInt(st.nextToken()); int w = Integer.parseInt(st.nextToken()); Vertev vx = new Vertev(x); Vertev vy = new Vertev(y); Edgee edg = new Edgee(vx, vy, w); pq.add(edg); } } public static void doMethod() { while (!pq.isEmpty()) { Edgee edge = pq.poll(); checkConn(edge); if (Graph.size() >= 2) { joinone(); } } Iterator it = Graph.get(0).iterator(); int Sum = 0; while (it.hasNext()) { Edgee v = (Edgee) it.next(); System.out.println(" from " + v.from.key + "---> to " + v.to.key + " weight " + v.weight); Sum += v.weight; } System.out.println(Sum); } public static void joinone() { Set<Edgee> newGraph = Graph.get(0); Set<Vertev> newSet = AGraph.get(0); ArrayList<Integer> keep = new ArrayList<>(); for (int g = 1; g < AGraph.size(); g++) { Iterator it = AGraph.get(g).iterator(); int mark = 0; while (it.hasNext()) { Vertev h = (Vertev) it.next(); if (isSetContain(newSet, h)) {// -- 包涵两个以上的不能加 排除 mark++; if (mark >= 2) { break; } } } if (mark < 2) { newGraph.addAll(Graph.get(g)); Graph.remove(g); keep.add(g); } else { Graph.remove(g); keep.add(g); } } for (int i = 0; i < keep.size(); i++) { AGraph.remove(i); } } public static void checkConn(Edgee edge) { boolean ishas = false; AGraph = new ArrayList<>(); for (Set<Edgee> st : Graph) { Set<Vertev> aset = new HashSet<Vertev>(); Iterator it = st.iterator(); while (it.hasNext()) { Edgee e = (Edgee) it.next(); aset.add(e.from); aset.add(e.to); } if (isSetContain(aset, edge.from) && !isSetContain(aset, edge.to)) { st.add(edge); aset.add(edge.to); ishas = true; } else if (!isSetContain(aset, edge.from) && isSetContain(aset, edge.to)) { st.add(edge); aset.add(edge.from); ishas = true; } AGraph.add(aset); } if (!ishas) { if (Graph.size() == 0) { Set<Vertev> aset = new HashSet<Vertev>(); aset.add(edge.from); aset.add(edge.to); AGraph.add(aset); } Set<Edgee> tmp = new HashSet<>(); tmp.add(edge); Graph.add(tmp); } } public static boolean isSetContain(Set<Vertev> p, Vertev x) { boolean ret = false; Iterator it = p.iterator(); while (it.hasNext()) { Vertev t = (Vertev) it.next(); if (t.key == x.key) { ret = true; break; } } return ret; } }
