LeetCode 最小生成树题解

LeetCode 最小生成树题解题目描述给定一个带权无向图计算最小生成树的权重和。示例输入n 4,edges [[0,1,1],[0,2,2],[0,3,3],[1,2,1],[2,3,4]]输出4解题思路方法Kruskal 算法思路使用 Kruskal 算法计算最小生成树。将所有边按权重排序。遍历所有边如果两个节点不在同一个集合中则合并。复杂度分析时间复杂度O(E log E)。空间复杂度O(V)。代码实现class UnionFind: def __init__(self, n): self.parent list(range(n)) self.rank [0] * n def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x] def union(self, x, y): px, py self.find(x), self.find(y) if px py: return False if self.rank[px] self.rank[py]: px, py py, px self.parent[py] px if self.rank[px] self.rank[py]: self.rank[px] 1 return True def mst(n, edges): edges.sort(keylambda x: x[2]) uf UnionFind(n) weight 0 for u, v, w in edges: if uf.union(u, v): weight w return weight # 测试 def test_mst(): n 4 edges [[0, 1, 1], [0, 2, 2], [0, 3, 3], [1, 2, 1], [2, 3, 4]] print(mst(n, edges)) # 输出4 if __name__ __main__: test_mst()总结最小生成树是 Kruskal 算法的典型应用按权重排序边合并不在同一集合的节点。