题目分析

这个题目是一个最小生成树问题，可以通过prim算法或者kurskal算法进行求解。

prim

prim算法是通过节点合并实现的，其步骤为：

首先任意选择一个节点，常常选择第1个节点，然后放入passed集合中。
计算剩余的所有点可以直接到达1号节点的距离
选择一个最小的点k加入到passed集合中。
从剩余节点中如果通过k到达passed集合比之前的更近，则更新该距离。
重复步骤3和4，直到所有的点都在passed集合中为止。
此时距离数组的和就是最小生成树的距离

prim算法时间方面，对于每一个新加入的节点，要计算其他节点通过该节点到达passed集合的距离，空间方面只需要保存passed集合和剩余点到passed集合的最近距离。因此算法的**时间复杂度为$O(n^2)$，空间复杂度为$O(n)$**。

class Solution(object):
    def minCostConnectPoints(self, points):
        def prim(points):
            no_passed = set(range(1, n))
            close_distance = [distance(points[0], points[i]) for i in range(n)]
            while no_passed:
                mini_distance, idx = float('inf'), -1
                for node in no_passed:
                    if mini_distance > close_distance[node]:
                        mini_distance, idx = close_distance[node], node
                no_passed.remove(idx)
                for node in no_passed:
                    close_distance[node] = min(close_distance[node], distance(points[node], points[idx]))
            return sum(close_distance)

        distance = lambda x, y: abs(x[0] - y[0]) + abs(x[1] - y[1])
        n = len(points)
        return prim(points)

kurskal

kurskal算法是通过边合并实现的，其步骤为：
1.首先给每个节点定义一个编号，通常i节点的编号为i，结果res赋值为0
2. 选择距离最近的两个节点，如果两个节点的编号不同，假设为i和j，则将所有等于i的节点的编号改为j相同，说明生成树的结果存在这条边，结果res加上这条边的距离。如果节点相同则说明两个节点已存在一个通路，继续寻找下一个距离最近的边。
3. 重复步骤2，直到所有的点的编号都相同为止。
4. 返回结果res即可。

kurskal算法时间方面，要对每一条边进行排序，假设边数为e，当e很大时，排序的过程非常耗时，当e很小时，网络最少合并n次，每次要判断每个编号是否需要更新，因此**时间复杂度为$O(max(elog(e), n^2))，空间复杂度为$O(e)$**。

在全连接网络中，$e = (n - 1)!$，所以kurskal的时间复杂度和空间复杂度都非常大，如本题，每两个点都有距离定义，因此适合于prim算法，不适合于kurskal算法。

class Solution(object):
    def minCostConnectPoints(self, points):
        def kurskal(points):
            distance_map = [[distance(points[i], points[j]), i, j] for i in range(n) for j in range(i)]
            distance_map.sort(reverse=True)
            label = list(range(n))
            combine_times = 0
            res = 0
            while combine_times != n - 1:
                mini_distance, i, j = distance_map.pop()
                if label[i] != label[j]:
                    label = [label[j] if label[k] == label[i] else label[k] for k in range(n)]
                    combine_times += 1
                    res += mini_distance
            return res

        distance = lambda x, y: abs(x[0] - y[0]) + abs(x[1] - y[1])
        n = len(points)
        return kurskal(points)

刷题总结

最小生成树问题时经典的贪心问题，其实难度并不大，记住思路就可以很容易的写出来，这时一个非常重要的算法，小伙伴们务必掌握它。