克鲁斯卡尔算法最小堆实现
时间: 2023-12-10 11:35:30 浏览: 33
克鲁斯卡尔算法最小堆实现步骤如下:
1.将所有边按照权值从小到大排序,构建一个最小堆。
2.从最小堆中取出一条边,判断这条边的两个端点是否在同一个连通块中,如果不在同一个连通块中,则将这条边加入最小生成树中,并将这两个端点所在的连通块合并。
3.重复步骤2,直到最小生成树中有n-1条边为止(n为图中节点数)。
下面是克鲁斯卡尔算法最小堆实现的Python代码示例:
```python
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, i):
if self.parent[i] != i:
self.parent[i] = self.find(self.parent[i])
return self.parent[i]
def union(self, i, j):
x, y = self.find(i), self.find(j)
if x == y:
return False
if self.rank[x] < self.rank[y]:
x, y = y, x
self.parent[y] = x
if self.rank[x] == self.rank[y]:
self.rank[x] += 1
return True
class Kruskal:
def __init__(self, n, edges):
self.uf = UnionFind(n)
self.edges = edges
self.mst = []
def kruskal(self):
self.edges.sort()
for edge in self.edges:
if self.uf.union(edge[0], edge[1]):
self.mst.append(edge)
if len(self.mst) == n - 1:
break
return self.mst
n = 5
edges = [(0, 1, 2), (0, 3, 6), (1, 2, 3), (1, 3, 8), (1, 4, 5), (2, 4, 7), (3, 4, 9)]
kruskal = Kruskal(n, edges)
print(kruskal.kruskal())
```