kruskal算法求简单联通权图的最小生成树
时间: 2023-06-18 21:07:22 浏览: 53
Kruskal算法是一种贪心算法,用于求解加权连通图的最小生成树。
具体步骤如下:
1. 将连通图中的边按照权值从小到大排序。
2. 从小到大依次考虑每条边,如果加入这条边不会形成环,则将它加入最小生成树中。
3. 最终得到的就是原图的最小生成树。
Kruskal算法的实现可以使用并查集来判断是否形成环。
代码实现如下(假设边的信息存储在Edge类中):
```python
class Edge:
def __init__(self, u, v, w):
self.u = u
self.v = v
self.w = w
def kruskal(n, edges):
parent = list(range(n))
rank = [0] * n
edges.sort(key = lambda x: x.w)
res = []
for e in edges:
x, y = find(parent, e.u), find(parent, e.v)
if x != y:
res.append(e)
union(parent, rank, x, y)
return res
def find(parent, x):
if parent[x] != x:
parent[x] = find(parent, parent[x])
return parent[x]
def union(parent, rank, x, y):
if rank[x] < rank[y]:
parent[x] = y
elif rank[x] > rank[y]:
parent[y] = x
else:
parent[x] = y
rank[y] += 1
```
其中,n是节点数,edges是边的列表。返回的是最小生成树的边的列表。