图之最小生成树

最小生成树

假设图中有N个结点，最小生成树，就是在图中找（N-1）条边，把所有的结点连接起来，同时要保证边的权重和最小

kruskal算法

• 将边按权重排序，并且认为所有的点都是孤立的集合
• 找到权重最小的边，把边的两个点并为一个集合
• 找到权重第二小的边，判断边的两个点是否已经是同一个集合
  • 是，忽略这个边
  • 否，将边的两个点合并为一个集合
• 以此找其他的边

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) {  
      priorityQueue.add(edge);  
   }  
   Set<Edge> result = new HashSet<>();  
   while (!priorityQueue.isEmpty()) {  
      Edge edge = priorityQueue.poll();  
      if (!unionFind.isSameSet(edge.from, edge.to)) {  
         result.add(edge);  
         unionFind.union(edge.from, edge.to);  
      }  
   }  
   return result;  
}