最小生成树
先来看一个问题：
网络异常，图片无法展示
|
在上述图中，描述了学校、农场等6个地点，并用权值标志了各个地点之间的道路距离，现在假设我需要用最小的边，去连通图中所有的地点，这个最小边连通的树就是它的最小生成树。
生成树的属性
- 一个连通图可以有多个生成树；
- 一个连通图的所有生成树都包含相同的顶点个数和边数；
- 生成树当中不存在环；
- 移除生成树中的任意一条边都会导致图的不连通， 生成树的边最少特性；
- 在生成树中添加一条边会构成环。
- 对于包含n个顶点的连通图，生成树包含n个顶点和n-1条边；
- 对于包含n个顶点的无向完全图最多包含nn−2n^{n-2}nn−2颗生成树。
最小生成树
最小生成树，就是无向图中边的权值最小的生成树。
对于一个带权连通无向图G=(V,E)，生成树不同，每棵树的权（树中所有边上的权值和）也不同，设R为G的所有生成树的集合，若T为R中权值和最小的生成树，则T称为G的最小生成树（Minimum-Spanning-Tree，MST）
注：
- 1、最小生成树可能有多个，但边的权值之和总是唯一且最小的
- 2、最小生成树的边数=定点数-1，砍掉一条则不连通，增加一条则会出现回路
- 3、若一个连通图本身就是一颗树，则其最小生成树就是它本身
- 4、只有连通图才有生成树，非连通图只有生成森林
生成最小生成树的算法有两种：Kruskal算法（克鲁斯卡尔）、普里姆算法（Prim）。
Kruskal算法
每次选择 权值最小且不违反最小生成树属性（不构成环） 的边，使这条边的两头连通（原本已近连通则不选）直到所有结点都连通。
思路
- 1.把所有边进行排序
- 2.先把最小的边考虑进去，然后再看是否形成环，如果成环了就不要把这个边考虑进去，如果没有，进入下一步
- 3.再把下一个小的边考虑进去，再判断是否形成环，如果成环了就不要把这个边考虑进去，如果没有，进入下一步
- 4.直到连通所有
难点
Kruskal算法的难点在于：如何判断添加一条边后是否形成环？
主要是在于实现集合查询与集合合并。首先，每个点都属于一个单独的集合，当把一个边考虑进去的时候，先判断大的集合里有没有包含这个节点，如果里面有这个节点了就表示形成环了，否则就将把这个节点所在的集合合并进去。
代码实现
public class Kruskal { // 这样是可以的，但是没有并查集快 public static class MySets{ public HashMap<Node, List<Node>> setMap; public MySets(List<Node> nodes){ for(Node cur: nodes){ List<Node> set = new ArrayList<Node>(); set.add(cur); setMap.put(cur, set); } } public MySets(List<Node> nodes){ for(Node cur: nodes){ List<Node> set = new ArrayList<Node>(); set.add(cur); setMap.put(cur, set); } } public MySets(List<Node> nodes){ for(Node cur: nodes){ List<Node> set = new ArrayList<Node>(); set.add(cur); setMap.put(cur, set); } } } // K算法（并查集） public static Set<Edge> KruskalMST(Gragh graph){ UnionFind unionFind = new UnionFind(); // 生成一个并查集结构 unionFind.makeSets(graph.nodes.values()); // 利用比较器将边进行排序 PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator()); for(Edge edge:graph.edges){ // M条边 priorityQueue.add(edge); // O(logM) } Set<Edge> result = new HashSet<>(); while(!priorityQueue.isEmpty()){ // M条边 Edge edge = priorityQueue.poll(); // O(logM) if(!unionFind.isSameSet(edge.form, edge.to)){ // O(1) result.add(edge); unionFind.union(edge.from, edge.to); } } return result; } } 复制代码
Prim算法
举个例子
网络异常，图片无法展示
|
如图所示，如果我们要对它进行Prim算法操作，那么数据演示如下：
- 假设从A点出发（Prim算法对出发的点没有要求，随意选一个出发点即可），此时就释放了三条边：A-B、A-C、A-D，从中选取权值最小的边
A-C，那么A、C两点被选中 - C点被选中，那么C-B、C-D、C-E、C-F四个边也被释放，从中选取权值最小的边
C-F（A点已经被选中了，所以不能选C-A这个边了），此时A、C、F三点被选中 - F点被选中，那么F-D、F-E两个边也被释放，从中选取权值最小的边
F-D，此时A、C、F、D四点被选中 - D点被选中，没有新的边需要被释放，此时在全局范围内（指被释放的但未曾被选中权值最小的边）挑权值最小的边，也就是A-B(6)、A-D(5)、C-B(5)、C-D(5)、C-E(6)、F-E(6)中挑选，其中A-D(5)、C-D(5)涉及的点都曾被选中了，因此只能选
C-B(5)这个边，此时A、C、F、D、B五点被选中 - B点被选中，
B-E边被释放，此时A、C、F、D、B、E已经全部被选中，最小生成树已经形成，A-C、C-F、F-D、C-B、B-E所形成的就是最小生成树
代码实现
public static class EdgeComparator implements Comparator<Edge>{ public int compare(Edge o1, Edge o2){ return o1.weight - o2.weight } } public static Set<Edge> primMST(Graph graph){ // 解锁的边进入小根堆 PriorityQueue<Edge> PriorityQueue = new PriorityQueue<>(new EdgeComparator()); HashSet<Node> set = new HashSet<>(); Set<Edge> result = new HashSet<>(); // 依次挑选的边在result里 for(Node node: graph.nodes.values()){ // 随便挑了一个点 // node 是开始点 if(!set.contains(node)){ set.add(node); for(Edge edge: node.edges){ // 由一个点，解锁所有相连的边 priorityQueue.add(edge); } while(!priorityQueue.isEmpty()){ Edge edge = priorityQueue.poll(); // 弹出解锁的边中，最小的边 Node toNode = edge.to; // 可能的一个新的点 if(!set.contains(toNode)){ // 不含有的时候，就是新的点 set.add(toNode); result.add(edge); for(Edge nextEdge: toNode.edges){ priorityQueue.add(nextEdge); } } } } } return result; } 复制代码
