算法-最小生成树
标签:算法

最小生成树(Minimum Span Tree)

最小生成树问题是找V-1条边来连接V个顶点使得总权值最小,适合解决电缆布线设计,网络设计,电路设计等问题。针对带权无向图,连通图。

1. 构造有权图

2. 切分定理(Cut Property)

切分定理:把图中的节点分为两部分,成为一个切分(Cut),如果一个边的两个端点,属于切分不同的两边,这个边称为横切边(Crossing Edge)。即给定任意切分,横切边中权值最小的边必然属于最小生成树(可以通过反证法证明)

3. Lazy Prim

我们先以0开始划分切分,把0周围的边都加入到最小堆中,然后从0的边中选出一个最小的0-7:0.16,然后把7周围的边加入到最小堆中,选出最小的1-7:0.19,把1周围边加入,选最小的是0-2:0.26,把2周围的边加入(此时2-1,2-7前面已经加入了,此时又重新加入了一遍,导致重复,故叫lazy),选2-3:0.17,再把3周围加入,此时最小是7-5:0.28,此时堆中最小的是1-3:0.29,但1-3已经在同一个切分,故删除1-3这条边,在删除1-5,2-7,加入5-4:0.35,删除1-2,删除4-7删除4-0,加入2-6:0.40,删除3-6,0-6,4-6。

package com.liuyao.graph2.lazyprim;

import com.liuyao.graph2.Edge;
import com.liuyao.graph2.ReadWeightedGraph;
import com.liuyao.graph2.SparseWeightedGraph;
import com.liuyao.graph2.WeightedGraph;

import java.util.Vector;

/**
 * Created By liuyao on 2018/5/1 17:02.
 */
public class LazyPrimMST<Weight extends Number & Comparable> {
    private WeightedGraph<Weight> G;    // 图的引用
    private MinHeap<Edge<Weight>> pq;   // 最小堆, 算法辅助数据结构
    private boolean[] marked;           // 标记数组, 在算法运行过程中标记节点i是否被访问
    private Vector<Edge<Weight>> mst;   // 最小生成树所包含的所有边
    private Number mstWeight;           // 最小生成树的权值

    public LazyPrimMST(WeightedGraph<Weight> g) {
        G = g;
//        构造最小堆,个数为点的个数
        pq = new MinHeap<Edge<Weight>>(G.E());
//        设置每条边都没被访问过
        marked = new boolean[G.V()];
//        申请一个Vector来存放最短路径的边
        mst = new Vector<Edge<Weight>>();

//        从0开始访问
        visit(0);
//        当最小堆不为空的,继续
        while (!pq.isEmpty()) {
//            取得当前最小堆中最小的那条边
            Edge<Weight> e = pq.extractMin();
//            如果边的两个点的访问标记一样,说明在同一个切分中,继续找最小的
            if (marked[e.v()] == marked[e.w()]) {
                continue;
            }
//            否者加入到mst中
            mst.add(e);
//            看边的哪一个点没有被访问,就visit把它周围的边加入到最小堆中
            if (!marked[e.v()]) {
                visit(e.v());
            } else {
                visit(e.w());
            }
        }

//        最后求所有最短路径的权值总和
        mstWeight = mst.elementAt(0).wt();
        for (int i = 1; i < mst.size(); i++) {
            mstWeight = mstWeight.doubleValue() + mst.elementAt(i).wt().doubleValue();

        }
    }

    // 访问节点v
    private void visit(int v) {
        assert !marked[v];
        marked[v] = true;
        // 将和节点v相连接的所有未访问的边放入最小堆中
        for (Edge<Weight> e : G.adj(v)) {
            if (!marked[e.other(v)]) {
                pq.insert(e);
            }
        }
    }

    //    返回最小生成树的所有边
    Vector<Edge<Weight>> mstEdges() {
        return mst;
    }

    //    返回最小生成树的权值
    Number result() {
        return mstWeight;
    }

    public static void main(String[] args) {
        String filename = "testG1-2.txt";
        int V = 8;

        SparseWeightedGraph<Double> g = new SparseWeightedGraph<Double>(V, false);
        ReadWeightedGraph readGraph = new ReadWeightedGraph(g, filename);

        // Test Lazy Prim MST
        System.out.println("Test Lazy Prim MST:");
        LazyPrimMST<Double> lazyPrimMST = new LazyPrimMST<Double>(g);
        Vector<Edge<Double>> mst = lazyPrimMST.mstEdges();
        for (int i = 0; i < mst.size(); i++) {
            System.out.println(mst.elementAt(i));
        }
        System.out.println("The MST weight is: " + lazyPrimMST.result());

        System.out.println();
    }
}

最后结果和上面分析的一样:

Lazy Prim的时间复杂度为O(ElogE)

4. 优化的Prim

package com.liuyao.graph2.lazyprim;

import com.liuyao.graph2.Edge;
import com.liuyao.graph2.ReadWeightedGraph;
import com.liuyao.graph2.SparseWeightedGraph;
import com.liuyao.graph2.WeightedGraph;

import java.util.Vector;

/**
 * Created By liuyao on 2018/5/1 18:23.
 */
public class PrimMST<Weight extends Number & Comparable> {
    private WeightedGraph G;              // 图的引用
    private IndexMinHeap<Weight> ipq;     // 最小索引堆, 算法辅助数据结构
    private Edge<Weight>[] edgeTo;        // 访问的点所对应的边, 算法辅助数据结构
    private boolean[] marked;             // 标记数组, 在算法运行过程中标记节点i是否被访问
    private Vector<Edge<Weight>> mst;     // 最小生成树所包含的所有边
    private Number mstWeight;             // 最小生成树的权值

    // 构造函数, 使用Prim算法求图的最小生成树
    public PrimMST(WeightedGraph g) {
        assert (g.E() >= 1);
        G = g;
        ipq = new IndexMinHeap<>(G.V());

        marked = new boolean[G.V()];
        edgeTo = new Edge[G.V()];

        // 算法初始化
        for (int i = 0; i < G.V(); i++) {
            marked[i] = false;
            edgeTo[i] = null;
        }
        mst = new Vector<Edge<Weight>>();

        //Prim
        visit(0);
        while (!ipq.isEmpty()) {
            // 使用最小索引堆找出已经访问的边中权值最小的边
            // 最小索引堆中存储的是点的索引, 通过点的索引找到相对应的边
            int v = ipq.extractMinIndex();
//            要确保当前到v的边不为空
            assert (edgeTo[v] != null);
//            将这条边添加到最短路径的边里面
            mst.add(edgeTo[v]);
//            继续查找v的周围的边
            visit(v);
        }

        // 计算最小生成树的权值
        mstWeight = mst.elementAt(0).wt();
        for (int i = 1; i < mst.size(); i++) {
            mstWeight = mstWeight.doubleValue() + mst.elementAt(i).wt().doubleValue();
        }

    }

    public void visit(int v) {
        assert !marked[v];
//        设置已被标记
        marked[v] = true;

        for (Object item : G.adj(v)) {
            Edge<Weight> e = (Edge<Weight>) item;
//            w为边的另一个顶点
            int w = e.other(v);
//            检查该顶点是否已经被标记了
            if (!marked[w]) {
//                如果到改点的边为null
                if (edgeTo[w] == null) {
//                    则设置当前边到w
                    edgeTo[w] = e;
//                    插入索引堆,索引为w,值为边的权值
                    ipq.insert(w, e.wt());
                } else if (e.wt().compareTo(edgeTo[w].wt()) < 0) {  //如果新的权值小于原来到w的边的权值
//                    更新w的边
                    edgeTo[w] = e;
//                    改变w的的权值
                    ipq.change(w, e.wt());
                }
            }
        }
    }

    // 返回最小生成树的所有边
    Vector<Edge<Weight>> mstEdges() {
        return mst;
    }

    // 返回最小生成树的权值
    Number result() {
        return mstWeight;
    }

    // 测试 Prim
    public static void main(String[] args) {

        String filename = "testG1-2.txt";
        int V = 8;

        SparseWeightedGraph<Double> g = new SparseWeightedGraph<Double>(V, false);
        ReadWeightedGraph readGraph = new ReadWeightedGraph(g, filename);

        // Test Prim MST
        System.out.println("Test Prim MST:");
        PrimMST<Double> primMST = new PrimMST<Double>(g);
        Vector<Edge<Double>> mst = primMST.mstEdges();
        for (int i = 0; i < mst.size(); i++) {
            System.out.println(mst.elementAt(i));
        }
        System.out.println("The MST weight is: " + primMST.result());

        System.out.println();
    }

}

得到的结果跟上面一样:

Prim的时间复杂度为O(ElogV)

5. Kruskal 算法

package com.liuyao.graph2.Kruskal;

import com.liuyao.graph2.Edge;
import com.liuyao.graph2.ReadWeightedGraph;
import com.liuyao.graph2.SparseWeightedGraph;
import com.liuyao.graph2.WeightedGraph;

import java.util.Vector;

/**
 * Created By liuyao on 2018/5/1 21:17.
 */
public class KruskalMST<Weight extends Number & Comparable> {
    private Vector<Edge<Weight>> mst;
    private Number mstWeight;

    // 构造函数, 使用Kruskal算法计算graph的最小生成树
    public KruskalMST(WeightedGraph graph) {
        mst = new Vector<Edge<Weight>>();
//        将图中的所有边存放到一个最小堆中
        MinHeap<Edge<Weight>> pq = new MinHeap<Edge<Weight>>(graph.E());
        for (int i = 0; i < graph.V(); i++) {
            for (Object item : graph.adj(i)) {
                Edge<Weight> e = (Edge<Weight>) item;
//                为了避免重复插入边,设置只有当e的前面点比后面小或等于时才插入
                if (e.v() <= e.w()) {
                    pq.insert(e);
                }
            }
        }
//        创建一个大小为点的个数的并查集,查看所有点的是否在同一个并查集中
        UnionFind unionFind = new UnionFind(graph.V());
//        当pq不为空或者边数已经为V-1时就停止
        while (!pq.isEmpty() && mst.size() < graph.V() - 1) {
//            取出最小边
            Edge<Weight> e = pq.extractMin();
//            如果当前最小的边的两个顶点在同一个集合里面,继续查找
            if (unionFind.isConnected(e.v(), e.w())) {
                continue;
            }
//            否者将当前边加入到最小路径中
            mst.add(e);
//            将边的两个顶点合并
            unionFind.unionElements(e.v(), e.w());
        }

        mstWeight = mst.elementAt(0).wt();
        for (int i = 1; i < mst.size(); i++) {
            mstWeight = mstWeight.doubleValue() + mst.elementAt(i).wt().doubleValue();
        }

    }

    // 返回最小生成树的所有边
    Vector<Edge<Weight>> mstEdges() {
        return mst;
    }

    // 返回最小生成树的权值
    Number result() {
        return mstWeight;
    }

    // 测试 Kruskal
    public static void main(String[] args) {

        String filename = "testG1-2.txt";
        int V = 8;

        SparseWeightedGraph<Double> g = new SparseWeightedGraph<Double>(V, false);
        ReadWeightedGraph readGraph = new ReadWeightedGraph(g, filename);

        // Test Kruskal
        System.out.println("Test Kruskal:");
        KruskalMST<Double> kruskalMST = new KruskalMST<Double>(g);
        Vector<Edge<Double>> mst = kruskalMST.mstEdges();
        for (int i = 0; i < mst.size(); i++) {
            System.out.println(mst.elementAt(i));
        }
        System.out.println("The MST weight is: " + kruskalMST.result());

        System.out.println();
    }
}

Kruskal的时间复杂度为O(ElogE)

  • 9 min read

CONTRIBUTORS


  • 9 min read