最小生成树（MST）是一棵子图，它连接了图中的所有顶点且总权重最小。常见的最小生成树算法有Kruskal算法和Prim算法。下面是使用Python实现这两种算法的示例。
Kruskal算法
Kruskal算法通过边的权重从小到大排序并逐步添加边来构建最小生成树，避免形成环。
class DisjointSet:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, u):
if self.parent[u] != u:
self.parent[u] = self.find(self.parent[u])
return self.parent[u]
def union(self, u, v):
root_u = self.find(u)
root_v = self.find(v)
if root_u != root_v:
if self.rank[root_u] > self.rank[root_v]:
self.parent[root_v] = root_u
elif self.rank[root_u] < self.rank[root_v]:
self.parent[root_u] = root_v
else:
self.parent[root_v] = root_u
self.rank[root_u] += 1
def kruskal(n, edges):
edges.sort(key=lambda x: x[2]) # 按边的权重排序
ds = DisjointSet(n)
mst = []
for u, v, weight in edges:
if ds.find(u) != ds.find(v):
ds.union(u, v)
mst.append((u, v, weight))
return mst
# 示例
n = 4 # 顶点数
edges = [
(0, 1, 10),
(0, 2, 6),
(0, 3, 5),
(1, 3, 15),
(2, 3, 4)
]
mst = kruskal(n, edges)
print("Kruskal的最小生成树:", mst)
Prim算法
Prim算法从一个初始顶点开始，不断扩展树的顶点集合，始终选择连接树内外顶点的最小权重边。
import heapq
def prim(n, edges):
adj = [[] for _ in range(n)]
for u, v, weight in edges:
adj[u].append((weight, v))
adj[v].append((weight, u))
visited = [False] * n
min_heap = [(0, 0)] # (权重, 顶点)
mst = []
total_weight = 0
while min_heap:
weight, u = heapq.heappop(min_heap)
if visited[u]:
continue
visited[u] = True
total_weight += weight
mst.append(u)
for next_weight, v in adj[u]:
if not visited[v]:
heapq.heappush(min_heap, (next_weight, v))
return total_weight, mst
# 示例
n = 4 # 顶点数
edges = [
(0, 1, 10),
(0, 2, 6),
(0, 3, 5),
(1, 3, 15),
(2, 3, 4)
]
total_weight, mst = prim(n, edges)
print("Prim的最小生成树权重:", total_weight)
print("Prim的最小生成树顶点:", mst)
这两种算法都可以找到图的最小生成树，Kruskal算法适用于边数较少的稀疏图，而Prim算法在处理稠密图时更有效。选择使用哪种算法取决于具体的图结构和应用场景。
