加权无向图----Prim算法实现最小生成树

SuperHeroes

发布于 2018-05-30 09:48:26

1.6K00

代码可运行

文章被收录于专栏：云霄雨霁云霄雨霁

运行总次数：0

代码可运行

上一篇：加权无向图的实现

加权无向图----Kruskal算法实现最小生成树

图的生成树是它的一棵含有其所有顶点的无环连通子图，加权图的最小生成树（MST）是它的一棵权值最小的生成树。

切分：图的一种切分是将图的所有顶点分为两个非空且不重合的两个集合。横切边是一条连接两个属于不同集合的顶点的边。

切分定理：在一幅加权图中，给定任意的切分，它横切边中权重最小者必然属于图的最小生成树。

切分定理是解决最小生成树问题的所有算法的基础。

Prim算法能够得到任意加权连通无向图的最小生成树。

数据结构设计：

采用一个布尔数组marked[]来记录顶点是否在树中，如果顶点v在，则markedv为true。
使用一条优先权队列来保存所有的横切边。
使用一条队列保存最小生成树的边。

算法：使用一个最小优先权队列保存横切边集合，每次新加进来一个结点，就将和该结点关联的所有边添加进最小优先权队列；生成最小树时，从横切边集合中取出最小边，判断是否和目前的树产生环，如果产生环，则舍弃该边；否则将该边加入最小生成树队列。

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;
    }
}

Prim算法的延时实现计算一个含V个顶点和E条边的连通加权无向图的最小生成树所需空间与E成正比，所需时间与ElogE成正比（最坏情况）。

Prim的即时实现：

要改进LazyPrimMST,可以尝试从优先队列中删除用不到的边。关键在于，我们关注的只是连接树顶点和非树顶点中权重最小的边。当我们将顶点v加入树中，只可能使非树顶点w到最小生成树更近了。简而言之，我们不必保存所有从w到树顶点的边，只需保存最小的那条即可。在v添加进树中时遍历v的邻接表检查是否需要更新权重最小的边。

引进两个顶点索引数组edgeTo[]和distTo[],它们有如下性质：

如果顶点v不在树中但至少含有一条边和树相连，那么edgeTov将是v和树连接的最短的边，distTov为这条边的权重。
所有这类v都保存在一条索引优先队列中，索引v关联的值是edgeTov的边的权重。

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]);
            }
        }
    }
}