## Prim算法 **最小生成樹**：在無向圖里找到一個連通圖的所有頂點的無環子集，使得子集中的邊的權重之和最小。 ### 算法描述 prim算法求圖的最小生成樹（加點法）： 1. 從圖里一個頂點出發，找該點相鄰的最小邊edge加入到小根堆 2. 取出小根堆里的邊edge,判斷edge的to頂點是否已經經過，沒有則找到最小邊，有則跳過 3. 將edge.to頂點的相鄰邊加入到小根堆里，循環2，3步驟 ### 步驟圖解析  ``` prim mst edge: edge: 1->3的weight=2 edge: 3->5的weight=1 edge: 1->2的weight=3 edge: 2->4的weight=5 ``` ### Java代碼實現 ~~~ /** * prim算法求圖的最小生成樹（加點法） * 1. 從圖里一個頂點出發，找該點相鄰的最小邊edge加入到小根堆 * 2. 取出小根堆里的邊edge,判斷edge的to頂點是否已經經過，沒有則找到最小邊，有則跳過 * 3. 將edge.to頂點的相鄰邊加入到小根堆里，循環2，3步驟 * @return 最小邊集合 */ public Set<Edge> primMST(){ Set<Edge> result = new LinkedHashSet<>(); // 小根堆，使用邊的權值排序 PriorityQueue<Edge> edgePQ = new PriorityQueue<>(((o1, o2) -> o1.weight - o2.weight)); Set<Vertex> pass = new HashSet<>(); // 加上循環是為了防止森林場景 for(Vertex vertex : vertexs.values()){ // 該頂點沒有在pass里 if(!pass.contains(vertex)) { // 將頂點加入到pass里，表示經過該頂點 pass.add(vertex); // 將該頂點的相鄰的邊加入到堆里 for (Edge edge : vertex.edges) { edgePQ.offer(edge); } // 取出該節點最小邊 while (!edgePQ.isEmpty()) { Edge edge = edgePQ.poll(); // 沒有經過edge.to頂點 if (!pass.contains(edge.to)) { // 記錄到邊集合里 result.add(edge); // 將edge.to頂點加入到pass里 pass.add(edge.to); // 將edge.to頂點相鄰的邊加入到小根堆里 for (Edge next : edge.to.edges) { if (!edgePQ.contains(next)) { edgePQ.offer(next); } } } } } } return result; } ~~~