天津哪里做网站,广告公司网站开发,如何搭建自己的网站平台,做二手车按揭的网站理论知识
Prim算法是一种用于计算加权无向图的最小生成树#xff08;MST, Minimum Spanning Tree#xff09;的贪心算法。最小生成树是一个连通的无向图的子图#xff0c;它包含所有的顶点且总权重最小。Prim算法从一个起始顶点开始#xff0c;不断将权重最小的边加入生成…理论知识
Prim算法是一种用于计算加权无向图的最小生成树MST, Minimum Spanning Tree的贪心算法。最小生成树是一个连通的无向图的子图它包含所有的顶点且总权重最小。Prim算法从一个起始顶点开始不断将权重最小的边加入生成树直到包含图中的所有顶点为止。
关键思想
起点选择从任意一个顶点开始将其标记为已访问。贪心选择从已访问的顶点集合中选择一条连接到未访问顶点的权重最小的边将该边加入MST。更新过程重复选择和标记过程直到所有顶点都包含在MST中。
时间复杂度
使用简单的实现如使用无序数组时Prim算法的时间复杂度为O(V^2)。使用优先队列如最小堆优化时时间复杂度可以降低到O(E log V)其中E是边的数量V是顶点的数量。
算法流程
要改进 LazyPrimMST可以尝试从优先队列中删除失效的边这样优先队列就只含有树顶点和非树顶点之间的横切边。关键在于我们感兴趣的只是连接树顶点和非树顶点中权重最小的边。当我们将顶点 v 添加到树中时对于每个非树顶点 w 产生的变化只可能使得 w 到最小生成树的距离更近了如图所示。简而言之我们不需要在优先队列中保存所有从 w 到树顶点的边——而只需要保存其中权重最小的那条在将 v 添加到树中后检查是否需要更新这条权重最小的边因为v-w 的权重可能更小。我们只需遍历 v 的邻接链表就可以完成这个任务。换句话说我们只会在优先队列中保存每个非树顶点 w 的一条边将它与树中的顶点连接起来的权重最小的那条边。将 w 和树的顶点连接起来的其他权重较大的边迟早都会失效所以没必要在优先队列中保存它们。
PrimMST 类使用了索引优先队列实现的 Prim 算法。它将 LazyPrimMST 中的 marked[] 和 mst[] 替换为两个顶点索引的数组edgeTo[] 和 distTo[]它们具有如下性质。
如果顶点 v 不在树中但至少含有一条边和树相连那么 edgeTo[v] 是将 v 和树连接的最短边distTo[v] 为这条边的权重。所有这类顶点 v 都保存在一条索引优先队列中索引 v 关联的值是 edgeTo[v]的边的权重。
这些性质的关键在于优先队列中的最小键即是权重最小的横切边的权重而和它相关联的顶点 v 就是下一个将被添加到树中的顶点。marked[] 数组已经没有必要了因为判断条件 !marked[w] 等价于 distTo[w] 是无穷的且 edgeTo[w] 为 null。要维护这些数据结构PrimMST 会从优先队列中取出一个顶点 v 并检查它的邻接链表中的每条边 v-w。如果 w 已经被标记过那么这条边就已经失效了如果 w 不在优先队列中或者 v-w 的权重小于目前已知的最小值 edgeTo[w]代码会更新数组将 v-w 作为将 w 和树连接的最佳选择。
以下流程是基于本实验数据描绘的处理轨迹图 解释流程图有助于对代码的理解理解核心原理 关注数据的组织方式 在节点中
白色圆形是树节点灰色圆形是非树节点
在边中 红线代表当前加入优先队列的边 粗红线代表队列中权重最小的边 粗黑线代表已经纳入MST中的边 灰色线代表可以被其他线平替的线 也就是说当我们遍历到一个非树节点时需要判断当前遍历到的边和该非树节点已经被树遍历到的边相比哪个最小不是最小的都会被标记为灰色。如何记录树到非树节点的距离呢是使用ditsTo[非树节点]这个数组来完成的
在Index列中
红色数字代表节点已经被遍历黑色数字代表该节点已经被纳入MST中了marked置为True灰色数字表示节点尚未被遍历 遍历动作一定是由一个新晋的树节点发起的 当树节点遍历到了另一个树节点则直接跳过根据切分定理我们要遍历的是非树节点
在edgeTo列中
黑色数字代表树节点灰色数字代表非树节点当边的两个节点都加入MST后连接符号“-”由红色变为黑色 新加入的边一定包含树节点另外一端肯定要指向某个非树节点非树节点是灰色的数字这里的灰色数字一定是跟index值保持一致的所以我们可以根据非树节点的编号作为索引来管理PQ队列我们的处理核心是与树直连的非树节点
在distTo列中
红色代表尚未确定边是否可以纳入MST黑色代表确定该边已经加入了MST并且已经从PQ中删除红色箭头代表当前PQ中值最小的边 实验数据
8
16
4 5 0.35
4 7 0.37
5 7 0.28
0 7 0.16
1 5 0.32
0 4 0.38
2 3 0.17
1 7 0.19
0 2 0.26
1 2 0.36
1 3 0.29
2 7 0.34
6 2 0.40
3 6 0.52
6 0 0.58
6 4 0.93代码实现
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;public class myPrimMST {private myEdge[] edgeTo;private double[] distTo;private boolean[] marked;private myIndexMinPQDouble pq;private double totalWeight;public myPrimMST(myEdgeWeightedGraph G){edgeTo new myEdge[G.V()];distTo new double[G.V()];marked new boolean[G.V()];pq new myIndexMinPQ(G.V());for(int v0;vG.V();v)distTo[v] Double.POSITIVE_INFINITY;distTo[0] 0.0;pq.insert(0,0.0);while(!pq.isEmpty())visit(G,pq.delMin());}private void visit(myEdgeWeightedGraph G, int v){marked[v] true;for(myEdge e: G.adj(v)){int w e.other(v);if(marked[w]) continue;if(e.weight()distTo[w]){edgeTo[w] e;distTo[w] e.weight();if(pq.contains(w)) pq.change(w,distTo[w]);else pq.insert(w,distTo[w]);}}}public IterablemyEdge edges(){myBagmyEdge mst new myBagmyEdge();for(int v1;v edgeTo.length;v)mst.add(edgeTo[v]);return mst;}public double weight(){totalWeight 0.00;for(myEdge e:edges()){totalWeight e.weight();StdOut.println(totalWeight);}return totalWeight;}public static void main(String[] args){In in new In(args[0]);myEdgeWeightedGraph G new myEdgeWeightedGraph(in);myPrimMST mst new myPrimMST(G);for(myEdge e:mst.edges())StdOut.println(e);StdOut.printf(%.5f\n, mst.weight());}
}代码详解
类定义和成员变量
java复制代码
public class myPrimMST {private myEdge[] edgeTo; // 记录最小生成树的边private double[] distTo; // 记录从树到该顶点的最小权重边private boolean[] marked; // 记录顶点是否在树中private myIndexMinPQDouble pq; // 索引优先队列帮助找到最小权重的边private double totalWeight; // 最小生成树的总权重
edgeTo存储每个顶点的连接边形成MST。distTo存储到每个顶点的最小边权重。marked标记哪些顶点已经被包括在MST中。pq索引优先队列用于动态查找最小边。
构造函数
java复制代码
public myPrimMST(myEdgeWeightedGraph G) {edgeTo new myEdge[G.V()];distTo new double[G.V()];marked new boolean[G.V()];pq new myIndexMinPQ(G.V());for(int v0; vG.V(); v)distTo[v] Double.POSITIVE_INFINITY;distTo[0] 0.0;pq.insert(0, 0.0);while(!pq.isEmpty())visit(G, pq.delMin());
}
初始化edgeTo、distTo、marked 和 pq。设置初始顶点的距离为 0 并将其插入优先队列。while 循环每次从优先队列中删除权重最小的顶点并调用 visit 方法处理该顶点。
visit方法
java复制代码
private void visit(myEdgeWeightedGraph G, int v) {marked[v] true;for(myEdge e: G.adj(v)) {int w e.other(v);if(marked[w]) continue;if(e.weight() distTo[w]) {edgeTo[w] e;distTo[w] e.weight();if(pq.contains(w)) pq.change(w, distTo[w]);else pq.insert(w, distTo[w]);}}
}
visit 方法标记顶点 v 为已访问。遍历所有与 v 连接的边并检查另一端顶点 w 是否已在MST中。如果找到更小的连接权重边则更新 edgeTo 和 distTo并在优先队列中更新或插入 w。
edges方法和weight方法
java复制代码
public IterablemyEdge edges() {myBagmyEdge mst new myBag();for(int v1; vedgeTo.length; v)mst.add(edgeTo[v]);return mst;
}public double weight() {totalWeight 0.00;for(myEdge e : edges())totalWeight e.weight();return totalWeight;
}
edges() 方法返回MST中的所有边。weight() 方法计算并返回MST的总权重。
main方法
java复制代码
public static void main(String[] args) {In in new In(args[0]);myEdgeWeightedGraph G new myEdgeWeightedGraph(in);myPrimMST mst new myPrimMST(G);for(myEdge e : mst.edges())StdOut.println(e);StdOut.printf(%.5f\n, mst.weight());
}
从文件中读取图数据并构建 myEdgeWeightedGraph 对象 G。使用 myPrimMST 类计算最小生成树 mst。打印最小生成树的所有边和总权重。
总结
Prim算法通过逐步构建最小生成树并利用优先队列来高效地选择最小权重的边。在这段代码中myPrimMST 类实现了Prim算法通过维护一个最小优先队列来管理尚未包括在MST中的顶点从而动态调整生成树并计算其总权重。
实验步骤
C:\Users\xyz\IdeaProjects\algrithoms\srcjavac myPrimMST.java
C:\Users\xyz\IdeaProjects\algrithoms\srcjava myPrimMST data\tinyEWD.txt
2-7 0.34
6-2 0.40
7-5 0.28
5-4 0.35
1-3 0.29
0-2 0.26
5-1 0.32
2.24000
