克鲁斯卡尔算法的代码操作
时间: 2023-09-22 12:07:29 浏览: 42
克鲁斯卡尔算法是一种用于求解最小生成树的贪心算法。下面是一个示例代码实现:
```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.size = [1] * 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):
px, py = self.find(x), self.find(y)
if px != py:
if self.size[px] < self.size[py]:
px, py = py, px
self.parent[py] = px
self.size[px] += self.size[py]
# 克鲁斯卡尔算法实现
def kruskal(n, edges):
edges.sort(key=lambda e: e.w) # 按边权值从小到大排序
uf = UnionFind(n)
ans = []
for e in edges:
if uf.find(e.u) != uf.find(e.v):
uf.union(e.u, e.v)
ans.append(e)
if len(ans) == n - 1:
break
return ans
```
上述代码中,`Edge` 类表示一条边,包含起点 `u`,终点 `v` 和边权 `w`。`UnionFind` 类表示并查集数据结构,用于判断两个点是否在同一个连通块中。`kruskal` 函数是克鲁斯卡尔算法的实现,首先将所有边按照边权从小到大排序,然后依次遍历每条边,如果该边连接的两个点不在同一个连通块中,则将它们合并,并将该边加入最小生成树中。最后返回最小生成树的边集合。