package graph; import java.io.File; import java.io.FileNotFoundException; import java.util.LinkedList; import java.util.List; import java.util.PriorityQueue; import java.util.Scanner; import uf.UnionFind; class Kedge implements Comparable<Kedge> { final int src, dst; final double weight; Kedge(int src, int dst, double weight) { this.src = src; this.dst = dst; this.weight = weight; } @Override public String toString() { return src+"--"+dst+"("+weight+")"; } @Override public int compareTo(Kedge that) { return this.weight < that.weight ? - 1 : this.weight > that.weight ? + 1 : 0; } } class Kgraph extends Graph<Integer> { final int V; // les sommets sont 0,1,...,V-1 private LinkedList<Kedge> allEdges; Kgraph(int V) { this.V = V; this.allEdges = new LinkedList<>(); } void addEdge(int src, int dst, double w) { assert 0 <= src && src < this.V; assert 0 <= dst && dst < this.V; this.addEdge(src, dst); this.addEdge(dst, src); this.allEdges.add(new Kedge(dst, src, w)); } List<Kedge> allEdges() { return this.allEdges; } } public class Kruskal { static List<Kedge> kruskal(Kgraph g) { List<Kedge> mst = new LinkedList<>(); UnionFind uf = new UnionFind(g.V); PriorityQueue<Kedge> q = new PriorityQueue<>(); q.addAll(g.allEdges()); while (mst.size() < g.V - 1) { Kedge e = q.remove(); if (uf.sameClass(e.src, e.dst)) { System.out.println("on ignore " + e); continue; } System.out.println("on prend " + e); uf.union(e.src, e.dst); mst.add(e); } return mst; } // on suppose ici g connexe static boolean isSpanningTree(Kgraph g, List<Kedge> t) { if (t.size() != g.V - 1) return false; UnionFind uf = new UnionFind(g.V); for (Kedge e: t) { if (uf.find(e.src) == uf.find(e.dst)) return false; uf.union(e.src, e.dst); } return true; } public static void main(String[] args) throws FileNotFoundException { Scanner sc = new Scanner(new File("examEWG.txt")); int V = sc.nextInt(); Kgraph g = new Kgraph(V); int E = sc.nextInt(); while (E-- > 0) g.addEdge(sc.nextInt(), sc.nextInt(), sc.nextDouble()); sc.close(); List<Kedge> mst = kruskal(g); assert isSpanningTree(g, mst); System.out.println(mst); double w = 0.0; for (Kedge e: mst) w += e.weight; System.out.println(w); } }