【算法基础实验】图论-最小生成树-Prim的即时实现

理论知识

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 myIndexMinPQ<Double> 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 v=0;v<G.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 Iterable<myEdge> edges(){myBag<myEdge> mst = new myBag<myEdge>();for(int v=1;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 myIndexMinPQ<Double> 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 v=0; v<G.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 Iterable<myEdge> edges() {myBag<myEdge> mst = new myBag<>();for(int v=1; v<edgeTo.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\src>javac myPrimMST.java 
C:\Users\xyz\IdeaProjects\algrithoms\src>java 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