数据结构之最小生成树

1. 引言

2. Prim算法

3. Kruskal算法

4. 性能分析与最佳实践

1. 引言

在图论中，最小生成树（Minimum Spanning Tree, MST）是一种在无向连通图中寻找一棵包含所有顶点的树，使得树的边权值之和最小的算法。最小生成树问题在实际中有广泛的应用，例如网络设计、交通规划等领域。本文将深入探讨两种著名的最小生成树算法：Prim算法和Kruskal算法。

2. Prim算法

2.1 基本原理

Prim算法是一种贪心算法，它从一个顶点开始，逐步扩展已选取的顶点集合，直到覆盖所有顶点。在每一步中，都选择一条连接已选取顶点集合与未选取顶点集合的最短边，并将其加入最小生成树中。

2.2 算法步骤

1. 初始化一个空的最小生成树和一个包含起始顶点的顶点集合。
2. 在所有连接已选取顶点集合与未选取顶点集合的边中，找到权值最小的边，并将其加入最小生成树。
3. 将该边的另一端点加入已选取顶点集合。
4. 重复步骤2和3，直到所有顶点都被选取。

2.3 代码示例

import heapq

def prim(graph):
mst = []
visited = [0]
edges = [
(cost, start, to)
for start in range(len(graph))
for to, cost in graph[start].items()
]
heapq.heapify(edges)

while edges:
cost, start, to = heapq.heappop(edges)
if to not in visited:
visited.append(to)
mst.append((start, to, cost))
for to_next, cost2 in graph[to].items():
if to_next not in visited:
heapq.heappush(edges, (cost2, to, to_next))

return mst
```

3. Kruskal算法

3.1 基本原理

Kruskal算法基于边的排序，首先将所有边按照权值从小到大排序，然后依次选择边加入最小生成树中，如果加入这条边不会形成环，则将其加入最小生成树，否则继续选择下一条边。

3.2 算法步骤

1. 将所有边按照权值从小到大排序。
2. 初始化一个空的最小生成树。
3. 遍历排序后的边列表，对于每条边，检查加入最小生成树后是否会形成环。
4. 如果不会形成环，将边加入最小生成树；否则继续遍历下一条边。
5. 重复步骤3和4，直到最小生成树包含所有顶点。

3.3 代码示例

def kruskal(graph):
def find(parent, i):
if parent[i] == i:
return i
return find(parent, parent[i])

def union(parent, rank, x, y):
root_x = find(parent, x)
root_y = find(parent, y)
if root_x != root_y:
if rank[root_x] > rank[root_y]:
parent[root_y] = root_x
else:
parent[root_x] = root_y
if rank[root_x] == rank[root_y]:
rank[root_y] += 1

mst = []
edges = [
(cost, start, to)
for start in range(len(graph))
for to, cost in graph[start].items()
]
edges.sort()

parent = [i for i in range(len(graph))]
rank = [0] * len(graph)

for cost, start, to in edges:
if find(parent, start) != find(parent, to):
mst.append((start, to, cost))
union(parent, rank, start, to)

return mst