/**
 * Company
 * Copyright (C) 2014-2017 All Rights Reserved.
 */
package com.cwenao.datastructure.graph;

import com.cwenao.datastructure.queue.IndexMinPQ;

/**
 * 图G，顶点集合为U，设集合空集合V，边集合UV，
 * 1.从U中选取顶点a为起始点，将a加入V，将a从U中删除
 * 2.以a为起点在集合UV中找到一点b使得a到b的权值最小
 * 3.将b加入V，将b从U中删除
 * 4.重复2、3直到U为空
 * @author cwenao
 * @version $Id PrimMST.java, v 0.1 2017-09-10 17:36 cwenao Exp $$
 */
public class PrimMST {
    private Edge[] edgeTo;
    private double[] distTo;
    private boolean[] marked;
    private IndexMinPQ<Double> pq;


    private void scan(EdgeWeightGraph edgeWeightGraph) {

    }

}

@@ -152,16 +152,70 @@
 MinPQ;%0A%0A
+import java.util.ArrayDeque;%0Aimport java.util.Queue;%0A%0A
 /**%0A * %E5%9B%BE
@@ -581,60 +581,1558 @@
    p
-rivate void scan(EdgeWeightGraph edgeWeightGraph) %7B%0A
+ublic PrimMST(EdgeWeightGraph graph) %7B%0A        edgeTo = new Edge%5Bgraph.getV()%5D;%0A        distTo = new double%5Bgraph.getV()%5D;%0A        marked = new boolean%5Bgraph.getV()%5D;%0A%0A        pq = new IndexMinPQ%3C%3E(graph.getV());%0A%0A        for (int v = 0; v %3C graph.getV(); v++) %7B%0A            distTo%5Bv%5D = Double.POSITIVE_INFINITY;%0A        %7D%0A        for (int v = 0; v %3C graph.getV(); v++) %7B%0A            if (!marked%5Bv%5D) %7B%0A                scan(graph, v);%0A            %7D%0A        %7D%0A    %7D%0A%0A    private void prim(EdgeWeightGraph graph, int s) %7B%0A        distTo%5Bs%5D = 0.0;%0A        pq.insert(s, distTo%5Bs%5D);%0A        while (!pq.isEmpty()) %7B%0A            int v = pq.delMin();%0A            scan(graph, v);%0A        %7D%0A    %7D%0A%0A    private void scan(EdgeWeightGraph edgeWeightGraph, int v) %7B%0A        marked%5Bv%5D = true;%0A        for (Edge edge : edgeWeightGraph.adj(v)) %7B%0A            int w = edge.getOther(v);%0A            if (marked%5Bw%5D) %7B%0A                continue;%0A            %7D%0A            if (edge.getWeight() %3C distTo%5Bw%5D) %7B%0A                distTo%5Bw%5D = edge.getWeight();%0A                edgeTo%5Bw%5D = edge;%0A                if (pq.contains(w)) %7B%0A                    pq.decreaseKey(w, distTo%5Bw%5D);%0A                %7D else %7B%0A                    pq.insert(w, distTo%5Bw%5D);%0A                %7D%0A            %7D%0A        %7D%0A    %7D%0A%0A    public Iterable%3CEdge%3E edges() %7B%0A        Queue%3CEdge%3E edges = new ArrayDeque%3C%3E();%0A%0A        for (int v = 0; v %3C edgeTo.length; v++) %7B%0A            Edge edge = edgeTo%5Bv%5D;%0A            if (edge!=null) %7B%0A                edges.offer(edge);%0A            %7D%0A        %7D%0A        return edges;
 %0A   

update the primMST