目录

一、 最小生成树定义及相关约定1. 定义2. 约定二、最小生成树原理1. 数的性质2. 切分定理3. 贪心算法三、Prim算法1. Prim算法流程2. Prim算法实现3. Prim算法实现精简版四、Kruskal算法1. Kruskal算法流程2. Kruskal算法实现3. Kruskal算法实现精简版

一、 最小生成树定义及相关约定

在加权图中，它的边关联了一个权重，那么我们就可以根据这个权重解决最小成本问题，但如何才能找到最小成本对应的顶点和边呢？最小生成树相关算法可以解决。

1. 定义

图的生成树是它的一棵含有其所有顶点的无环连通子图，一副加权无向图的最小生成树它的一棵权值(树中所有边的权重之和)最小的生成树

2. 约定

只考虑连通图。最小生成树的定义说明它只能存在于连通图中，如果图不是连通的，那么分别计算每个连通图子图的最小生成树，合并到一起称为最小生成森林。

二、最小生成树原理

1. 数的性质

用一条边接树中的任意两个顶点都会产生一个新的环 从树中删除任意一条边，将会得到两棵独立的树

2. 切分定理

要从一副连通图中找出该图的最小生成树，需要通过切分定理完成。

切分

将图的所有顶点按照某些规则分为两个非空且没有交集的集合。

横切边

连接两个属于不同集合的顶点的边称之为横切边。

例如我们将图中的顶点切分为两个集合，灰色顶点属于一个集合，白色顶点属于另外一个集合，那么效果如下：

切分定理

在一副加权图中，给定任意的切分，它的横切边中的权重最小者必然属于图中的最小生成树。

注意:一次切分产生的多个横切边中，权重最小的边不一定是所有横切边中唯一属于图的最小生成树的边。

3. 贪心算法

贪心算法是计算图的最小生成树的基础算法，它的基本原理就是切分定理，使用切分定理找到最小生成树的一条边，不断的重复直到找到最小生成树的所有边。如果图有V个顶点，那么需要找到V - 1条边，就可以表示该图的最小生成树。

计算图的最小生成树的算法有很多种，但这些算法都可以看做是贪心算法的一种特殊情况，这些算法的不同之处在于保存切分和判定权重最小的横切边的方式。

三、Prim算法

Prim算法，它的每一步都会为一棵生成中的树添加一条边。一开始这棵树只有一个顶点，然后会向它添加V - 1条边，每次总是将下一条连接树中的顶点与不在树中的顶点且权重最小的边加入到树中。

Prim算法的切分规则

把最小生成树中的顶点看做是一个集合，把不在最小生成树中的顶点看做是另外一个集合。

1. Prim算法流程

Prim算法始终将图中的顶点切分成两个集合，最小生成树顶点和非最小生成树顶点，通过不断的重复做某些操作，可以逐渐将非最小生成树中的顶点加入到最小生成树中，直到所有的顶点都加入到最小生成树中。

2. Prim算法实现

代码中提到的Edge、EdgeWeightedGraph类可详见Java数据结构-图

import java.util.ArrayList;import java.util.Arrays;import java.util.List;import java.util.PriorityQueue;public class PrimMST {// 索引代表顶点，值表示当前顶点和最小生成树之间的最短边private Edge[] edgeTo;// 索引代表顶点，值表示当前顶点和最小生成树之间的最短边的权重private double[] distTo;// 索引代表顶点，如果当前顶点已经在生成树中，则值为true，否则为falseprivate boolean[] marked;/*存放树中顶点与非树中顶点之间的有效横切边使用优先队列，Edge实现了 Comparable每次返回权重最小的边*/private PriorityQueue<Edge> pq;// 根据一副加权无向图，创建最小生成树计算对象public PrimMST(EdgeWeightedGraph G) {// 初始化edgeTothis.edgeTo = new Edge[G.V()];// 初始化distTothis.distTo = new double[G.V()];Arrays.fill(distTo, Double.POSITIVE_INFINITY);// 初始化markedthis.marked = new boolean[G.V()];// 初始化pqpq = new PriorityQueue<Edge>(G.V());visit(G, 0);//遍历索引最小优先队列，拿到最小和N切边对应的顶点，把该顶点加入到最小生成树中while (!pq.isEmpty()){// 取出当前距离生成树权重最小的边Edge e = pq.poll();// 获取两个顶点的索引int v = e.either(), w = e.other(v);// 如果两个点现在均已加入了生成树，则不做处理if (marked[v] && marked[w])continue;// 当前 v 点未加入if (!marked[v])visit(G, v);// 当前 w 点未加入if (!marked[w])visit(G, w);}}// 将顶点v添加到最小生成树中，并且更新数据private void visit(EdgeWeightedGraph G, int v) {// 把顶点v添加到最小生成树中marked[v] = true;// 更新数据for (Edge e : G.adj(v)) {// 获取e边的另外一个顶点(当前顶点是v)int w = e.other(v);/*判断另外一个顶点是不是已经在生成树中，如果在树中，则不做任何处理，如果不在树中，更新数据*/if (marked[w]){continue;}// 判断边e的权重是否小于从w顶点到树中已经存在的最小边的权重；if (e.weight() < distTo[w]){// 更新数据edgeTo[w] = e;distTo[w] = e.weight();pq.offer(e);}}}// 获取最小生成树的所有边public List<Edge> edges() {// 创建队列对象List<Edge> allEdges = new ArrayList<>();// 遍历edgeTo数组，拿到每一条边，如果不为null，则添加到列表中for (Edge edge : edgeTo) {if (edge != null) {allEdges.add(edge);}}return allEdges;}}

3. Prim算法实现精简版

上述算是Prim算法的标准版，但如果对于解决一些小算法题，设计边、加权有向图类，在代码中还是比较臃肿，以下实现一个Prim算法的精简版，使用邻接矩阵来存储图。

public class PrimMST {// 图类static class Graph{// 顶点数量int v;// 使用邻接矩阵存放边，weights[i][j] 代表 i -> j 的权重double[][] weights;public Graph(int v, double[][] weights) {this.v = v;this.weights = weights;}}/*根据传入的图，计算最下生成树的权重；若不存在生成树，返回 -1*/public static double prim(Graph graph){// 标记已加入最小生成树的顶点int[] visited = new int[graph.v];// 标记每个顶点到生成树的最短距离double[] distTo = new double[graph.v];// 所有点到生成树的距离都设为正无穷Arrays.fill(distTo, Double.MAX_VALUE);/*等会遍历时会从 0 作为起始点， 0 号一定会加入生成树，所以赋值它到生成树的距离为 0*/distTo[0] = 0;double sumWeight = 0;// 遍历 graph.v 次for (int k = 0; k < graph.v; ++k){// 找到目前距离生成树距离最小的顶点的索引int tempIndex = -1;for (int i = 0; i < graph.v; ++i) {if (visited[i] == 0 && (tempIndex == -1 || distTo[i] < distTo[tempIndex])) {tempIndex = i;}}if (k != 0 && distTo[tempIndex] == Double.MAX_VALUE){/*当前点不为起始点并且距离生成树的距离已为正无穷，说明图已经不连通了，不存在生成树，直接返回 -1*/return -1;}// 将该点到生成树的距离加入总权重sumWeight += distTo[tempIndex];// 标记该点已经加入生成树visited[tempIndex] = 1;for (int j = 0; j < graph.v; ++j){/*用以上加入生成树的点更新其他点到生成树的距离主要是解决 tempIndex 点的连接点这可以比喻为 tempIndex 处的顶点当上了驸马加入了皇家那么跟他有关系的顶点距离皇家的距离也更近了*/distTo[j] = Math.min(distTo[j], graph.weights[tempIndex][j]);}}return sumWeight;}}

四、Kruskal算法

kruskal算法是计算一副加权无向图的最小生成树的另外一种算法，它的主要思想是按照边的权重(从小到大)处理它们，将边加入最小生成树中，加入的边不会与已经加入最小生成树的边构成环，直到树中含有V - 1条边为止。

kruskal算法和prim算法的区别：

Prim算法是一条边一条边的构造最小生成树，每一步都为一棵树添加一条边。kruskal算法构造最小生成树的时候也是一条边一条边地构造，但它的切分规则是不一样的。它每一次寻找的边会连接一片森林中的两棵树。如果一副加权无向图由V个顶点组成，初始化情况下每个顶点都构成一棵独立的树，则V个顶点对应V棵树，组成一片森林，

kruskal算法每一次处理都会将两棵树合并为一棵树，直到整个森林中只剩一棵树为止。

1. Kruskal算法流程

初始化先将所有边加入优先队列，每次使用poll()取出权重最小的边，并得到该边关联的两个顶点v和w，通过uf.connect(v, w)判断v和w是否已经连通，如果连通，则证明这两个顶点在同一棵树中，那么就不能再把这条边添加到最小生成树中，因为在一棵树的任意两个顶点上添加一条边，都会形成环，而最小生成树不能有环的存在，如果不连通，则通过uf.union(v, w)把顶点v所在的树和顶点w所在的树合并成一棵树，并把这条边加入到mst列表中，这样如果把所有的边处理完，最终mst中存储的就是最小生树的所有边。

2. Kruskal算法实现

同样的，代码中提到的Edge、EdgeWeightedGraph类可详见Java数据结构-图

同时，在这里还使用了另外一个数据结构-并查集，可详见Java数据结构-并查集

import java.util.ArrayList;import java.util.List;import java.util.PriorityQueue;public class KruskalMST {// 保存最小生成树的所有边private List<Edge> mst;/*索引代表顶点，使用uf.connect(v,w)可以判断顶点v和顶点w是否在同一颗树中，使用uf.union(v,w)可以把顶点v所在的树和顶点w所在的树合并*/private UF_Tree_Weighted uf;// 存储图中所有的边，使用优先队列，对边按照权重进行排序private PriorityQueue<Edge> pq;// 根据一副加权无向图，创建最小生成树计算对象public KruskalMST(EdgeWeightedGraph G) {// 初始化mstthis.mst = new ArrayList<>();// 初始化ufthis.uf = new UF_Tree_Weighted(G.V());// 初始化 pqthis.pq = new PriorityQueue<>();// 把图中所有的边存储到pq中for (Edge e : G.edges()) {pq.offer(e);}// 遍历pq队列，拿到最小权重的边，进行处理while(!pq.isEmpty() && mst.size() < G.V() - 1){// 找到权重最小的边Edge e = pq.poll();// 找到该边的两个顶点int v = e.either();int w = e.other(v);/*判断这两个顶点是否已经在同一颗树中，如果在同一颗树中，则不对该边做处理，如果不在一棵树中，则让这两个顶点属于的两棵树合并成一棵树*/if (uf.connected(v, w)){continue;}uf.union(v,w);// 让边e进入到mst队列中mst.add(e);}}// 获取最小生成树的所有边public List<Edge> edges() {return mst;}}

3. Kruskal算法实现精简版

在三中我们使用了Prim算法的精简版，同样的，上述算是kruskal算法的标准版，但如果对于解决一些小算法题，设计边、加权有向图类、以及并查集，在代码中还是比较臃肿，以下实现一个kruskal算法的精简版，使用邻接矩阵来存储图。

public class KruskalMST {// 图类static class Graph{// 顶点数量int v;// 使用邻接矩阵存放边，weights[i][j] 代表 i -> j 的权重double[][] weights;/*存放边的信息way[i][0] way[i][1] way[i][2]分别代表 第 i 条边的起点、终点、权重用 Number 类是因为 索引为整数 但是权重为小数*/List<Number[]> way;public Graph(int v, double[][] weights) {this.v = v;this.weights = weights;this.way = new ArrayList<>();for (int i = 0; i < weights.length; ++i){for (int j = 0; j < weights[i].length; ++j){/*因为是无向图，一条边就有两种形容方式 i -> j 与 j -> i此处只取一种*/if (weights[i][j] != Double.MAX_VALUE && i < j)way.add(new Number[]{i, j, weights[i][j]});}}// 按照权重排序，（这就类似上述使用的优先队列了）Collections.sort(way, new Comparator<Number[]>() {@Overridepublic int compare(Number[] o1, Number[] o2) {double r = (double)o1[2] - (double) o2[2];return r < 0 ? -1 : r > 0 ? 1 : 0;}});}}// 将 a, b 归为一组public static void connection(int[] groups, int a, int b){int gA = groups[a];int gB = groups[b];// 全部化为 gA 的 值for (int i = 0; i < groups.length; ++i){if (groups[i] == gB)groups[i] = gA;}}// 返回 a 所在分组public static int find(int[] groups, int a){return groups[a];}/*根据传入的图，计算最下生成树的权重；若不存在生成树，返回 -1*/public static double kruskal(Graph graph){// 建立 并查集int[] groups = new int[graph.v];for (int i = 0; i < groups.length; ++i)groups[i] = i;// 统计待会找到的边数int countE = 0;double sumWeight = 0;for (int i = 0; i < graph.way.size(); ++i){// 获取边的 起点、终点、权值int a = (int) graph.way.get(i)[0];int b = (int) graph.way.get(i)[1];double w = (double) graph.way.get(i)[2];int gA = find(groups, a);int gB = find(groups, b);if (gA != gB){// 若 a、b 不属于同一组，则将他们分为同一组connection(groups, a, b);sumWeight += w;countE += 1;}}// 找到的边的数量不为 结点数 - 1， 不存在生成树if (countE < graph.v - 1)return -1;return sumWeight;}}