程序实现克鲁斯卡尔算法
时间: 2023-07-10 21:03:51 浏览: 51
克鲁斯卡尔算法是一种最小生成树的算法,用于在一个加权连通图中找到最小生成树。下面是使用 Python 实现克鲁斯卡尔算法的示例代码:
```python
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = []
def add_edge(self, u, v, w):
self.graph.append([u, v, w])
def find(self, parent, i):
if parent[i] == i:
return i
return self.find(parent, parent[i])
def union(self, parent, rank, x, y):
xroot = self.find(parent, x)
yroot = self.find(parent, y)
if rank[xroot] < rank[yroot]:
parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot
else:
parent[yroot] = xroot
rank[xroot] += 1
def kruskal(self):
result = []
i = 0
e = 0
self.graph = sorted(self.graph, key=lambda item: item[2])
parent = []
rank = []
for node in range(self.V):
parent.append(node)
rank.append(0)
while e < self.V - 1:
u, v, w = self.graph[i]
i = i + 1
x = self.find(parent, u)
y = self.find(parent, v)
if x != y:
e = e + 1
result.append([u, v, w])
self.union(parent, rank, x, y)
print("Minimum Spanning Tree:")
for u, v, weight in result:
print("%d - %d: %d" % (u, v, weight))
g = Graph(4)
g.add_edge(0, 1, 10)
g.add_edge(0, 2, 6)
g.add_edge(0, 3, 5)
g.add_edge(1, 3, 15)
g.add_edge(2, 3, 4)
g.kruskal()
```
在上面的示例中,我们使用了一个 `Graph` 类来表示图,并实现了 `add_edge` 方法来添加边。`kruskal` 方法实现了克鲁斯卡尔算法,并输出最小生成树的边和权重。