最小生成树（Minimum Spanning Tree）的原理及实现（Java）_java

最小生成树（Minimum Spanning Tree）：给定无向图中，边权重最小的生成树。
满足条件
生成树——包含图中所有顶点的树；
最小——边权重之和最小的生成树。
它是图中全局的概念，而SPT（Shortest Path Tree，最短路径树）是相对图中某一个初始节点而言的。

算法原理

Cut和Crossing edge

Cut——将图中所有顶点分入（这个好像是随便来的？）两个非空集合中；
Crossing Edge——连接的顶点分别位于不同的集合中。
在一次cut中，所有crossing edge权值最小的edge一定是MST中的一个边（证明过程很有趣）

Prims算法

1.随机选定graph中的一个顶点；
2.将它和graph中其他顶点分割为两个集合A和B；
3.在Crossing edge中找到权重最小（如果有多个，随便选一个）的edge连接的顶点；
4.重新分割，将3中发现的属于集合B的顶点归入A中；
重复3和4步骤，直至找到MST。步骤三的时间复杂度比较高，可以使用PQ进行优化，不过好难看懂，可以参考这个video。

Kruskals算法

1.将所有edge按照权重在PQ中按从小到大的顺序跟踪；
2.取出PQ跟踪的第一个edge，将其放入MST中，检查是否会形成环路，如果是，则丢弃该edge；
3.重复步骤2直至找到MST（V-1条边）。

java代码
MSTFind.java

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class MSTFind {
    private Graph graph;

    MSTFind(Graph graph) {
        this.graph = graph;
    }

    public List<Graph.Edge> Prims() {
        /* 1.随机选定graph中的一个顶点；
           2.将它和graph中其他顶点分割为两个集合A和B；
           3.在Crossing edge中找到权重最小（如果有多个，随便选一个）的edge连接的顶点，将该edge归入MST中；
           4.重新分割，将3中发现的属于集合B的顶点归入A中；
           重复3和4步骤，直至找到MST（V-1条边）。
         */
        Set<Integer> A = new HashSet<>();
        Set<Integer> B = new HashSet<>();
        List<Graph.Edge> MST = new ArrayList<>();
        A.add(0);
        for (int i = 0; i < graph.V(); i++) {
            if (!A.contains(i)) {
                B.add(i);
            }
        }
        while (MST.size() != graph.V() - 1) {
            Graph.Edge minEdge = findMinCrossEdge(A, B);
            MST.add(minEdge);
            cutSets(A, B, minEdge);
        }
        return MST;
    }

    private Graph.Edge findMinCrossEdge(Set<Integer> a, Set<Integer> b) {
        /* 找到权重最小的crossing edge
         */
        Graph.Edge res = new Graph.Edge(0, new Graph.Pair(0, Integer.MAX_VALUE));
        for (int v : a) {
            for (Graph.Pair p : graph.adj(v)) {
                if (!a.contains(p.getAnotherV())) {
                    if (p.getWeight() < res.getWeight()) {
                        res = new Graph.Edge(v, p);
                    }
                }
            }
        }
        return res;
    }

    private void cutSets(Set<Integer> a, Set<Integer> b, Graph.Edge e) {
        for (int v : e.getVs()) {
            if (!a.contains(v)) {
                a.add(v);
                b.remove(v);
            }
        }
    }

    public static void main(String[] args) {
        Graph test = new Graph(7);   // 按照实例初始化graph
        test.addEdge(0, 1, 2);
        test.addEdge(0, 2, 1);
        test.addEdge(1, 2, 5);
        test.addEdge(1, 3, 11);
        test.addEdge(1, 4, 3);
        test.addEdge(2, 4, 1);
        test.addEdge(2, 5, 15);
        test.addEdge(3, 4, 2);
        test.addEdge(4, 5, 4);
        test.addEdge(3, 6, 1);
        test.addEdge(4, 6, 5);
        test.addEdge(5, 6, 1);
        MSTFind t = new MSTFind(test);
        for (Graph.Edge e : t.Prims()) {
            System.out.print(e.getVs() + " ");
        }
    }
}

Graph.java

import java.util.*;

public class Graph {
    /* 无向、有权图
     */
    private static List<Pair>[] ver;
    private static Set<Edge> edges;

    Graph(int v) {
        /* Create empty graph with v vertices
         */
        ver = new List[v];
        edges = new HashSet<>();
    }

    public static class Pair {
        private int anotherV;
        private int weight;

        Pair(int v, int weight) {
            this.anotherV = v;
            this.weight = weight;
        }

        public int getAnotherV() {
            return anotherV;
        }

        public int getWeight() {
            return weight;
        }
    }

    public static class Edge {
        private int v;
        private Pair t;

        Edge(int v, Pair t) {
            this.v = v;
            this.t = t;
        }

        public int getV() {
            return v;
        }

        public int getWeight() {
            return t.getWeight();
        }

        public List<Integer> getVs() {
            List<Integer> res = new ArrayList<>();
            res.add(v);
            res.add(t.getAnotherV());
            return res;
        }
    }


    public void addEdge(int v, int w, int weight) {
        /* add an edge v-w with weight
         */
        Pair pairV = new Pair(w, weight);
        Pair pairW = new Pair(v, weight);
        if (ver[v] == null) {
            ver[v] = new ArrayList<>();
        }
        if (ver[w] == null) {
            ver[w] = new ArrayList<>();
        }
        ver[v].add(pairV);
        ver[w].add(pairW);
    }

    Iterable<Pair> adj(int v) {
        /* vertices adjacent to v
         */
        return ver[v];
    }

    public int V() {
        /* number of vertices
         */
        return ver.length;
    }

    public int E() {
        /* number of edges
         */
        int res = 0;
        for (int i = 0; i < ver.length; i++) {
            res += ver[i].size();
        }
        return res / 2;
    }

    public static void main(String[] args) {
        Graph test = new Graph(7);   // 按照实例初始化graph
        test.addEdge(0, 1, 2);
        test.addEdge(0, 2, 1);
        test.addEdge(1, 2, 5);
        test.addEdge(1, 3, 11);
        test.addEdge(1, 4, 3);
        test.addEdge(2, 4, 1);
        test.addEdge(2, 5, 15);
        test.addEdge(3, 4, 2);
        test.addEdge(4, 5, 4);
        test.addEdge(3, 6, 1);
        test.addEdge(4, 6, 5);
        test.addEdge(5, 6, 1);
        for (int i = 0; i < test.V(); i++) {
            List<Integer> adj = new ArrayList<>();
            for (Pair p : test.adj(i)) {
                adj.add(p.getAnotherV());
            }
            System.out.println("和" + i + "邻接的顶点为：" + adj);
        }
        System.out.println("顶点的数量：" + test.V());   // 顶点的数量应该为5
        System.out.println("边的的数量：" + test.E());   // 边的数量应该为6
    }
}