企业官网建设流程全解析

我们先来看题目描述：

给你一个 points 数组，表示 2D 平面上的一些点，其中 points[i] = [xi, yi] 。 连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 val 的绝对值。 请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。

示例 1：

输入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]] 输出：20 解释：

我们可以按照上图所示连接所有点得到最小总费用，总费用为 20 。

注意到任意两个点之间只有唯一一条路径互相到达。

示例 2：

输入：points = [[3,12],[-2,5],[-4,1]] 输出：18

示例 3：

输入：points = [[0,0],[1,1],[1,0],[-1,1]] 输出：4

示例 4：

输入：points = [[-1000000,-1000000],[1000000,1000000]] 输出：4000000

示例 5：

输入：points = [[0,0]] 输出：0

题解：Kruskal 算法需要用到 Union-Find 并查集算法，因为生成的树不能包含环，而并查集可以用来判环。 对于添加的某条边，如果该边的两个节点本来就在同一连通分量里，那么添加这条边会产生环；

反之，如果该边的两个节点不在同一连通分量里，则添加这条边不会产生环。 为了得到的这棵生成树是权重和最小的，用到了贪心思路： 将所有边按照权重从小到大排序，从权重最小的边开始遍历，如果这条边和 mst 中的其它边不会形成环，则这条边是最小生成树的一部分，将它加入 mst 集合；否则，这条边不是最小生成树的一部分，不要把它加入 mst 集合。