使用net域名的大网站,wordpress目录加图标,青岛建设银行网站首页,wordpress实例网站文章目录 题目1584.连接所有点的最小费用 最小生成树MST#xff0c;有两种算法进行求解#xff0c;分别是Kruskal算法和Prim算法Kruskal算法从边出发#xff0c;适合用于稀疏图Prim算法从顶点出发#xff0c;适合用于稠密图#xff1a;基本思想是从一个起始顶点开始#… 文章目录 题目1584.连接所有点的最小费用 最小生成树MST有两种算法进行求解分别是Kruskal算法和Prim算法Kruskal算法从边出发适合用于稀疏图Prim算法从顶点出发适合用于稠密图基本思想是从一个起始顶点开始逐步扩展生成树每次选择一条连接已选顶点和未选顶点的最小权重边直到所有顶点都被包含在生成树中。
Prim算法的基本步骤
初始化选择一个起始顶点将其加入生成树中。选择最小边在所有连接生成树中顶点和未加入生成树的顶点的边中选择权重最小的边。扩展生成树将这条边及其连接的未加入顶点加入生成树。重复重复步骤2和步骤3直到所有顶点都加入生成树。 与求解最短路径的Dijkstra算法的求解思路是有异曲同工之妙的 Prim 算法的朴素模版时间复杂度 O ( n 2 ) O(n^2) O(n2)
# 该模版可以求解最小生成树的权值ans 0# done[i]表示节点i到最小生成树的最小距离是否确定done [False]*n # 注意现在并没有设置done[0]Truedis [float(inf)]*ndis[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 jdone[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 ( e l o g e ) O(eloge) O(eloge),e是边数Kruskal算法模版 # 先按照距离排序edge.sort(keylambda 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 0count 0 # 计数器# 对边进行遍历for d,x,y in edge:fx,fy find(x),find(y)# 当属于同一个祖先就不要不然会形成环if fx fy:continueans d# 更新计数器count1union(x,y)# 如何合并了n-1的边就结束if count n-1:breakreturn 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(i1,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]Truedis [float(inf)]*ndis[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 jdone[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 []# 将全部的边都加入这个edgefor i in range(n):x1,y1 points[i]for j in range(i1,n):x2,y2 points[j]d abs(x1-x2)abs(y1-y2)edge.append((d,i,j))# 先按照距离排序edge.sort(keylambda 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 0count 0 # 计数器for d,x,y in edge:fx,fy find(x),find(y)if fx fy:continueans dcount1union(x,y)if count n-1:breakreturn ans
