** Prim算法 **
Prim算法的每一步都會為一棵生長中的樹添加一條邊够庙。一開始這棵樹只有一個頂點，然后會向它添加V-1條邊笙僚，每次總是將下一條連接樹中的頂點與不在樹中的頂點且權(quán)重最小的邊加入樹中。
1.Prim算法的延時實現(xiàn)：
新加入樹中的頂點與其他已經(jīng)在樹中頂點的所有邊都會失效（這樣的邊不可能是橫切邊），Prim的延時算法會把這些邊先保留桥滨，等到要刪除的時候再檢查有效性。
public class LazyPrimMST{
private boolean[] marked; //最小生成樹的頂點
private Queue<Edge> mst; //最小生成樹的邊
private MinPQ<Edge> pq; //橫切邊（包括已經(jīng)失效的邊）
public LazyPrimMST(EdgeWeightedGraph G){
pq = new MinPQ<Edge>();
marked = new boolean[G.V()];
mst = new Queue<Edge>();
visit(G, 0); //假設(shè)G是連通的
while(!pq.isEmpty()){
Edge e = pq.delMin(); //從pq中得到權(quán)重最小的邊
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){
//標(biāo)記頂點v并將所有連接v和未標(biāo)記頂點的邊加入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算法的即時實現(xiàn)
要改進之前的算法弛车，我們可以嘗試從優(yōu)先隊列中刪除失效的邊齐媒，這樣優(yōu)先隊列就只含有樹頂點和非樹頂點之間的橫切邊。除此之外纷跛，對于每個非樹頂點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); //用頂點和權(quán)重0初始化pq
while(!pq.isEmpty())
visit(G, pq.delMin()); //將最近的頂點添加到樹中
}
private void visit(EdgeWeightedGraph G, int v){
//將頂點添加到樹中，更新數(shù)據(jù)
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算法的主要思想是按照邊的權(quán)重排序（從小到大）處理他們，將邊加入最小生成樹中韧骗，加入的邊不會與已加入的邊構(gòu)成環(huán)扎附，直到樹中含有V-1條邊為止。
我們將會使用一條優(yōu)先隊列來將邊按照權(quán)重排序，用一個union-find數(shù)據(jù)結(jié)構(gòu)來識別會形成環(huán)的邊，以及一條隊列來保存最小生成樹的所有邊。
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中得到權(quán)重最小的邊和它的頂點
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()
}