什么是最小生成树？

一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。

概述

在一给定的无向图G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即），而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集且为无循环图，使得的 w(T) 最小，则此 T 为 G 的最小生成树。

最小生成树其实是最小权重生成树的简称

应用

例如：要在n个城市之间铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。

关于图的几个概念定义：

• 连通图：在无向图中，若任意两个顶点vivi与vjvj都有路径相通，则称该无向图为连通图。
• 强连通图：在有向图中，若任意两个顶点vivi与vjvj都有路径相通，则称该有向图为强连通图。
• 连通网：在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权；权代表着连接连个顶点的代价，称这种连通图叫做连通网。
• 生成树：一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。

以下代码会用到的数据类型：

/*
* 图中的边
*/
public class Edge implements Comparable<Edge> {
    private final int v;
    private final int w;
    private int weight;

    public Edge(int v, int w, int weight) {
        this.v = v;
        this.w = w;
        this.weight = weight;
    }

    public int either() {
        return v;
    }

    public int other(int vertex) {
        if (vertex == v) {
            return w;
        } else {
            return v;
        }
    }

    public int getWeight() {
        return weight;
    }

    @Override
    public int compareTo(Edge o) {
        if (this.weight > o.weight) {
            return 1;
        } else if (this.weight < o.weight) {
            return -1;
        } else {
            return 1;
        }
    }

    @Override
    public String toString() {
        return "Edge{" +  "v=" + v +  ", w=" + w + ", weight=" + weight + '}';
    }
}

/*
* 无向连通图的数据类型
*/
public class EdgeWeightedGraph {
    private final int V;
    private int E;
    private LinkedList<Edge>[] adj;

    public EdgeWeightedGraph(int V) {
        this.V = V;
        this.E = 0;
        this.adj = (LinkedList<Edge>[]) new LinkedList[V];
        for (int v = 0; v < V; v++) {
            adj[v] = new LinkedList<Edge>();
        }
    }

    public int V() {
        return V;
    }

    public int E() {
        return E;
    }

    public void addEdge(Edge e) {
        int v = e.either();
        int w = e.other(v);
        adj[v].add(e);
        adj[w].add(e);
        E++;
    }

    public LinkedList<Edge> edges() {
        LinkedList<Edge> b = new LinkedList<>();
        for (int v = 0; v < V; v++) {
            for (Edge e : adj[v]) {
                if (e.other(v) > v) {
                    b.add(e);
                }
            }
        }
        return b;
    }

    public Iterable<Edge> adj(int v) {
        return adj[v];
    }
}

下面介绍两种求最小生成树算法

1.Kruskal算法

此算法可以称为加边法，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。

1. 把图中的所有边按代价从小到大排序；
2. 把图中的n个顶点看成独立的n棵树组成的森林；
3. 按权值从小到大选择边，所选的边连接的两个顶点 ui , vi。ui , vi,应属于两颗不同的树，则成为最小生成树的一条边，并将这两颗树合并作为一颗树。
4. 重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。

此算法需要用到 并查集(Union-Find) 的知识,不懂得同学请先点击这里Union-Find查看有关知识。

代码如下：

并查集：

public class UF {
    private int[] id;
    private int count;

    public UF(int N) {
        count = N;
        id = new int[N];
        for (int i = 0; i < N; i++) {
            id[i] = i;
        }
    }

    public int count() {
        return count;
    }

    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    public int find(int p) {
        while (p != id[p]) {
            p = id[p];
        }
        return p;
    }

    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        id[pRoot] = qRoot;
        count--;
    }
}

public class KruskalMST {
    private Queue<Edge> mst;                //  存储最小生成树的每条边
    private Queue<Edge> pq;                 //  优先队列，获取权重最小的边
    private int weight;                     //  权重和

    public KruskalMST() {
    }

    public void kruskalMST(EdgeWeightedGraph G) {
        mst = new LinkedList<Edge>();
        pq = new PriorityQueue<Edge>();
        for (Edge e : G.edges()) {
            pq.offer(e);
        }
        UF uf = new UF(G.V());
        while (!pq.isEmpty() && mst.size() < G.V() - 1) {
            Edge e = pq.poll();             //  从pq中获得权重最小的边和它的顶点
            int v = e.either();
            int w = e.other(v);
            if (!uf.connected(v, w)) {      //  如果v和w不构成环
                uf.union(v, w);             //  合并分量
                mst.offer(e);               //  将边添加到最小生成树中
            }
        }
        printKruskalMST();
    }

    private void printKruskalMST() {
        while (!mst.isEmpty()) {
            Edge e = mst.poll();
            weight += e.getWeight();
            System.out.println(e);
        }
        System.out.println("总权重为："+weight);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int V = sc.nextInt();
            int E = sc.nextInt();
            EdgeWeightedGraph edgeWeightedGraph = new EdgeWeightedGraph(V);
            for (int i = 0; i < E; i++) {
                Edge e = new Edge(sc.nextInt() - 1, sc.nextInt() - 1, sc.nextInt());
                edgeWeightedGraph.addEdge(e);
            }
            KruskalMST kruskal = new KruskalMST();
            kruskal.kruskalMST(edgeWeightedGraph);
        }
    }
}

测试如下：

L:\jdk-11.0.2\bin\java.exe "-javaagent:L:\IDEA\IntelliJ IDEA 2018.3.5\lib\idea_rt.jar=60157:L:\IDEA\IntelliJ IDEA 2018.3.5\bin" -Dfile.encoding=UTF-8 -classpath C:\Users\lwj\Desktop\数据结构与算法\out\production\algorithms Main.Tree.KruskalMST
6 10
1 3 1
1 2 6
1 4 5
2 3 5
2 5 3
3 5 6
3 4 5
3 6 4
4 6 2
6 5 6
Edge{v=0, w=2, weight=1}
Edge{v=3, w=5, weight=2}
Edge{v=1, w=4, weight=3}
Edge{v=2, w=5, weight=4}
Edge{v=1, w=2, weight=5}
总权重为：15

2.Prim算法

此算法可以称为“加点法”，每次迭代选择代价最小的边对应的点，加入到最小生成树中。算法从某一个顶点s开始，逐渐长大覆盖整个连通网的所有顶点。

1. 图的所有顶点集合为VV；初始令集合u=,v=V−uu=,v=V−u;
2. 在两个集合u,vu,v能够组成的边中，选择一条代价最小的边(u0,v0)(u0,v0)，加入到最小生成树中，并把v0v0并入到集合u中。
3. 重复上述步骤，直到最小生成树有n-1条边或者n个顶点为止。

代码如下：

public class PrimMST {
    private boolean[] marked;
    private Queue<Edge> mst;
    private Queue<Edge> pq;

    public void primMST(EdgeWeightedGraph G) {
        pq = new PriorityQueue<Edge>();
        marked = new boolean[G.V()];
        mst = new LinkedList<Edge>();
        visit(G, 0);
        while (!pq.isEmpty()) {
        Edge e = pq.poll();
        int v = e.either();
        int w = e.other(v);
        if (marked[v] && marked[w]) continue;
            mst.offer(e);
            if (!marked[v]) visit(G, v);
            if (!marked[w]) visit(G, w);
        }
        printMST();
    }

    private void visit(EdgeWeightedGraph G, int v) {
        marked[v] = true;
        for (Edge e : G.adj(v)) {
            if (!marked[e.other(v)]) {
                pq.offer(e);
            }
        }
    }

    private void printMST() {
        while (!mst.isEmpty()) {
            Edge e = mst.poll();
            weight += e.getWeight();
            System.out.println(e);
        }
        System.out.println("总权重为："+weight);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int V = sc.nextInt();
            int E = sc.nextInt();
            EdgeWeightedGraph edgeWeightedGraph = new EdgeWeightedGraph(V);
            for (int i = 0; i < E; i++) {
                Edge e = new Edge(sc.nextInt() - 1, sc.nextInt() - 1, sc.nextInt());
                edgeWeightedGraph.addEdge(e);
            }     
            PrimMST primMST = new PrimMST();
            primMST.primMST(edgeWeightedGraph);
        }
    }
}

测试如下：

L:\jdk-11.0.2\bin\java.exe "-javaagent:L:\IDEA\IntelliJ IDEA 2018.3.5\lib\idea_rt.jar=60266:L:\IDEA\IntelliJ IDEA 2018.3.5\bin" -Dfile.encoding=UTF-8 -classpath C:\Users\lwj\Desktop\数据结构与算法\out\production\algorithms Main.Tree.PrimMST
6 10
1 3 1
1 2 6
1 4 5
2 3 5
2 5 3
3 5 6
3 4 5
3 6 4
4 6 2
6 5 6
Edge{v=0, w=2, weight=1}
Edge{v=2, w=5, weight=4}
Edge{v=3, w=5, weight=2}
Edge{v=1, w=2, weight=5}
Edge{v=1, w=4, weight=3}
总权重为：15

对比

总结

克鲁斯卡尔（Kruskal）算法因为只与边相关，则适合求稀疏图的最小生成树。而prime算法因为只与顶点有关，所以适合求稠密图的最小生成树。 无疑，Kruskal算法在效率上要比Prim算法快，因为Kruskal只需要对权重边做一次排序，而Prim算法则需要做多次排序。尽管Prim算法每次做的算法涉及的权重边不一定会涵盖连通图中的所有边，但是随着所使用的排序算法的效率的提高，Kruskal算法和Prim算法之间的差异将会清晰的显性出来。