** Prim算法 **
Prim算法的每一步都会为一棵生长中的树添加一条边。一开始这棵树只有一个顶点，然后会向它添加V-1条边，每次总是将下一条连接树中的顶点与不在树中的顶点且权重最小的边加入树中。
1.Prim算法的延时实现：
新加入树中的顶点与其他已经在树中顶点的所有边都会失效（这样的边不可能是横切边），Prim的延时算法会把这些边先保留，等到要删除的时候再检查有效性。
public class LazyPrimMST{
private boolean[] marked; //最小生成树的顶点
private Queue<Edge> mst; //最小生成树的边
private MinPQ<Edge> pq; //横切边（包括已经失效的边）
public LazyPrimMST(EdgeWeightedGraph G){
pq = new MinPQ<Edge>();
marked = new boolean[G.V()];
mst = new Queue<Edge>();
visit(G, 0); //假设G是连通的
while(!pq.isEmpty()){
Edge e = pq.delMin(); //从pq中得到权重最小的边
int v = e.either(), w = e.other(v);
if ( marked[v] && marked[w]) continue; //跳过失效的边
mst.enqueue(e); //将边添加到树中
if(!marked[v]) visit(G,v); //将顶点添加到树中
if(!marked[v]) visit(G,w);
}
}
private void visit(EdgeWeightedGraph G, int v){
//标记顶点v并将所有连接v和未标记顶点的边加入pq
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()
}
2.Prim算法的即时实现
要改进之前的算法，我们可以尝试从优先队列中删除失效的边，这样优先队列就只含有树顶点和非树顶点之间的横切边。除此之外，对于每个非树顶点w，在把新的树顶点v添加到树中时，w到最小生成树的距离可能更近了。我们不需要保存所有从w到最小生成树的边，而只需要其中最小的那一条——在将v添加到树中后，遍历v邻接链表即可。
public class PrimMST{
private Edge[] edgeTo; //距离树最近的边
private double[] distTo; //distTo[w] = edgeTo[w].weight()
private boolean[] marked; //如果v在树中则为true
private IndexMinPQ<Double> pq; //有效的横切边
public PrimMST(EdgeWeightedGraph G){
edgeTo = new Edge[G.V()];
distTo = new double[G.V()];
marked = new boolean[G.V()];
for(int v = 0; v<G.V(); v++){
distTo[v] = Double.POSITIVE_INFINITY;
pq = new IndexMinPQ<Double>(G.V());
distTo[0] = 0.0;
pq.insert(0,0.0); //用顶点和权重0初始化pq
while(!pq.isEmpty())
visit(G, pq.delMin()); //将最近的顶点添加到树中
}
private void visit(EdgeWeightedGraph G, int v){
//将顶点添加到树中，更新数据
marked[v] = true;
for(Edge e:G.adj(v)){
int w = e.other(v);
if(marked[w]) continue; //v-w失效
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<Edge> edges()
public double weight()
}
** Kruskal算法 **
Kruskal算法的主要思想是按照边的权重排序（从小到大）处理他们，将边加入最小生成树中，加入的边不会与已加入的边构成环，直到树中含有V-1条边为止。
我们将会使用一条优先队列来将边按照权重排序，用一个union-find数据结构来识别会形成环的边，以及一条队列来保存最小生成树的所有边。
public class KruskalMST{
private Queue<Edge> mst;
public KruskalMST(EdgeWeightedGraph G){
mst = new Queue<Edge>();
MinPQ<Edge> pq = new MinPQ<Edge>();
for( Edge e:G.edges()) pq.insert(e);
UF uf = new UF(G.V());
while( !pq.isEmpty() && mst.size() < G.V() -1){
Edge e = pq.delMin(); //从pq中得到权重最小的边和它的顶点
int v = e.either(), w = e.other();
if(uf.connected(v, w)) continue; //忽略失效的边
uf.union(v,w); //合并分量
mst.enqueue(e); //将得到的边添加到最小生成树中
}
}
public Iterable<Edge> edges()
{ return mst; }
public double weight()
}