▶ 书中第四章部分程序，包括在加上自己补充的代码，两种 Prim 算法求最小生成树
● 简单 Prim 算法求最小生成树
package package01; import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.Edge;
import edu.princeton.cs.algs4.EdgeWeightedGraph;
import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.MinPQ; public class class01
{
private static final double FLOATING_POINT_EPSILON = 1E-12; private boolean[] marked; // 顶点是否在生成树中
private double weight; // 生成树的权值和
private Queue<Edge> mst; // 生成树包含的边
private MinPQ<Edge> pq; // 搜索队列 public class01(EdgeWeightedGraph G)
{
marked = new boolean[G.V()];
mst = new Queue<Edge>();
pq = new MinPQ<Edge>();
for (int v = 0; v < G.V(); v++) // 对每个没有遍历的节点都使用 prim
{
if (!marked[v])
prim(G, v);
}
} private void prim(EdgeWeightedGraph G, int s)
{
for (scan(G, s); !pq.isEmpty();)
{
Edge e = pq.delMin(); // 取出权值最小的边
int v = e.either(), w = e.other(v);
if (marked[v] && marked[w]) // 若该边两端都遍历过，不要（由于 scan，v 与 w 之一肯定被遍历过）
continue;
mst.enqueue(e); // 将权值最小的边加入生成树
weight += e.weight(); // 更新权值和
if (!marked[v]) // 从新边的新顶点继续收集新的边
scan(G, v);
if (!marked[w])
scan(G, w);
}
} private void scan(EdgeWeightedGraph G, int v) // 将一端为 v、另一端没有遍历过的边放入队列中
{
marked[v] = true;
for (Edge e : G.adj(v))
{
if (!marked[e.other(v)])
pq.insert(e);
}
} public Iterable<Edge> edges()
{
return mst;
} public double weight()
{
return weight;
} public static void main(String[] args)
{
In in = new In(args[0]);
EdgeWeightedGraph G = new EdgeWeightedGraph(in);
class01 mst = new class01(G);
for (Edge e : mst.edges())
StdOut.println(e);
StdOut.printf("%.5f\n", mst.weight());
}
}
● 改进，使用索引最小优先队列来建立搜索队列，记录（起点到）每个顶点的距离来判断是否将新边加入生成树
package package01; import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.Edge;
import edu.princeton.cs.algs4.EdgeWeightedGraph;
import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.IndexMinPQ; public class class01
{
private static final double FLOATING_POINT_EPSILON = 1E-12; private boolean[] marked;
private Edge[] edgeTo; // 除了搜索起始顶点，新加入每条边对应一个顶点，顶点 v 对应的边是 edgeTo[v]
private double[] distTo; // 生成树到每个顶点的距离，用于衡量新边是否值得加入生成树
private IndexMinPQ<Double> pq;// 搜索队列 public class01(EdgeWeightedGraph G)
{
marked = new boolean[G.V()];
edgeTo = new Edge[G.V()];
distTo = new double[G.V()];
pq = new IndexMinPQ<Double>(G.V());
for (int v = 0; v < G.V(); v++)
distTo[v] = Double.POSITIVE_INFINITY;
for (int v = 0; v < G.V(); v++)
{
if (!marked[v])
prim(G, v);
}
} private void prim(EdgeWeightedGraph G, int s)
{
distTo[s] = 0.0; // 搜索起点对应的距离为 0
for (pq.insert(s, distTo[s]); !pq.isEmpty();)
{
int v = pq.delMin(); // 每次取距离最小的顶点来开花（防止同一个顶点可以有对多条边连到树上）
scan(G, v); // 注意 scan 只负责在给定的顶点上开花，不负责递归
}
} private void scan(EdgeWeightedGraph G, int v)
{
marked[v] = true;
for (Edge e : G.adj(v))
{
int w = e.other(v);
if (marked[w]) // 边 v-w 两端都被遍历过，在队列中
continue;
if (e.weight() < distTo[w]) // 边 v-w 的权值小于顶点 w 的距离，说明加入该条边后生成树的总权值会下降
{
distTo[w] = e.weight(); // 加入边 v-w，更新 distTo 和 edgeTo
edgeTo[w] = e;
if (pq.contains(w)) // 搜若索队列中已经存在 w 则更新其 distTo（键值），不存在则将 w 加入
pq.decreaseKey(w, distTo[w]);
else
pq.insert(w, distTo[w]);
}
}
} public Iterable<Edge> edges()
{
Queue<Edge> mst = new Queue<Edge>();
for (int v = 0; v < edgeTo.length; v++)// 遍历边列表，把每个顶点对应的边加入队列中
{
Edge e = edgeTo[v];
if (e != null)
mst.enqueue(e);
}
return mst;
} public double weight()
{
double weight = 0.0;
for (Edge e : edges())
weight += e.weight();
return weight;
} public static void main(String[] args)
{
In in = new In(args[0]);
EdgeWeightedGraph G = new EdgeWeightedGraph(in);
class01 mst = new class01(G);
for (Edge e : mst.edges())
StdOut.println(e);
StdOut.printf("%.5f\n", mst.weight());
}
}