# 最小生成树算法
# 概述
最小生成树（Minimum Spanning Tree，MST）是一个带权无向图所有生成树中权值和最小的生成树。本文介绍两种经典的最小生成树算法：Prim算法和Kruskal算法。
# Prim算法
# 算法原理
Prim算法从任意顶点开始，每次选择一个与当前树距离最近的顶点加入树中，直到所有顶点都被加入为止。
# 算法步骤
- 选择任意顶点作为起始点，加入MST
- 找到与当前MST中顶点相连的最小权值边
- 将该边连接的未访问顶点加入MST
- 重复步骤2-3直到所有顶点都在MST中
# 复杂度分析
- 时间复杂度：O(V^2)，其中V是顶点数
- 空间复杂度：O(V)
# 代码实现
def prim(graph):
n = len(graph)
selected = [False] * n
selected[0] = True
edges = 0
mst_weight = 0
while edges < n - 1:
minimum = float('inf')
x = 0
y = 0
for i in range(n):
if selected[i]:
for j in range(n):
if not selected[j] and graph[i][j]:
if graph[i][j] < minimum:
minimum = graph[i][j]
x = i
y = j
selected[y] = True
mst_weight += graph[x][y]
edges += 1
return mst_weight
# 示例
比较次数: 0
已访问节点:
# Kruskal算法
# 算法原理
Kruskal算法按照边的权值从小到大的顺序选择边，如果该边不会在MST中形成环，则将其加入MST。
# 算法步骤
- 将图中所有边按权值排序
- 依次选择权值最小的边
- 如果加入该边不会形成环，则将其加入MST
- 重复步骤2-3直到选择了V-1条边
# 复杂度分析
- 时间复杂度：O(E log E)，其中E是边数
- 空间复杂度：O(V)，其中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 kruskal(graph):
n = len(graph)
edges = []
# 收集所有边
for i in range(n):
for j in range(i + 1, n):
if graph[i][j]:
edges.append((graph[i][j], i, j))
# 按权值排序
edges.sort()
uf = UnionFind(n)
mst_weight = 0
edge_count = 0
for weight, u, v in edges:
if uf.union(u, v):
mst_weight += weight
edge_count += 1
if edge_count == n - 1:
break
return mst_weight
# 示例
比较次数: 0
已访问节点:
# 应用场景
- 网络布线规划
- 电路设计
- 通信网络设计
- 供水管网规划
# 算法比较
| 算法 | 适用场景 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| Prim | 稠密图 | O(V^2) | O(V) |
| Kruskal | 稀疏图 | O(E log E) | O(V) |