加权无向图----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);//从顶点0 开始
        while(!pq.isEmpty()) {//构造最小生成树
            Edge e = pq.delMin();
            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[w])    visit(G,w);
        }
    }
    private void visit(EdgeWeightedGraph G,int 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 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());
        }
	
    public 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;//最佳边Edge变为e
                distTo[w] = e.weight();//更新distTo[]
                if(pq.contains(w))    pq.change(w, distTo[w]);
                else pq.insert(w, distTo[w]);
            }
        }
    }
}