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)，总权值为 1+2+3+2+1=9。

解题思路

方法：Kruskal 算法

思路：

• Kruskal 算法的核心思想是按照边的权值从小到大排序，然后依次选择边，如果这条边连接的两个顶点不在同一个连通分量中，则将其加入最小生成树。
• 具体步骤：
  1. 将所有边按照权值从小到大排序。
  2. 初始化一个并查集，用于跟踪顶点的连通性。
  3. 依次遍历排序后的边，对于每条边：
     • 如果边的两个顶点不在同一个连通分量中，将这条边加入最小生成树，并合并这两个顶点的连通分量。
  4. 重复步骤 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(key=lambda 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表示：A=0, B=1, C=2, D=3, E=4, F=5） 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(65+u)} - {chr(65+v)}: {weight}") print(f"Total 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 算法的原理和实现，对于理解和解决图论相关问题非常重要。