最小生成树：Kruskal算法和Prim算法

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        res = [] #存储每条边在points中的两个下标和曼哈顿距离
        n = len(points)
        # 计算任意两点之间的曼哈顿距离，并将边添加到边列表中
        for i in range(n):
            x1, y1 = points[i]
            for j in range(i+1,n):
                x2,y2 = points[j]
                res.append([i,j,abs(x2-x1)+abs(y2-y1)]) #i,j表示边的起点和终点
        #对边排序
        res.sort(key=lambda x:x[2])
        #初始化并查集
        parent = list(range(n))#列表存储了每个节点的父节点信息。
        #在最初的时候，每个节点的父节点都是自身，即parent[i] = i，表示每个节点自成一个集合。
        def find(x):
            if x != parent[x]:
                parent[x] = find(parent[x])
            return parent[x]
        #构建最小生成树
        edge = 0 #初始化边数为0
        cost = 0
        for i ,j ,d in res:
            a,b = find(i),find(j) 
            if a!= b: #每次考虑一条边，检查该边的两个端点是否已经在同一个集合中(即是否构成环)
                parent[b] = a
                edge += 1
                cost += d
            if edge == n-1: #结束条件（最小生成树边数为n-1）
                break
        return cost

        n = len(points)
        d = [float("inf")]*n # 表示各个顶点与加入最小生成树的顶点之间的最小距离
        vis = [False]*n # 表示是否已经加入到了最小生成树里面
        d[0]= 0 # 选择第一个点作为起始点，将其距离设为0，表示到自身的距离为0
        cost = 0 # 最小生成树的总费用
        # 遍历每个顶点，将其加入到最小生成树中
        for _ in range(n): #也可替换成while循环
            # 寻找当前轮的最小d
            m = float("inf")
            node = -1  # 用于记录当前轮中距离最小的点
            
            for i in  range(n): 
            # 如果顶点i未加入到最小生成树，并且与已加入点之间的距离小于当前最小距离，则更新最小距离
                if not vis[i] and d[i] < m:
                    node = i
                    m = d[i]
            vis[node] = True # 将该点标记为已加入最小生成树
            cost += m # 更新最小生成树的总费用

            # 更新与加入的顶点相连接的顶点的d
            for i in range(n):
                 # 如果顶点i未加入到最小生成树，则更新其与加入顶点的距离
                if not vis[i]:
                    # 计算顶点i与加入顶点之间的曼哈顿距离，并更新距离列表d[i]
                    d[i] = min(d[i],abs(points[i][0]-points[node][0])+abs(points[i][1]-points[node][1]))
        return cost