最小生成树

什么是最小生成树?

一个有 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条边,如果生成树中再添加一条边,则必定成环。

1.jpg


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

/*
* 图中的边
*/
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查看有关知识。

20160714144315409.jpg

代码如下:

并查集:
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个顶点为止。

20160714161107576.jpg

代码如下:

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

对比

捕获.PNG

总结

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

本文由 罗罗 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:https://www.lwjppz.cn /archives/20190821132514
最后更新于:2020-02-26 16:19:57

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×