Kruskal 最小生成樹算法

def minCostConnectPoints(self, points):""":type points: List[List[int]]:rtype: int"""n = len(points)mp = []parent = list(range(n))for i in range(n):for j in range(i+1,n):mp.append((abs(points[i][0]-points[j][0]) + abs(points[i][1] - points[j][1]),i,j)) #把每個節點連接起來，并計算權重def find(x): #路徑壓縮，找根節點if x!= parent[x]:parent[x] = find(parent[x])return parent[x]def union(index1,index2): #兩個集合合并parent[find(index1)] = find(index2)mp.sort() #最小生成樹，用到貪心算法，先連接權重小的邊cost = 0edges = 0for d,i,j in mp:if find(i) != find(j): #并查集判斷，不能構成環union(i,j)cost += d edges += 1if edges == n-1:breakreturn cost

prim最小生成樹算法

def minCostConnectPoints(self, points):""":type points: List[List[int]]:rtype: int"""n = len(points)mp = []visited = set() #記錄已經訪問的元素，在兩個地方都要用到 def cut(i): #這里相當于找連接好的集合里的所有節點，與未連接的節點間的最短邊for j in range(n):if j not in visited: #這兩個節點間的邊已經用過了，無需重復計算heapq.heappush(mp,(abs(points[i][0]-points[j][0]) + abs(points[i][1] - points[j][1]),j))mincost = 0cut(0) #從節點0開始visited.add(0) #記錄訪問while len(visited) != len(points): #所有節點都進行了連接d,node = heappop(mp) #找最短邊if node in visited: #這個節點連接過了，下一個continuemincost += d #權重加起來cut(node) #前面節點集合里的對外邊已經計算過了，計算最新加入的就行visited.add(node) #記錄訪問 return mincost

不用堆節約時間

def minCostConnectPoints(self, points: List[List[int]]) -> int:#Prim算法n = len(points)d = [float("inf")] * n # 表示各個頂點與加入最小生成樹的頂點之間的最小距離.vis = [False] * n # 表示是否已經加入到了最小生成樹里面d[0] = 0ans = 0for _ in range(n):# 尋找目前這輪的最小dM = float("inf") for i in range(n):if not vis[i] and d[i] < M:node = iM = d[i]vis[node] = Trueans += M# 更新與這個頂點相連接的頂點的d.for i in range(n):if not vis[i]:d[i] = min(d[i], abs(points[i][0] - points[node][0]) + abs(points[i][1] - points[node][1]))return ans

總結

以上是生活随笔為你收集整理的LC1584. 连接所有点的最小费用的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。