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(key=lambda 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 算法的典型应用，按权重排序边，合并不在同一集合的节点。