首页 > 代码库 > 算法8-5:Prim算法

算法8-5:Prim算法

Prim算法用于计算最小生成树。Prim算法分为两种,一种是懒汉式,一种是饿汉式。


懒汉式Prim


懒汉式Prim算法步骤如下:

  1. 首先将顶点0加入到MST中

  2. 从MST与未访问顶点之间边中选出最短的边,在满足MST的前提下,将这条边加入到MST


代码

import java.util.LinkedList;
import java.util.List;

public class LazyPrim {
    private MinPQ<Edge> pq = new MinPQ<Edge>();
    private List<Edge> mst = new LinkedList<Edge>();
    private boolean[] visited;
 
    public LazyPrim(EdgeWeightedGraph G) {
        visited = new boolean[G.V()];
 
        // 将第一个顶点加入到MST中
        visit(G, 0);
 
        // 依次选出最短的边
        while (!pq.isEmpty()) {
            Edge minEdge = pq.popMin();
            int v = minEdge.either();
            int w = minEdge.other(v);
 
            // 忽略造成回路的边
            if (visited[v] && visited[w]) {
                continue;
            }
 
            // 访问该点,将该边加入到MST
            if (!visited[v]) visit(G, v);
            else visit(G, w);
            mst.add(minEdge);
        }
    }
 
    public Iterable<Edge> edges() {
        return mst;
    }
 
    public double weight() {
        double result = 0;
        for (Edge e : edges()) {
            result += e.weight();
        }
        return result;
    }
 
    private void visit(EdgeWeightedGraph G, int v) {
        // 将该点标记为已访问
        visited[v] = true;
 
        // 将该点伸展的边加入到优先级队列中
        for(Edge e:G.adj(v)){
            int w = e.other(v);
            if(!visited[w]) {
                pq.add(e);
            }
        }
    }
}


复杂度


懒汉式Prim算法在最坏的情况下时间复杂度为E logE,空间复杂度是E。


饿汉式Prim


饿汉式Prim的基本思想就是给每个尚未加入到MST的顶点都只记录一个最短的,连接MST的边。因为只记录一个边,所以计算量稍微减少了一些。


Prim算法中需要用到优先级队列。根据优先级队列的实现方式,算法复杂度也有所差异。如果用二叉堆方式进行时间,那么它的时间复杂度就是E logV,如果用数组方式实现,那么这种算法的复杂度就是V^2。


对于边数非常多的图,使用数组方式时间优先级队列可以提高算法性能,对于边数较少的图,使用二叉堆方式实现优先级队列可以获得较高的性能。