## Kruskal算法 **最小生成树**：在无向图里找到一个连通图的所有顶点的无环子集，使得子集中的边的权重之和最小。 ### 算法描述 kruskal算法求图的最小生成树（加边法） 1. 初始化map，key=顶点，value=包含自己顶点的集合 2. 建立小根堆，按图里所有边的权值排序 3. 依次取出堆里的最小边，判断边的from和to顶点是否在同一个集合 4. 如果不在就记录边到结果集合里，并且将from和to顶点合并到同一个集合 ### 步骤图解析       ``` kruskal mst edge: edge: 3->5的weight=1 edge: 1->3的weight=2 edge: 1->2的weight=3 edge: 2->4的weight=5 ``` ### Java代码实现 ~~~ /** * kruskal算法求图的最小生成树（加边法） * 1. 初始化map，key=顶点，value=包含自己顶点的集合 * 2. 建立小根堆，按图里所有边的权值排序 * 3. 依次取出堆里的最小边，判断边的from和to顶点是否在同一个集合 * 4. 如果不在就记录边到结果集合里，并且将from和to顶点合并到同一个集合 * @return 最小边集合 */ public Set<Edge> kruskalMST(){ Set<Edge> result = new LinkedHashSet<>(); SimpleSet simpleSet = new SimpleSet(vertexs.values()); // 小根堆，使用边的权值排序 PriorityQueue<Edge> edgePQ = new PriorityQueue<>(((o1, o2) -> o1.weight - o2.weight)); for(Edge edge : edges){ edgePQ.offer(edge); } while (!edgePQ.isEmpty()){ Edge edge = edgePQ.poll(); // 边的from和to不在同一个集合里 if(!simpleSet.isSameSet(edge.from,edge.to)){ // 合并 simpleSet.union(edge.from,edge.to); result.add(edge); } } return result; } ~~~ ~~~ // 简单集合，替代并查集，提供判断2个顶点是否在同一个集合的方法和合并2个顶点到同一个集合的方法 class SimpleSet{ private Map<Vertex,Set<Vertex>> vertexSetMap; // 初始化map,key=顶点，value=包含自己顶点的set public SimpleSet(Collection<Vertex> vertexs){ vertexSetMap = new HashMap<>(); for(Vertex vertex : vertexs){ Set<Vertex> set = new HashSet<>(); set.add(vertex); vertexSetMap.put(vertex,set); } } /** * 判断2个顶点在同一集合 * @param from 开始顶点 * @param to 结束顶点 * @return 在同一个集合里返回true，反之返回false */ public boolean isSameSet(Vertex from,Vertex to){ return vertexSetMap.get(from) == vertexSetMap.get(to); } /** * 合并2个顶点到同一个集合 * @param from 开始顶点 * @param to 结束顶点 */ public void union(Vertex from,Vertex to){ Set<Vertex> fromSet = vertexSetMap.get(from); fromSet.addAll(vertexSetMap.get(to)); vertexSetMap.put(from,fromSet); for(Vertex next : vertexSetMap.get(to)){ vertexSetMap.put(next,fromSet); } } } ~~~