doocs/leetcode 最小生成树：从理论到实战的完整指南
项目地址: https://gitcode.com/doocs/leetcode 概述
最小生成树（Minimum Spanning Tree，MST）是图论中的一个经典问题，它在网络设计、电路布线、聚类分析等领域有着广泛的应用。在 LeetCode 算法题库中，最小生成树相关题目是面试中的高频考点，也是检验算法能力的重要标准。
本文将深入探讨 doocs/leetcode 项目中最小生成树相关题目的解决方案，涵盖 Prim 算法、Kruskal 算法等核心算法，并通过实际代码示例展示如何高效解决这类问题。
最小生成树基础概念
什么是最小生成树？
最小生成树是指在一个带权无向连通图中，找到一个边的子集，使得：
- 这个子集连接了图中所有顶点
- 不包含任何环
- 所有边的权重之和最小
核心算法对比
| 算法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| Prim 算法 | O(n²) | O(n) | 稠密图 |
| Kruskal 算法 | O(m log m) | O(n) | 稀疏图 |
其中 n 为顶点数，m 为边数。
经典算法详解
Prim 算法
Prim 算法采用贪心策略，从单个顶点开始，逐步扩展生成树。算法流程如下：
Kruskal 算法
Kruskal 算法同样采用贪心策略，但处理方式不同：
doocs/leetcode 最小生成树题目解析
1135. 最低成本联通所有城市
问题描述：给定 n 个城市和连接成本，求联通所有城市的最小成本。
解决方案：使用 Kruskal 算法
class Solution:
def minimumCost(self, n: int, connections: List[List[int]]) -> int:
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
connections.sort(key=lambda x: x[2])
p = list(range(n))
ans = 0
for x, y, cost in connections:
x, y = x - 1, y - 1
if find(x) == find(y):
continue
p[find(x)] = find(y)
ans += cost
n -= 1
if n == 1:
return ans
return -1
算法分析：
- 时间复杂度：O(m log m)，其中 m 为边数
- 空间复杂度：O(n)，用于并查集存储
1584. 连接所有点的最小费用
问题描述：给定二维平面上的点，用曼哈顿距离作为连接成本，求最小连接成本。
解决方案：提供两种方法
方法一：朴素 Prim 算法
class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
n = len(points)
g = [[0] * n for _ in range(n)]
dist = [float('inf')] * n
vis = [False] * n
# 构建邻接矩阵
for i, (x1, y1) in enumerate(points):
for j in range(i + 1, n):
x2, y2 = points[j]
t = abs(x1 - x2) + abs(y1 - y2)
g[i][j] = g[j][i] = t
dist[0] = 0
ans = 0
for _ in range(n):
i = -1
for j in range(n):
if not vis[j] and (i == -1 or dist[j] < dist[i]):
i = j
vis[i] = True
ans += dist[i]
for j in range(n):
if not vis[j]:
dist[j] = min(dist[j], g[i][j])
return ans
方法二：Kruskal 算法
class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
def find(x: int) -> int:
if p[x] != x:
p[x] = find(p[x])
return p[x]
n = len(points)
g = []
# 生成所有边
for i, (x1, y1) in enumerate(points):
for j in range(i + 1, n):
x2, y2 = points[j]
t = abs(x1 - x2) + abs(y1 - y2)
g.append((t, i, j))
p = list(range(n))
ans = 0
# 按权重排序边
for cost, i, j in sorted(g):
pa, pb = find(i), find(j)
if pa == pb:
continue
p[pa] = pb
ans += cost
n -= 1
if n == 1:
break
return ans
1489. 找到最小生成树里的关键边和伪关键边
问题描述：识别最小生成树中的关键边和伪关键边。
关键边：删除后会导致最小生成树权重增加的边 伪关键边：可能出现在某些最小生成树中但不会出现在所有最小生成树中的边
class UnionFind:
def __init__(self, n):
self.p = list(range(n))
self.n = n
def union(self, a, b):
if self.find(a) == self.find(b):
return False
self.p[self.find(a)] = self.find(b)
self.n -= 1
return True
def find(self, x):
if self.p[x] != x:
self.p[x] = self.find(self.p[x])
return self.p[x]
class Solution:
def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:
# 为每条边添加索引
for i, e in enumerate(edges):
e.append(i)
edges.sort(key=lambda x: x[2])
# 计算原始最小生成树权重
uf = UnionFind(n)
v = sum(w for f, t, w, _ in edges if uf.union(f, t))
ans = [[], []]
for f, t, w, i in edges:
# 测试删除该边后的最小生成树
uf = UnionFind(n)
k = sum(z for x, y, z, j in edges if j != i and uf.union(x, y))
if uf.n > 1 or (uf.n == 1 and k > v):
ans[0].append(i) # 关键边
continue
# 测试强制包含该边的最小生成树
uf = UnionFind(n)
uf.union(f, t)
k = w + sum(z for x, y, z, j in edges if j != i and uf.union(x, y))
if k == v:
ans[1].append(i) # 伪关键边
return ans
算法选择策略
何时使用 Prim 算法？
- 图比较稠密（边数接近顶点数的平方）
- 需要频繁查询顶点间距离
- 可以使用堆优化版本提高效率
何时使用 Kruskal 算法？
- 图比较稀疏（边数远小于顶点数的平方）
- 边已经按权重排序或可以快速排序
- 需要判断边的关键性
性能优化技巧
Prim 算法优化
使用优先队列（堆）可以将时间复杂度优化到 O(m log n)：
import heapq
def prim_optimized(graph, n):
visited = [False] * n
min_heap = [(0, 0)] # (cost, vertex)
total_cost = 0
count = 0
while min_heap and count < n:
cost, vertex = heapq.heappop(min_heap)
if visited[vertex]:
continue
visited[vertex] = True
total_cost += cost
count += 1
for neighbor, weight in graph[vertex]:
if not visited[neighbor]:
heapq.heappush(min_heap, (weight, neighbor))
return total_cost if count == n else -1
Kruskal 算法优化
使用路径压缩和按秩合并优化并查集：
class OptimizedUnionFind:
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):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
elif self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
else:
self.parent[root_y] = root_x
self.rank[root_x] += 1
return True
实战应用场景
网络设计
最小生成树在计算机网络设计中用于构建成本最低的连接方案，确保所有节点都能通信且总成本最小。
电路布线
在集成电路设计中，最小生成树用于确定引脚间的最短连接路径，减少信号延迟和功耗。
聚类分析
在数据挖掘中，最小生成树可以用于层次聚类，通过删除最长边来将数据分割成不同的簇。
常见问题与解决方案
问题1：图不连通怎么办？
解决方案：在算法实现中检查连通分量数量，如果最终连通分量大于1，返回错误或特定值。
问题2：存在重边或自环怎么办？
解决方案：在构建图时过滤掉自环，对于重边只保留权重最小的边。
问题3：大规模图如何处理？
解决方案：使用优化后的算法版本，如堆优化的 Prim 算法或使用高效排序的 Kruskal 算法。
总结
最小生成树问题是图论中的基础且重要的问题，掌握 Prim 和 Kruskal 两种核心算法对于解决相关问题至关重要。通过 doocs/leetcode 项目中的实际题目练习，可以深入理解算法的实现细节和应用场景。
关键要点：
- Prim 算法适合稠密图，Kruskal 算法适合稀疏图
- 并查集是 Kruskal 算法的高效实现基础
- 理解关键边和伪关键边的概念有助于解决更复杂的问题
- 实际应用中需要根据具体场景选择合适的算法和优化策略
通过系统学习和实践，最小生成树相关问题将成为算法能力提升的重要阶梯。