最小生成树-普利姆算法lazy实现

时间:2021-02-28 11:39:52

算法描述

lazy普利姆算法的步骤

1.从源点s出发,遍历它的邻接表s.Adj,将所有邻接的边(crossing edges)加入优先队列Q;
2.从Q出队最轻边,将此边加入MST.
3.考察此边的两个端点,对两个端点重复第1步.

示例

从顶点0开始,遍历它的邻接表:边0-7、0-2、0-4、0-6会被加入优先队列Q.
顶点0的邻接表搜索完毕后,边0-7是最轻边,所以它会出队,并加入MST.
如下图:
最小生成树-普利姆算法lazy实现
边0-7出队后,开始考察边的两个端点:

顶点0已经访问过了,跳过;
顶点7还未探索,开始探索顶点7.对7的邻接表进行访问和第一步类似.
我们找到最轻边7-1并加入MST

如下图:

最小生成树-普利姆算法lazy实现

对每条边重复,当所有边都考察完毕,我们就得到了最小生成树,如下图:
最小生成树-普利姆算法lazy实现

时间复杂度

扫描所有边会耗时O(E ).
由于所有的边都会入队,优先队列调整的操作耗时O(logE ).
那lazy方式最差就是O(ElogE ).
其中E 是图的边数.

算法实现

算法的第一步,将源点s所有的邻接的边加入Q,如下:

    /** * 找出从源点出发的所有的crossing edges,并用一个优先队列维护他们 * * 原理: * 将对未访问的邻接点进行遍历当作一次切断(graph-cut),则源点和邻接点间的边就是crossing edge * 根据贪心策略求MST的要求,要加入的边必须是最轻边(权重最小的边), * 故而将crossing edges加入优先队列,这样便可用O(logN)的时间找出最小权重边 * * @param src 源点 */
    private void search(int src) {
        visited[src] = true;
        for(Edge e : g.vertices()[src].Adj) {
            WeightedEdge we = (WeightedEdge)e;
            if(!visited[we.to])
                crossingEdges.offer(we);
        }
    }

算法的第二步和第三步如下:

    /** * lazy普利姆算法中,从一个源点出发 * 1:通过对源点的所有邻接点进行遍历的方式找出所有crossing edges * 2:将crossing edges中最轻的(拥有最小的权重)边加入MST * 3:将最轻边的另一个顶点作为源点,重复1-2步. * * * @param src 源点 */
    private void mst(int src) {
        search(src);
        while (!crossingEdges.isEmpty()) {
            WeightedEdge we = crossingEdges.poll();
            //懒惰方式处理不再候选的边
            if(visited[we.src] && visited[we.to])
                continue;
            //加入最小生成树
            mst.offer(we);
            //累积mst的权重
            mstWeight += we.weight;
            //向src的邻接点方向搜索
            if(!visited[we.src])
                search(we.src);
            //向to的邻接点方向搜索
            if(!visited[we.to])
                search(we.to);
        }
    }

其中,维护所有crossing edge的,是一个优先队列:

    /** * 优先队列,用于维护crossing edges * 高效返回最轻边 */
    protected PriorityQueue<WeightedEdge> crossingEdges;

带权边的定义很简单,像下面这样:

import java.util.Comparator;

/** * Created by 浩然 on 4/19/15. * 带权边 */
public class WeightedEdge extends Edge implements Comparable<WeightedEdge> {
    /** * 边的权重 */
    public Double weight;

    /** * 边的源点 */
    public int src;

    /** * 构造一条带权边 *@param src 源点 * @param other 目标点 * @param weight 权重 */
    public WeightedEdge(int src,int other, Double weight) {
        super(other);
        this.src = src;
        this.weight = weight;
    }

    /** * 比较两条边的大小,这里作升序 * @param to 被比较边 * @return 如果权重比被比较的边小则返回-1,如果大于则返回1,相等则返回0 */
    @Override
    public int compareTo(WeightedEdge to) {
        if(this.weight < to.weight)
            return -1;
        else if(this.weight > to.weight)
            return 1;
        return 0;
    }
}

public class Edge {
    public int to;
    public Edge(int key) {
        this.to = key;
    }
}

而顶点的定义更简单,如下:

public class Vertex {
    /** * 邻接表 */
    public LinkedList<Edge> Adj;
}

完整代码

public class LazyPrim extends Algorithm {

    /** * 优先队列,用于维护crossing edges * 高效返回最轻边 */
    protected PriorityQueue<WeightedEdge> crossingEdges;

    public LazyPrim(WeightedUndirectedGraph g) {
        super(g);
    }

    /** * lazy普利姆算法求MST或MSF(Minimum Spanning Forest最小生成森林) * * 算法复杂度:最差O(ElogE) */
    public void performMST() {
        resetMemo();
        //对图中的所有顶点进行遍历,找出MST或MSF
        for(int  i = 0; i < g.vertexCount();i++){
            if(!visited[i]) {
                mst(i);
            }
        }
    }

    /** * lazy普利姆算法中,从一个源点出发 * 1:通过对源点的所有邻接点进行遍历的方式找出所有crossing edges * 2:将crossing edges中最轻的(拥有最小的权重)边加入MST * 3:将最轻边的另一个顶点作为源点,重复1-2步. * * * @param src 源点 */
    private void mst(int src) {
        search(src);
        while (!crossingEdges.isEmpty()) {
            WeightedEdge we = crossingEdges.poll();
            //懒惰方式处理不再候选的边
            if(visited[we.src] && visited[we.to])
                continue;
            //加入最小生成树
            mst.offer(we);
            //累积mst的权重
            mstWeight += we.weight;
            //向src的邻接点方向搜索
            if(!visited[we.src])
                search(we.src);
            //向to的邻接点方向搜索
            if(!visited[we.to])
                search(we.to);
        }
    }

    /** * 找出从源点出发的所有的crossing edges,并用一个优先队列维护他们 * * 原理: * 将对未访问的邻接点进行遍历当作一次切断(graph-cut),则源点和邻接点间的边就是crossing edge * 根据贪心策略求MST的要求,要加入的边必须是最轻边(权重最小的边), * 故而将crossing edges加入优先队列,这样便可用O(logN)的时间找出最小权重边 * * @param src 源点 */
    private void search(int src) {
        visited[src] = true;
        for(Edge e : g.vertices()[src].Adj) {
            WeightedEdge we = (WeightedEdge)e;
            if(!visited[we.to])
                crossingEdges.offer(we);
        }
    }

    @Override
    protected void resetMemo() {
        super.resetMemo();
        //重置优先队列
        crossingEdges = new PriorityQueue<>();
    }
}