题解 | 最小生成树

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 返回最小的花费代价使得这n户人家连接起来
# @param n int整型 n户人家的村庄
# @param m int整型 m条路
# @param cost int整型二维数组 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
# @return int整型
#
class UnionFind:
    def __init__(self, n):
        self.parent=list(range(n+1))
        self.rank=[0]*(n+1)
    # def find(self,x): #找到x所在的顶点集的根节点
    #     while x!=self.parent[x]:#如果 x 不是根节点
    #         x=self.parent[x]
    #     return x
    def find(self,x):#查找的时候进行路径压缩
        while x!=self.parent[x]:#如果 x 不是根节点
            self.parent[x]=self.parent[self.parent[x]] #压缩,把x挂在它的‘爷爷’结点上
            x=self.parent[x]
        return x

    def union(self,x,y):
        rx,ry=self.find(x),self.find(y)
        if rx!=ry:#按秩合并，低秩根挂在高秩根下
            if self.rank[rx]<self.parent[ry]:
                self.parent[rx]=ry
            elif self.rank[rx]>self.parent[ry]:
                self.parent[ry]=rx
            else: #==
                self.parent[rx]=ry
                self.parent[ry]+=1 #秩要加1
            return True
        return False #根据Cycle Property, 这条边不属于任何最小生成树
 
class Solution:
    def miniSpanningTree(self , n: int, m: int, cost: List[List[int]]) -> int:
        # write code here
        #Cut Property: 任意地把顶点集分为两部分（称为一个割），跨割最小边必定出现在某颗最小生成树中
        #Cycle Property: 在任意带权图的某个环中，权重大于环中其他任何边的那条边，不可能属于任何最小生成树
        cost.sort(key=lambda edge:edge[2])#根据修路成本排序
        uf=UnionFind(n)
        edges=0
        money=0
        for u,v,w in cost: #Kruskal算法，贪心加入最短边
            if uf.union(u,v): #合并成功
                edges+=1
                money+=w
                if edges==n-1:
                    break
        return money

根据Cut Property和 Cycle Property，我们知道可以先对边按照权重进行排序，然后根据贪心原理、每次加入最短边来连通两个子集，并且舍弃会造成环的边（经过排序后，必然是环中权重最大的边，所以要舍弃）。其实也就是 Kruskal 算法。

关于如何判断加入边的时候、两个顶点是否在同一个子集从而是否会造成环，就需要用到并查集，然后再查找的过程中可以进行路径压缩、优化后续查找的时间复杂度。