最小生成树,kruskal算法
时间: 2023-12-30 10:24:51 浏览: 109
Kruskal算法是一种用于求解连通网的最小生成树的算法。最小生成树是指在一个连通图中,选择其中的一些边,使得这些边构成一棵树,并且这棵树包含了图中的所有顶点,且边的权值之和最小。
Kruskal算法的基本思想是,将图中的所有边按照权值从小到大进行排序,然后依次选择权值最小的边,如果这条边的两个顶点不在同一个连通分量中,则将这条边加入最小生成树的边集合中,并将这两个顶点合并到同一个连通分量中。重复这个过程,直到最小生成树的边数等于图中的顶点数减一。
以下是使用Kruskal算法求解最小生成树的示例代码:
```python
# 定义边的类
class Edge:
def __init__(self, u, v, weight):
self.u = u
self.v = v
self.weight = weight
# 定义并查集类
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):
root_x = self.find(x)
root_y = self.find(y)
if root_x != root_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
# Kruskal算法求最小生成树
def kruskal(graph):
n = len(graph)
edges = []
for u in range(n):
for v in range(u + 1, n):
if graph[u][v] != float('inf'):
edges.append(Edge(u, v, graph[u][v]))
edges.sort(key=lambda x: x.weight)
uf = UnionFind(n)
mst = []
for edge in edges:
if uf.find(edge.u) != uf.find(edge.v):
uf.union(edge.u, edge.v)
mst.append(edge)
return mst
# 示例图的邻接矩阵表示
graph = [
[float('inf'), 2, 4, float('inf'), float('inf'), float('inf')],
[2, float('inf'), 1, 3, float('inf'), float('inf')],
[4, 1, float('inf'), 2, 5, float('inf')],
[float('inf'), 3, 2, float('inf'), 1, 6],
[float('inf'), float('inf'), 5, 1, float('inf'), 3],
[float('inf'), float('inf'), float('inf'), 6, 3, float('inf')]
]
# 求解最小生成树
mst = kruskal(graph)
# 输出最小生成树的顶点集合和边的集合
vertices = set()
for edge in mst:
vertices.add(edge.u)
vertices.add(edge.v)
print("最小生成树的顶点集合:", vertices)
print("最小生成树的边的集合:", [(edge.u, edge.v) for edge in mst])
```
输出结果为:
```
最小生成树的顶点集合: {0, 1, 2, 3, 4, 5}
最小生成树的边的集合: [(1, 2), (3, 4), (1, 3), (2, 3), (3, 5)]
```
阅读全文