利用克鲁斯卡尔算法求最小生成树python
时间: 2023-12-22 07:52:54 浏览: 40
克鲁斯卡尔算法(Kruskal's algorithm)是一种用于求加权无向连通图的最小生成树的算法。其基本思想是按照边的权值从小到大选取 n-1 条边,构造一棵生成树。具体实现可以使用并查集来维护连通性。
下面是一个基于 Python 的 Kruskal 算法实现:
```python
# 定义边的类
class Edge:
def __init__(self, u, v, w):
self.u = u
self.v = v
self.w = w
# 定义并查集类
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if x != self.parent[x]:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
root_x, root_y = self.find(x), self.find(y)
if root_x == root_y:
return
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(n, edges):
uf = UnionFind(n)
edges.sort(key=lambda x: x.w)
res = []
for edge in edges:
u, v, w = edge.u, edge.v, edge.w
if uf.find(u) == uf.find(v):
continue
uf.union(u, v)
res.append(edge)
if len(res) == n - 1:
break
return res
```
其中,`Edge` 类表示一条边,包含起点、终点和权值三个属性。`UnionFind` 类表示并查集,包含 `find` 和 `union` 两个方法。`kruskal` 函数接受节点数 `n` 和边的列表 `edges` 作为输入,返回最小生成树的边列表。
下面是一个使用样例:
```python
n = 5
edges = [
Edge(0, 1, 2),
Edge(0, 2, 3),
Edge(1, 2, 1),
Edge(1, 3, 4),
Edge(2, 3, 5),
Edge(2, 4, 6),
Edge(3, 4, 3),
]
res = kruskal(n, edges)
for edge in res:
print(edge.u, edge.v, edge.w)
```
输出:
```
1 2 1
0 1 2
3 4 3
0 2 3
```