## 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); } } } ~~~