图论 之 最小生成树

• 最小生成树MST，有两种算法进行求解，分别是Kruskal算法和Prim算法
• Kruskal算法从边出发，适合用于稀疏图
• Prim算法从顶点出发，适合用于稠密图：基本思想是从一个起始顶点开始，逐步扩展生成树，每次选择一条连接已选顶点和未选顶点的最小权重边，直到所有顶点都被包含在生成树中。

Prim算法的基本步骤：

• 初始化：选择一个起始顶点，将其加入生成树中。
• 选择最小边：在所有连接生成树中顶点和未加入生成树的顶点的边中，选择权重最小的边。
• 扩展生成树：将这条边及其连接的未加入顶点加入生成树。
• 重复：重复步骤2和步骤3，直到所有顶点都加入生成树。

与求解最短路径的Dijkstra算法的求解思路是有异曲同工之妙的

• Prim 算法的朴素模版，时间复杂度$O(n^2)$

# 该模版可以求解最小生成树的权值
        ans = 0
        # done[i]表示节点i到最小生成树的最小距离是否确定
        done = [False]*n # 注意，现在并没有设置done[0]=True
        dis = [float('inf')]*n
        dis[0] = 0
        # 构建最小生成树
        for i in range(n):
            m = float('inf')
            # 还没在树中，并且到达树的距离最小的节点
            for j in range(n):
                if not done[j] and (node < 0 or dis[j] < dis[node]):
                    node = j
            done[node] = True
            # 累加情况
            ans += dis[node]
            # 更新node的邻居的情况
            for neigh in range(n):
                if not done[neigh] and edge[node][neigh] < dis[neigh]:
                    dis[neigh] = edge[node][neigh]
        return ans

• Kruakal算法是从边出发，一直合并不与当前节点形成环的边，时间复杂度$O(eloge)$,e是边数
• Kruskal算法模版

        # 先按照距离排序
        edge.sort(key=lambda x:x[0])

        # 使用并查集
        parent = list(range(n))
        def find(index):
            if parent[index] != index:
                parent[index] = find(parent[index])
            return parent[index]
        def union(index1,index2):
            parent[find(index1)] = find(index2)
        ans = 0
        count = 0 # 计数器
        # 对边进行遍历
        for d,x,y in edge:
            fx,fy = find(x),find(y)
            # 当属于同一个祖先就不要，不然会形成环
            if fx == fy:
                continue
            ans += d
            # 更新计数器
            count+=1
            union(x,y)
            # 如何合并了n-1的边，就结束
            if count == n-1:
                break
        return ans

题目

1584.连接所有点的最小费用

1584.连接所有点的最小费用

思路分析：最小生成树的模版题目

• 使用Prim算法模版题

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        # 有两种实现方式，分别是Kruskal算法和Prim 算法
        # Kruskal算法从边出发，适合用于稀疏图，prim算法从点出发，适合用于稠密图
        n = len(points)
        # 先构建邻接表
        edge = [[float('inf')]*n for _ in range(n)]
        for i in range(n):
            x1,y1 = points[i]
            for j in range(i+1,n):
                x2,y2 = points[j]
                d = abs(x1-x2)+abs(y1-y2)
                edge[i][j] = d 
                edge[j][i] = d 
        # 该模版可以求解最小生成树的权值
        ans = 0
        # done[i]表示节点i到最小生成树的最小距离是否确定
        done = [False]*n # 注意，现在并没有设置done[0]=True
        dis = [float('inf')]*n
        dis[0] = 0
        # 构建最小生成树
        for i in range(n):
            m = float('inf')
            # 还没在树中，并且到达树的距离最小的节点
            for j in range(n):
                if not done[j] and (node < 0 or dis[j] < dis[node]):
                    node = j
            done[node] = True
            # 累加情况
            ans += dis[node]
            # 更新node的邻居的情况
            for neigh in range(n):
                if not done[neigh] and edge[node][neigh] < dis[neigh]:
                    dis[neigh] = edge[node][neigh]
        return ans

• 使用Kruskal算法模版

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        # 有两种实现方式，分别是Kruskal算法和Prim 算法
        # Kruskal算法从边出发，适合用于稀疏图，prim算法从点出发，适合用于稠密图

        # 使用Kruskal，从边出发
        n = len(points)
        edge = []
        # 将全部的边都加入这个edge
        for i in range(n):
            x1,y1 = points[i]
            for j in range(i+1,n):
                x2,y2 = points[j]
                d = abs(x1-x2)+abs(y1-y2)
                edge.append((d,i,j))
        # 先按照距离排序
        edge.sort(key=lambda x:x[0])

        # 使用并查集
        parent = list(range(n))
        def find(index):
            if parent[index] != index:
                parent[index] = find(parent[index])
            return parent[index]
        def union(index1,index2):
            parent[find(index1)] = find(index2)
        ans = 0
        count = 0 # 计数器
        for d,x,y in edge:
            fx,fy = find(x),find(y)
            if fx == fy:
                continue
            ans += d
            count+=1
            union(x,y)
            if count == n-1:
                break
        return ans