实现采用克鲁斯卡尔算法求最小生成树代码
时间: 2023-07-22 15:21:15 浏览: 47
以下是一个简单的Python实现克鲁斯卡尔算法求最小生成树的代码,供参考:
```python
class Kruskal:
def __init__(self, num_vertices):
self.num_vertices = num_vertices
self.parent = [i for i in range(num_vertices)]
def find(self, vertex):
if self.parent[vertex] != vertex:
self.parent[vertex] = self.find(self.parent[vertex])
return self.parent[vertex]
def union(self, vertex1, vertex2):
parent1 = self.find(vertex1)
parent2 = self.find(vertex2)
self.parent[parent1] = parent2
def kruskal(self, edges):
mst = []
edges = sorted(edges, key=lambda x: x[2])
for edge in edges:
vertex1, vertex2, weight = edge
if self.find(vertex1) != self.find(vertex2):
self.union(vertex1, vertex2)
mst.append(edge)
return mst
```
在上面的代码中,我们定义了一个`Kruskal`类,其中包含了`find`和`union`两个函数来实现并查集,以及`kruskal`函数来实现克鲁斯卡尔算法。具体来说:
- `find`函数:用于查找给定顶点的祖先节点,如果该顶点不是根节点,则递归查找其祖先节点并进行路径压缩优化,最终返回该顶点的根节点。
- `union`函数:用于合并两个顶点所在的连通块,将其中一个的祖先节点指向另一个的祖先节点。
- `kruskal`函数:实现克鲁斯卡尔算法,首先按照边权值从小到大排序,然后依次遍历每一条边,如果该边连接的两个顶点不在同一个连通块中,则将它们合并,并将该边加入最小生成树中。
使用该类的示例如下:
```python
# 创建Kruskal对象,传入顶点数目
k = Kruskal(5)
# 边列表,每个元素为一个三元组,分别表示边的两个顶点和权值
edges = [(0, 1, 2), (0, 3, 6), (1, 2, 3), (1, 3, 8), (1, 4, 5), (2, 4, 7), (3, 4, 9)]
# 调用kruskal函数求最小生成树
mst = k.kruskal(edges)
# 输出最小生成树
for edge in mst:
print("顶点{}和顶点{}之间的边,权值为{}".format(edge[0], edge[1], edge[2]))
```
输出结果为:
```
顶点0和顶点1之间的边,权值为2
顶点1和顶点2之间的边,权值为3
顶点1和顶点4之间的边,权值为5
顶点0和顶点3之间的边,权值为6
```