实现最小生成树计算的Prim算法和Kruskal算法python
时间: 2023-11-18 15:10:33 浏览: 50
Prim算法实现:
```python
import heapq
class Graph:
def __init__(self, vertices):
self.graph = [[] for _ in range(vertices)]
self.vertices = vertices
def add_edge(self, u, v, w):
self.graph[u].append((v, w))
self.graph[v].append((u, w))
def prim(self, start):
# 初始化
visited = [False] * self.vertices
heap = [(0, start)]
mst_weight = 0
while heap:
# 取出当前最小权值的边
weight, current = heapq.heappop(heap)
if visited[current]:
continue
visited[current] = True
mst_weight += weight
# 添加所有连接当前节点的边到堆中
for neighbor, weight in self.graph[current]:
if not visited[neighbor]:
heapq.heappush(heap, (weight, neighbor))
return mst_weight
g = Graph(5)
g.add_edge(0, 1, 2)
g.add_edge(0, 3, 6)
g.add_edge(1, 3, 8)
g.add_edge(1, 2, 3)
g.add_edge(1, 4, 5)
g.add_edge(2, 4, 7)
print(g.prim(0))
```
Kruskal算法实现:
```python
class Graph:
def __init__(self, vertices):
self.graph = []
self.vertices = vertices
self.parent = [i for i in range(vertices)]
self.rank = [0] * vertices
def add_edge(self, u, v, w):
self.graph.append((u, v, w))
def find(self, node):
# 寻找父节点
if self.parent[node] != node:
self.parent[node] = self.find(self.parent[node])
return self.parent[node]
def union(self, x, y):
# 合并两个集合
xroot = self.find(x)
yroot = self.find(y)
if self.rank[xroot] < self.rank[yroot]:
self.parent[xroot] = yroot
elif self.rank[xroot] > self.rank[yroot]:
self.parent[yroot] = xroot
else:
self.parent[yroot] = xroot
self.rank[xroot] += 1
def kruskal(self):
# 初始化
self.graph = sorted(self.graph, key=lambda x: x[2])
mst_weight = 0
for u, v, w in self.graph:
if self.find(u) != self.find(v):
self.union(u, v)
mst_weight += w
return mst_weight
g = Graph(5)
g.add_edge(0, 1, 2)
g.add_edge(0, 3, 6)
g.add_edge(1, 3, 8)
g.add_edge(1, 2, 3)
g.add_edge(1, 4, 5)
g.add_edge(2, 4, 7)
print(g.kruskal())
```