算法描述

在普利姆算法的lazy实现中，参考：普利姆算法的lazy实现

我们现在来考虑这样一个问题：

我们将所有的边都加入了优先队列，但事实上，我们真的需要所有的边吗？

我们再回到普利姆算法的lazy实现，看一下这个问题：



当顺着顶点0的邻接表考察顶点7时，边7-2和边7-1被加入了优先队列Q.

然而，当我们开始对顶点2进行考察时：

边2-3是最轻边，我们显然不需要对边7-2和边7-1进行再次考察.

但是，由于边7-2和边7-1在对顶点2进行考察之前已经加入了优先队列Q，似乎我们对之前发生的事无可奈何，也必须让优先队列维护着这些不再候选的废边，从而加重了优先队列的负担，影响了效率.

结果是否真的如此？

如果我们仔细思考，会注意到我们可以采取这样的一个技巧去防止将废边加入优先队列：

我们关注的只是当前能看到的最轻边，所以边7-2和边7-1对我们来说只有这样的意义：

边7-2：到顶点2的距离是x;

边7-1：到顶点2的距离是y;

边3-2：到顶点2的距离是z.

而z > x且z >y.

所以我们既然无法避免在先于顶点2之前就将边7-2和边7-1当做废边（贪心算法），所以我们可以

采取更新的方式来在优先队列Q中维护到某个顶点的最短距离.

换句话说，我们对某个顶点，只在Q中维护一条边，就是当前已知连着它的最轻边.

由此，我们避免了将所有的边都加入优先队列Q，从而使得最差情况下Q的操作与图的顶点数V 成线性渐进：O(V ).

但一般的优先队列只提供了入队（enqueue）和出队（dequeue）操作，要更新到某个顶点的最短距离，我们需要高效地在优先队列中访问这个顶点.

那么按照一般优先队列的方式，比如jdk中的优先队列，它会是这样：

    private int indexOf(Object o) {

        if (o != null) {

            for (int i = 0; i < size; i++)

                if (o.equals(queue[i]))

                    return i;

        }

        return -1;

    }

这虽然可以帮助我们在队列中找到元素，但这显然不高效.

有没有一种办法可以按常量时间来找到所需元素？

答案是：索引（index）,由此：

我们需要一个对顶点在队列中的索引.

这可以保证我们以常量的时间在队列中找到顶点.

关于索引式优先队列及实现可以参考：带索引的优先队列

实现分析

万事具备，那么我们对某顶点的邻接点（或邻接的边）的遍历和处理就会是这样：

    private void search(int src) {

        IndexPriorityQueue<Double> q = indexCrossingEdges;

        visited[src] = true;

        //遍历邻接的边

        for(Edge edge:g.vertices()[src].Adj) {

            WeightedEdge we = (WeightedEdge)edge;

            int to = we.to;

            if(visited[to])

                continue;

            //到顶点to的距离可以改善了

            if(we.weight < distanceTo[to]) {

                distanceTo[to] = we.weight;

                lastEdgeTo[to] = we;

                if(q.contains(to)) {

                    //我们在队列中只维护一条到某个顶点的距离

                    //在我们可以改善到这个顶点的距离是，我们更新它

                    q.decreaseKey(to, distanceTo[to]);

                }else {

                    q.offer(to, distanceTo[to]);

                }

            }

        }

    }

}

算法一开始的时候，我们从源点v出发，将其加入队列Q，然后开始进行mst的建立工作：

    private void mst(int v) {

        IndexPriorityQueue<Double> q = indexCrossingEdges;

        distanceTo[v] = 0.0d;

        q.offer(v, distanceTo[v]);

        while (!q.isEmpty()) {

            int src = q.poll();

            search(src);

        }

    }

完整实现

普利姆算法的完整eager实现如下,其中的一些类和字段不明白的

请参考：普利姆算法的lazy实现

/**

 * Created by 浩然 on 4/21/15.

 */

public class EagerPrim extends LazyPrim {

    protected  WeightedEdge[] lastEdgeTo;

    /**

     * 索引式优先队列，用于维护crossing edges

     * 用于在eager普利姆算法中高效返回最轻边并支持decrease-key操作

     */

    protected IndexPriorityQueue<Double> indexCrossingEdges;

    public EagerPrim(WeightedUndirectedGraph g) {

        super(g);

    }

    @Override

    protected void resetMemo() {

        super.resetMemo();

        lastEdgeTo = new WeightedEdge[g.vertexCount()];

        //重置优先队列

        indexCrossingEdges = new IndexPriorityQueue<>();

    }

    private void setupMST() {

        for (int v = 0; v < lastEdgeTo.length; v++) {

            WeightedEdge we = lastEdgeTo[v];

            if (we != null) {

                mst.offer(we);

                mstWeight += we.weight;

            }

        }

    }

    /**

     * eager-prim算法，时间复杂度为最差O(ElogV)

     */

    @Override

    public void performMST() {

        resetMemo();

        //对图中的所有顶点进行遍历，可以找出MSF（最小生成森林）

        //这里我们假设图是连通的，所以可以找出一棵MST

        mst(0);

        setupMST();

    }

    private void mst(int v) {

        IndexPriorityQueue<Double> q = indexCrossingEdges;

        distanceTo[v] = 0.0d;

        q.offer(v, distanceTo[v]);

        while (!q.isEmpty()) {

            int src = q.poll();

            search(src);

        }

    }

    private void search(int src) {

        IndexPriorityQueue<Double> q = indexCrossingEdges;

        visited[src] = true;

        //遍历邻接的边

        for(Edge edge:g.vertices()[src].Adj) {

            WeightedEdge we = (WeightedEdge)edge;

            int to = we.to;

            if(visited[to])

                continue;

            //到顶点to的距离可以改善了

            if(we.weight < distanceTo[to]) {

                distanceTo[to] = we.weight;

                lastEdgeTo[to] = we;

                if(q.contains(to)) {

                    //我们在队列中只维护一条到某个顶点的距离

                    //在我们可以改善到这个顶点的距离是，我们更新它

                    q.decreaseKey(to, distanceTo[to]);

                }else {

                    q.offer(to, distanceTo[to]);

                }

            }

        }

    }

}

时间复杂度

由于避免了对废弃边的访问，所以在优先队列中最多维护V条记录.

优先队列的操作耗时O(logV ).

遍历所有边的操作耗时O(E ),则整体耗时O(ElogV)