LeetCode Kruskal 算法题解

LeetCode Kruskal 算法题解题目描述Kruskal 算法是一种用于构建最小生成树的贪心算法。最小生成树是连通图中所有边的权值之和最小的生成树。示例对于以下加权图A --(2)-- B --(4)-- C | | | (1) (3) (1) | | | D --(5)-- E --(2)-- F最小生成树的边包括A-D (1), A-B (2), B-E (3), E-F (2), F-C (1)总权值为 123219。解题思路方法Kruskal 算法思路Kruskal 算法的核心思想是按照边的权值从小到大排序然后依次选择边如果这条边连接的两个顶点不在同一个连通分量中则将其加入最小生成树。具体步骤将所有边按照权值从小到大排序。初始化一个并查集用于跟踪顶点的连通性。依次遍历排序后的边对于每条边如果边的两个顶点不在同一个连通分量中将这条边加入最小生成树并合并这两个顶点的连通分量。重复步骤 3直到最小生成树包含 V-1 条边其中 V 是顶点数。复杂度分析时间复杂度O(E log E)其中 E 是边数。排序边的时间复杂度为 O(E log E)并查集的操作时间接近常数。空间复杂度O(E V)需要存储边和并查集的信息。代码实现方法Kruskal 算法# 并查集类 class UnionFind: def __init__(self, size): self.parent list(range(size)) self.rank [0] * size 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): x_root self.find(x) y_root self.find(y) if x_root y_root: return False # 已经在同一个集合中 # 按秩合并 if self.rank[x_root] self.rank[y_root]: self.parent[x_root] y_root else: self.parent[y_root] x_root if self.rank[x_root] self.rank[y_root]: self.rank[x_root] 1 return True # Kruskal 算法 def kruskal(edges, num_vertices): # 按照边的权值从小到大排序 edges.sort(keylambda x: x[2]) uf UnionFind(num_vertices) min_spanning_tree [] total_weight 0 for edge in edges: u, v, weight edge if uf.union(u, v): min_spanning_tree.append(edge) total_weight weight # 最小生成树包含 V-1 条边 if len(min_spanning_tree) num_vertices - 1: break return min_spanning_tree, total_weight # 测试 def test_kruskal(): # 构建图的边列表顶点用0-5表示A0, B1, C2, D3, E4, F5 edges [ (0, 1, 2), # A-B (2) (0, 3, 1), # A-D (1) (1, 2, 4), # B-C (4) (1, 4, 3), # B-E (3) (2, 5, 1), # C-F (1) (3, 4, 5), # D-E (5) (4, 5, 2), # E-F (2) ] num_vertices 6 # 测试 Kruskal 算法 min_spanning_tree, total_weight kruskal(edges, num_vertices) print(Minimum Spanning Tree edges:) for u, v, weight in min_spanning_tree: print(f{chr(65u)} - {chr(65v)}: {weight}) print(fTotal weight: {total_weight}) # 输出 # Minimum Spanning Tree edges: # A - D: 1 # C - F: 1 # A - B: 2 # E - F: 2 # B - E: 3 # Total weight: 9 if __name__ __main__: test_kruskal()测试用例测试用例最小生成树输入A --(2)-- B --(4)-- C | | | (1) (3) (1) | | | D --(5)-- E --(2)-- F输出Minimum Spanning Tree edges: A - D: 1 C - F: 1 A - B: 2 E - F: 2 B - E: 3 Total weight: 9总结Kruskal 算法是一种重要的图论算法它可以用于构建最小生成树。通过贪心策略和并查集Kruskal 算法可以高效地找到权值之和最小的生成树。Kruskal 算法的核心思想是按照边的权值从小到大排序然后依次选择边如果这条边连接的两个顶点不在同一个连通分量中则将其加入最小生成树。掌握 Kruskal 算法的原理和实现对于理解和解决图论相关问题非常重要。