本文主要是介绍Leetcode 1135. Connecting Cities With Minimum Cost [Python]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
最小生成树，可以采用克鲁斯卡算法，先按照边的权重排序，然后遍历这些边的三元组，两个节点通过Find函数查找是否已经在一个相连的部分内（Parent是否一样），如果不是，则Union起来，边的cnt+=1，总权重res增加对应的边的权重。当边的数量为节点数减1时，则所有节点都连接为一个整体了。
class Solution:def minimumCost(self, N: int, connections: List[List[int]]) -> int:pat = [0]*(N+1)for i in range(1,N+1):pat[i] = idef find(a, pat):if pat[a] != a:pat[a] = find(pat[a], pat)return pat[a] def union(a, b):pa = find(a, pat)pb = find(b, pat)if pa != pb:pat[pb] = paconnections.sort(key = lambda x:x[2])res = 0cnt = 0#graph = collections.defaultdict(int)for con in connections:#graph[(con[0],con[1])] = con[2]p0 = find(con[0], pat)p1 = find(con[1], pat)if p0 != p1:pat[p1] = p0cnt += 1res += con[2]if cnt < N-1:return -1else:return res
这篇关于Leetcode 1135. Connecting Cities With Minimum Cost [Python]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
