初识最小生成树 首先，小伙伴们可能要冒出第一个问题了。什么是生成树？生成树 指的是「无向图」中，具有该图的 全部顶点 且 边数最少 的连通子图。「图8. 生成树」中，所有粉色线条组成的一棵树[(A, B), (A, C), (A, D), (A, E)]，就是该无向图的其中一个生成树。其实[(A, E),(A, B), (B, C), (C, D)]也是该无向图的一个生成树。由此可见，一个「无向图」的生成树可以是多个。 图8生成树 那么再了解了什么是生成树后，小伙伴们可能又要冒出第二个问题了。什么是最小生成树。最小生成树指的是「加权无向图」中总权重最小的生成树。「图9. 最小生成树」中，所有绿色线条组成的一颗生成树[(A, E),(A, B), (B, C), (C, D)]，就是该加权无向图的其中一个最小生成树。其实[(A, E), (E, D), (A, B), (B, C)]也是该加权无向图的另一个最小生成树，由此可见，一个「加权无向图」的最小生成树可以是多个。 图9.最小生成树 那么在该章节中，我们将学习下「生成最小生成树」的两种算法以及「切分定理」：切分定理Kruskal 算法Prim 算法切分定理 「切分」是什么呢？很多的定理都是以人的名字命名的，但是「切分」并不是一个人的名字。在「切分定理」中有两个基本概念，我们需要了解下：切分：将「图」切成两个部分，称之为一个「切分」。「图 10. 切分图」就是一个「切分」，其中(B, A, E)为一个部分，(C, D)为另外一个部分。横切边：如果一条边连接的两个顶点属于切分的两个部分，这个边称为「横切边」。在「图10. 切分图」中，(B, C), (A, C), (A, D), (E, D) 均为「横切边」。 10.切分图 再了解了切分定理的基础概念之后，我们就需要学习下「切分定理」了。切分定理是 Kruskal 算法和 Prim 算法的重要的理论支撑。那么什么是「切分定理」呢？根据 维基百科 的定义，「切分定理」指的是： 在一幅连通加权无向图中，给定任意的切分，如果有一条横切边的权值严格小于所有其他横切边，则这条边必然属于图的最小生成树中的一条边。切分定理的证明 视频链接Kruskal 算法(以边扩散) 「Kruskal 算法」是求解「加权无向图」的「最小生成树」的一种算法。 视频链接 时间复杂度: $O(E*logE)$ $E$ 表示边数。 空间复杂度： $O(V)$ $V$表示顶点数。练习题--连接所有点的最小费用 题目图 视频讲解解题代码class Solution { // Kruskal Algorithm public int minCostConnectPoints(int[][] points) { if (points == null || points.length == 0) { return 0; } int size = points.length; PriorityQueue<Edge> pq = new PriorityQueue<Edge>((x, y) -> x.cost - y.cost); UnionFind uf = new UnionFind(size); for (int i = 0; i < size; i++) { for (int j = i+1; j < size; j++) { int[] coordinate1 = points[i]; int[] coordinate2 = points[j]; // Calculate the distance between two coordinates. int cost = Math.abs(coordinate1[0] - coordinate2[0]) + Math.abs(coordinate1[1] - coordinate2[1]); Edge edge = new Edge(i, j, cost); pq.add(edge); } } int result = 0; int count = size - 1; while ( pq.size() > 0 && count > 0 ) { Edge e = pq.poll(); if ( !uf.connected(e.point1, e.point2)) { uf.union(e.point1, e.point2); result += e.cost; count--; } } return result; } class Edge { int point1; int point2; int cost; Edge(int point1, int point2, int cost) { this.point1 =…