几种常见的最小生成树算法以及代码实现注释
以下是几种常见的最小生成树算法（Minimum Spanning Tree, MST）以及带有代码注释的实现示例（使用Python语言）：
1. Prim算法：
- 原理：从一个起始顶点开始，逐步扩展生成最小生成树。每次选择与当前生成树连接的边中权重最小的边，将其连接的顶点加入生成树，直到生成树包含所有顶点为止。
- 实现（使用邻接矩阵表示图）：
```python
def prim_mst(graph):
num_vertices = len(graph)
# 初始化最小生成树的顶点集合和边集合
mst = []
visited = [False] * num_vertices
# 选择初始顶点
start_vertex = 0
visited[start_vertex] = True
while len(mst) < num_vertices - 1:
min_weight = float('inf')
min_edge = None
# 遍历已访问顶点集合，寻找权重最小的边
for i in range(num_vertices):
if visited[i]:
for j in range(num_vertices):
if not visited[j] and graph[i][j] < min_weight:
min_weight = graph[i][j]
min_edge = (i, j)
if min_edge:
# 将权重最小的边加入最小生成树
mst.append(min_edge)
visited[min_edge[1]] = True
return mst
```
2. Kruskal算法：
- 原理：按照边的权重从小到大选择，并且不形成环路。将边逐个加入生成树，直到生成树包含所有顶点为止。
- 实现（使用并查集表示集合）：
```python
class UnionFind:
def __init__(self, num_vertices):
self.parent = list(range(num_vertices))
self.rank = [0] * num_vertices
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 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
def kruskal_mst(graph):
num_vertices = len(graph)
# 初始化最小生成树的边集合
mst = []
# 按权重升序排序所有边
edges = []
for i in range(num_vertices):
for j in range(i+1, num_vertices):
if graph[i][j] != 0:
edges.append((i, j, graph[i][j]))
edges.sort(key=lambda x: x[2])
uf = UnionFind(num_vertices)
for edge in edges:
u, v, weight = edge
if uf.find(u) != uf.find(v):
# 加入当前边不会形成环路，将其加入最小生成树
mst.append((u, v, weight))
uf.union(u, v)
return mst
```
3. Boruvka算法：
- 原理：从每个连通分量中选择最小权重的边，将连通分量合并，重复这个过程，直到只剩下一个连通分量为止。
- 实现（使用邻接表表示图）：
```python
class Graph:
def __init__(self, num_vertices):
self.num_vertices = num_vertices
self.edges = []
def add_edge(self, src, dest, weight):
self.edges.append((src, dest, weight))
class Subset:
def __init__(self, parent, rank):
self.parent = parent
self.rank = rank
def find(subsets, i):
if subsets[i].parent != i:
subsets[i].parent = find(subsets, subsets[i].parent)
return subsets[i].parent
def union(subsets, x, y):
if subsets[x].rank < subsets[y].rank:
subsets[x].parent = y
elif subsets[x].rank > subsets[y].rank:
subsets[y].parent = x
else:
subsets[y].parent = x
subsets[x].rank += 1
def boruvka_mst(graph):
num_vertices = graph.num_vertices
mst = []
subsets = [Subset(i, 0) for i in range(num_vertices)]
cheapest = [-1] * num_vertices
num_trees = num_vertices
while num_trees > 1:
for i in range(len(graph.edges)):
src, dest, weight = graph.edges[i]
x = find(subsets, src)
y = find(subsets, dest)
if x != y:
if cheapest[x] == -1 or weight < graph.edges[cheapest[x]][2]:
cheapest[x] = i
if cheapest[y] == -1 or weight < graph.edges[cheapest[y]][2]:
cheapest[y] = i
for i in range(num_vertices):
if cheapest[i] != -1:
src, dest, weight = graph.edges[cheapest[i]]
x = find(subsets, src)
y = find(subsets, dest)
if x != y:
mst.append((src, dest, weight))
union(subsets, x, y)
num_trees -= 1
cheapest = [-1] * num_vertices
return mst
```
这些是常见的最小生成树算法及其代码实现。每种算法都有不同的时间复杂度和适用场景，根据具体问题的需求选择合适的算法。
