ThinkChat2.0新版上线,更智能更精彩,支持会话、画图、阅读、搜索等,送10W Token,即刻开启你的AI之旅 广告
## Prim算法 **最小生成树**:在无向图里找到一个连通图的所有顶点的无环子集,使得子集中的边的权重之和最小。 ### 算法描述 prim算法求图的最小生成树(加点法): 1. 从图里一个顶点出发,找该点相邻的最小边edge加入到小根堆 2. 取出小根堆里的边edge,判断edge的to顶点是否已经经过,没有则找到最小边,有则跳过 3. 将edge.to顶点的相邻边加入到小根堆里,循环2,3步骤 ### 步骤图解析 ![](https://img.kancloud.cn/1d/99/1d9931f2f1ffac60e4fbb1bad1c51dd8_2006x1238.png) ``` 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; } ~~~