最小生成树

# 最大权和生成树

一个有 n 个结点的连通图的生成树是原图的最小连通子图，且包含原图中所有 n 个结点，并且有保持图联通的最少的边。最大生成树就是权和最大生成树，现在给出一个无向带权图的邻接矩阵，权为 0 表示没有边。｛{0，4，5，0，3}，{4，0，4，2，3}， {5，4，0，2，0}，{0，2，2，0，1}，{3，3，0，1，0}｝，求这个图的最大生成树的权和为 14。

最小生成树

最小生成树其实是最小权重生成树的简称，一副连通加权无向图中一棵权值最小的生成树。

Kruskal

(1)新建图 G

(2)把图 G 中所有的边按照权值从小到大排序。(一般使用优先队列) (3)取出最小的边 (4)如果这条边连接的两个节点于图 G 中不在同一个连通分量中，则添加这条边到图 G 中.(使用并查集) (5)重复 3，直至图 G 中所有的节点都在同一个连通分量中

public class KruskalMST {

    private Queue<Edge> mst = new Queue<>();
    private double weight;

    public KruskalMST(EdgeWeightedGraph g){
        MinPQ<Edge> minPQ = new MinPQ<>();
        for (Edge edge:g.edges()){
            minPQ.insert(edge);
        }
        UF uf =new UF(minPQ.size());
        while (!minPQ.isEmpty()){
            Edge edge = minPQ.delMin();
            int v = edge.either();
            int w = edge.other(v);
            if(!uf.connected(v,w)){
                uf.union(v,w);
                mst.enqueue(edge);
                //weight+=edge.weight();
            }
        }
    }
}

Kruskal 算法基本上取决于优先队列的选择，以及并查集的实现。比较优的算法效率为O(ElogE)E 为图中的边数.对优先队列和并查集不了解的同学可以看看我这两篇文章，查找算法之顺序、二分、二叉搜索树、红黑树和并查集

Prim

Prim 算法，简单的说就是从一个点开始不断让树长大的过程,并且保持权值最小。 (1)生成图 G

(2)从 s 点开始 (3)把与 s 点相连的边都加入 edgeTo[],并且保存到这些点的距离 distTo[],且插入到优先队列 (4)出队一个点 (5)查找与这个点相连的点，若权值比 distTo[]中保存的值小则进更新，同时更新 distTo[]和优先队列 (6)重复 4

private Edge[] edgeTo;        // edgeTo[v] = shortest edge from tree vertex to non-tree vertex
    private double[] distTo;      // distTo[v] = weight of shortest such edge
    private boolean[] marked;     // marked[v] = true if v on tree, false otherwise
    private IndexMinPQ<Double> pq;

    public PrimMST(EdgeWeightedGraph G){
        edgeTo = new Edge[G.V()];
        distTo = new double[G.V()];
        marked = new boolean[G.V()];
        pq = new IndexMinPQ<Double>(G.V());
        for (int v = 0; v < G.V(); v++)
            distTo[v] = Double.POSITIVE_INFINITY;

        for (int v = 0; v < G.V(); v++)      // run from each vertex to find
            if (!marked[v]) prim(G, v);      // minimum spanning forest
    }

    private void prim(EdgeWeightedGraph g, int s) {
        distTo[s]=0;
        pq.insert(s,distTo[s]);
        while (!pq.isEmpty()){
            grow(g,pq.delMin());
        }
    }

    private void grow(EdgeWeightedGraph g, int v) {
        marked[v]=true;
        for (Edge e :g.adj(v)){
            int w = e.other(v);
            if(marked[w])   continue;
            if(distTo[w]>e.weight()){
                distTo[w]=e.weight();
                edgeTo[w] = e;
                if(pq.contains(w))
                    pq.decreaseKey(w,distTo[w]);
                else
                    pq.insert(w,distTo[w]);
            }
        }

    }

Kruskal can have better performance if the edges can be sorted in linear time, or are already sorted。Prim’s better if the number of edges to vertices is high.

最小生成树

最小生成树

Kruskal

Prim

Links